Natural numbers permutation
The numbers 1,2,...,101 are randomly permuted. Define a number to be a local maxima if it is larger than it's 2 neighbouring numbers.
i.e. 5 and 7 are local maxima in the sequence 5,4,7, 6.
What is the expected number of local maxima in the permuted sequence.
NOTE: This problem is not original.
The answer is 34.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let Aj be the indicator random for the jth number in the sequence which has the value 1 when the jth number is a local maxima and 0 if the number isn't a local maxima.
We want to find E(A1 + A2 + .... + A100 + A101 ) = 2E(A1 ) + 99 (A2). This is true due to symmetry and the fact that E(A1+...+An) = E(A1)+....+ E(An) .
The expected value of an indicator random variable is the probability that the random variable takes on the value 1. So in this case E(A1)=E(A101) = 1/2 and E(A2)= E(A3)=...= E(a100) = 1/3.
So E(A1+... A101)= 2E(A1) +99E(A2) = 2(0.5) + 99(1/3) = 34