What is the expected number of samples you’ll take until $x_{i+1} > x_i$?

1.1k Views Asked by At

Randomly (but uniformly) sample a number between $0$ and $1$. Stop the first time that a sample is greater than the immediately previous sample. That is, if your samples are labeled $x_1, x_2$, etc., stop when $x_{i+1} > x_i$.

What is the expected number of samples you’ll take until this happens?

1

There are 1 best solutions below

3
On BEST ANSWER

Neat enough, the expected number of samples is $e$.

Let $\sigma$ denote your stopping time.

$P(\sigma = 2) = 1/2, P(\sigma = 3) = 2/3!, \dots, P(\sigma = n) = (n-1)/n!$.

Putting it together:

$E\sigma = 2 P(\sigma = 2) + 3 P(\sigma = 3) + \dots = \sum_{k \geq 2} k(k-1)/k! = \sum_{k \geq 2} 1/(k-2)! = \sum_{k \geq 0} 1/k!$

Edit: It's worth noting that as long as your $x_i$ are in some bounded interval and i.i.d. without atoms, the same result would hold.