Expected Value of Local Maxima and Local Minima Recently I came across this question:
Given a random permutation of integers 1, 2, 3, …, n with a discrete, uniform distribution, find the expected number of local maxima. (A number is a local maxima if it is greater than the number before and after it.) For example, if n=4 and our permutation was 1, 4, 2, 3, then the # of local maxima would be 2 (both 4 and 3 are maxima).
I know the answer will be (n+1)/3 .I wanted to know what will be the answer when we have to consider the local maxima as well as the local minima i.e Finding out the expected number of local maxima and local minima.
 A: 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. 
A: 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 $ 
