Expected number of uniform variates which are strictly increasing
Tags: math
Let (r_1, r_2, \ldots) be an infinite sequence of iid uniform random variates. Let K be the largest number such that r_1 < r_2 < \cdots < r_K. What is \mathbb{E}[K]?
Note that:
\mathbb{E}[K] = \sum_{k=1}^{\infty} \text{Pr}[K \ge k].
We have K \ge k iff the k elements satisify r_1 < r_2 < \cdots < r_k, which happens with probability 1/k!. Therefore:
\mathbb{E}[K] = \sum_{k=1}^{\infty} \frac1{k!} = e - 1.