×

# Decreasing numbers

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?

Note by Jinay Patel
3 years, 8 months ago

Sort by:

This 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$ · 3 years, 8 months ago

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}$$ · 3 years, 8 months ago