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:
\[p(i, x) = \frac{(1-x)^i (x+i)}{(i+1)!}\]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:
\[\mathbb{E}[l] = \sum_{i=0}^{\infty} i p(i, 0) dx = \sum_{i=0}^{\infty} \frac{i^2}{(i+1)!} = \sum_{i=0}^{\infty} \frac{i(i+1) - i}{(i+1)!} = e - 1\]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:
\[u(x) = \begin{cases} 0 & \text{if } x < 0 \\ 1 + \int_{0}^{1} u(x - y) dy = 1 + \int_{x-1}^{x} u(y) dy & \text{otherwise} \end{cases}\]We can derivate it to get:
\[u'(x) = \begin{cases} 0 & \text{if } x < 0 \\ u(x) - u(x-1) & \text{otherwise} \end{cases}\]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$.
\[(e^x P_n(x))' = e^x(P_n'(x) + P_n(x)) = e^x P_n(x) - e^{x-1} P_{n-1}(x-1)\]We get \(P'_n(x) = -\frac1e P_{n-1}(x-1)\). Since \(P_n(n) = P_{n-1}(x)\), we get:
\[\begin{align} P_0(x) &= 1 \\ P_n(x) &= P_{n-1}(n) - \frac{1}{e} \int_{n-1}^{x-1} P_{n-1}(y) dy \end{align}\]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?