Expected Value of Local Maxima and Local Minima

Let $n\ge 3$. Suppose that the permutation $\alpha$ takes $k$ to $a_k$ ($k=1$ to $n$). Let $\alpha'$ be the permutation that takes $k$ to $(n+1)-a_k$. Then the number of local maxima (minima) of $\alpha$ is the same as the number of local minima (maxima) of $\alpha'$. Thus by symmetry the expected number of local maxima and the expected number of local minima are the same.

If the expected number of local maxima is $\frac{n+1}{3}$, it follows that the expected number of points that are local maxima or local minima is $\frac{2(n+1)}{3}$.

For completeness, we give a proof that the expected number of local maxima is indeed $\frac{n+1}{3}$.

Your example shows that you are including endpoint maxima. The probability that a random permutation has a left endpoint maximum is $\frac{1}{2}$, and the probability of a right endpoint maximum is the same, so the expected number of endpoint maxima is $1$.

Now let random variable $Y$ be the number of non-endpoint maxima. For $i=2$ to $n-1$, let $X_i=1$ if we have a local maximum at the $i$-th position, and let $X_i=0$ otherwise. Then $Y=X_2+X_3+\cdots+X_{n-1}$, and therefore by the linearity of expectation $$E(Y)=E(X_2)+E(X_3)+\cdots +E(X_{n-1}).$$ Now we find $\Pr(X_i=1)$. Consider the numbers that are in positions $i-1$, $i$, and $i+1$. There are $3!$ permutations of these numbers, and precisely $2$ of these permutations give a local maximum at $i$. Thus $\Pr(X_i=1)=\frac{2}{3!}=\frac{1}{3}$.

It follows that $E(Y)=(n-2)\cdot\frac{1}{3}$. Now add in the expected number $1$ of endpoint maxima. We get $(n-2)\cdot\frac{1}{3}+1$, which simplifies to $\frac{n+1}{3}$.

Remarks: $1.$ We prove directly that the number of places at which we have a local max or min is $\frac{2(n+1)}{3}$.

An endpoint is always a local max or min, giving us $2$ points. For the others, if $2\le i\le n-1$, let $W_i=1$ if we have a local max or min at the $i$-th position, and $0$ otherwise. Then the number $Z$ of non-endpoint local max or min is $W_2+W_3+\cdots+W_{n-1}$.

The probability that $W_i=1$ is $\frac{4}{3!}=\frac{2}{3}$. Thus $E(Z)=(n-2)\cdot\frac{2}{3}$. Add $2$ for the endpoints.

$2.$ We used the method of indicator random variables. It is often far easier than finding the expectation of a random variable by first finding its distribution.

Here is a numerical method that can be used to solve the problem for small K.

1) Brute force solve the problem for small x (say x = 3 to 12)
2) Find a common denominator for each of your solutions (for K = 2, the common denominator is 90)
3) put each solution in terms of the common denominator
4) Use the method of common differences to find what the maximum order of the quadratic equations will be $(ax^n + bx^{n-1} + cx^{n-2} ... )$
http://www.purplemath.com/modules/nextnumb.htm
5) using your solutions set up a matrix representing the system of linear equations and then solve the matrix, which will give you your values for $a, b, c$, ...
6) then use those values for your your equation.
7) simplify as desired

For $K = 2$, it simplifies to $E[X^2] = (40 X^2 - 144 X + 131)/90$
For $K = 3$, it simplifies to $E[X^3] = (280 X^3 -1344 X^2 + 2063 X - 1038)/945 $