What is the expected number of peaks in an array of length $n$ with each number randomly drawed from $[0, 1]$?

467 Views Asked by At

Suppose we randomly draw a real number from $[0, 1]$ for $n$ times, and get an array: $a_1, a_2, ..., a_n$. If for some integer $i$ such that $2<=i<=n-1$ and $a_{i-1}<a_i$ and $a_i>a_{i+1}$, we call $a_i$ a peak in the array.

The question is: what is the expected number of peaks in the array $a_1, a_2, ..., a_n$?

For example, in array $[0.6,0.3,0.7,0.4,0.9,0.8]$, there are $2$ peaks: $0.7$ and $0.9$.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $A_i =\{\text {Peak at}\ i\}$, and let $Y_i=I_{A_i}$ be the indicator function, where $2\le i\le n-1$. Since the $X_i$ are i.i.d., $P(A_i)=P(\{X_{i-1}\lt X_i\}\cap\{X_i\gt X_{i+1}\})$ is independent of $i$, and an easy calculation or an argument by symmetry shows this probability is $1/3$. The number of peaks is $W =\sum Y_i$ and $$E(W) = \sum E(Y_i) = \sum P(A_i) =\frac{n-2}{3}$$