Uniform variables are usually the first example of random variables that students see. They are easy to understand and to generate. But they are also a good source of puzzles. Here are two of them that I like. They can be solved quickly with a bit of insight but also lead to interesting generalizations. I also like that they both make appear the exponential function.

Problem 1

Statement

Let $X_i$ be a sequence of independent uniform random variables on $[0,1]$. Define $l$ as the largest integer such that $X_1 < … < X_l$. What is $\mathbb{E}[l]$?

Solution

Thinking of that problem as a dynamic programming problem, we need to add some state variable corresponding to the last value of $X_i$. We define $l(x)$ as the expected value of $l$ starting from $x$.

Then, $l(x) = \int_{x}^{1} 1 + l(y) dy = (1-x) + \int_{x}^{1} l(y) dy$.

We derivate to get $l’(x) = -l(x) - 1$. We have $l(1) = 0$ and thus $l(x) = e^{1-x} - 1$ and $l(0) = e - 1$.

Generalization

We can ask a more general question: what is the distribution of $l$?

Let’s define $p(i, x) = \Pr[X_1 > x \land l = i ]$. Thus, $p(i+1, x) = \int_{x}^{1} p(i, y) dy$.

A simple induction gives:

We can check that it sums to $1$ using properties of the exponential function.

We can also compute the expected value of $l$ and retrieve the previous result:

Problem 2

Statement

Let $X_i$ be a sequence of independent uniform random variables on $[0,1]$ and define $Y_k = X_1 + … + X_k$. Define $u(x) = \mathbb{E}[\min{k : Y_k > x}]$. What is u(1)?

Solution

We can think of it in a dynamic programming way: $u(x)$ is the number of steps to reach $x$ starting from $0$. Then we have the following recurrence:

We can derivate it to get:

We have solved the case where $0 \le x \le 1$ since $u(x-1) = 0$ which gives $u’(x) = u(x)$ and thus $u(x) = e^x$ as $u(0)=1$.

We get $u(1) = e$.

Generalization

The differential equation is harder to solve for $x > 1$.

We can show by induction that for $n \le x \le n+1$, $u(x) = \exp(x) P(n)$ for some polynomial $P$ of degree $n$.

We get \(P'_n(x) = -\frac1e P_{n-1}(x-1)\). Since \(P_n(n) = P_{n-1}(x)\), we get:

It’s easy to compute the first values of $P_n$ using sympy:

import sympy as sp

x = sp.Symbol('x')

P = sp.core.numbers.One()
for n in range(1, 8):
    P = P.subs(x, n) - sp.integrate(P, (x, n-1, x-1)) / sp.E
    print(P)

We can also make a nice conjecture on the limit of $u(n) - 2n$:

P = sp.core.numbers.One()
for n in range(1, 10):
    P = P.subs(x, n) - sp.integrate(P, (x, n-1, x-1)) / sp.E
    print(float(P.subs(x, n) * sp.exp(n) - 2*n))

0.7182818284590452
0.670774270471605
0.6665656395558899
0.6666044900326954
0.6666620686224118
0.6666671413781214
0.6666667815221434
0.6666666704268879
0.6666666652703214

$u(n) - 2n$ seems to converge to $\frac{2}{3}$. Do you have a nice proof?

(28 Jul 2024): Martin Ridout sent me a very interesting proof due to Hillel Furstenberg (who got the Abel prize in 2020) along with a lot of references. You can read it here.