Louis Abraham's Home Page

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.

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]$?

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$.

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)?

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:

Leave a Comment