Pick a random number (evenly distributed) between 0 and 1. Continue picking random numbers as long as they keep decreasing; stop picking when you obtain a number that is greater than the previous one you picked. What is the expected number of numbers you pick?

## Comments

Sort by:

TopNewestThis is a non-combinatorial solution. The probability of successfully finding a run of at least length one is \(\int_0^1 dx_1\). It's easy to argue that the probability of successfully finding a run of at least length two is \(\int_0^1 (\int_0^{x_2} dx_1) dx_2\), and in general \[\int_0^1 \int_0^{x_n} \cdots \int_0^{x_2} dx_1 \cdots dx_n \] parameterizing this over \(x\) as \[p_n(x) = \int_0^x \int_0^{x_n} \cdots \int_0^{x_2} dx_1 \cdots dx_n \] we soon find that \(p_1(x) = x, p_2(x) = \frac{x^2}{2}, p_3(x) = \frac{x^3}{3!}, \dots, p_k(x) = \frac{x^k}{k!}\) such that the probability of encountering a run of at least length \(k\) is \(\frac{1}{k!}\) (by instantiating \(p\) at \(x = 1\)). Let \(P[X = k]\) be the probability of encountering a run of exactly length \(k\), then \[P[X = k] = p_k(1) - p_{k+1}(1) = \frac{1}{k!} - \frac{1}{(k+1)!} = \frac{k}{(k+1)!}\] the generating function of the expected value is then just \[f(x) = \sum_k \frac{k^2}{(k+1)!}x^k\] evaluated at \(x = 1\); this is clearly analytic around \(x = 0\) and also around \(x = 1\), so we can manipulate this series keeping in mind that the OGF of \(e^x = \sum_k \frac{x^k}{k!}\): \[\begin{align*} f(x) &= \sum_k \frac{k^2}{(k+1)!}x^k \\\\ &= x^{-1} \sum_k \frac{(k-1)^2}{k!} x^k \\\\ &= x^{-1} \left(\sum_k k^2 \frac{x^k}{k!} - 2\sum_k \frac{x^k}{(k-1)!} + \sum_k \frac{x^k}{k!}\right) \\\\ &= x^{-1} \left(\sum_k k \frac{x^k}{(k-1)!} - 2x\sum_k \frac{x^{k-1}}{(k-1)!} + e^x\right) \\\\ &= x^{-1} \left(x \sum_k (k+1) \frac{x^k}{k!} - 2xe^x + e^x\right) \\\\ &= \frac{x^2 - x + 1}{x} e^x\end{align*}\] where \[E[X] = f(1) = e\] – Lee Gao · 3 years, 8 months ago

Log in to reply

Not sure whether this is correct, but let's try.

The probability that you will get the chance of getting the \(n\)th number is \(\frac{1}{(n-1)!}\), as you need the previous \(n-1\) numbers to be ordered decreasing and all \((n-1)!\) possible orderings are equally likely. Summing over all \(n\) gives the expected number:

\(\displaystyle\sum_{n=1}^\infty \dfrac{1}{(n-1)!} = \boxed{e}\) – Ivan Koswara · 3 years, 8 months ago

Log in to reply