Expected number of uniform variates which are strictly increasing

Tags: math

Let (r1, r2, …) be an infinite sequence of iid uniform random variates. Let K be the largest number such that r1 < r2 < ⋯ < rK. What is 𝔼[K]?

Note that:


$$\mathbb{E}[K] = \sum_{k=1}^{\infty} \text{Pr}[K \ge k].$$

We have K ≥ k iff the k elements satisify r1 < r2 < ⋯ < rk, which happens with probability 1/k!. Therefore:


$$\mathbb{E}[K] = \sum_{k=1}^{\infty} \frac1{k!} = e - 1.$$

Posted on 2022-03-26