IMC 2025 · Problem 9

Let $n$ be a positive integer. Consider the following random process which produces a sequence of $n$ distinct positive integers $X_1, X_2, \ldots, X_n$.

First, $X_1$ is chosen randomly with $\mathbb{P}(X_1 = i) = 2^{-i}$ for every positive integer $i$. For $1 \le j \le n-1$, having chosen $X_1, \ldots, X_j$, arrange the remaining positive integers in increasing order as $n_1 < n_2 < \cdots$, and choose $X_{j+1}$ randomly with $\mathbb{P}(X_{j+1} = n_i) = 2^{-i}$ for every positive integer $i$.

Let $Y_n = \max\{X_1, \ldots, X_n\}$. Show that

$$\mathbb{E}[Y_n] = \sum_{i=1}^{n} \frac{2^i}{2^i - 1}$$

where $\mathbb{E}[Y_n]$ is the expected value of $Y_n$.