International Mathematics Competition
for University Students
2025

IMC2025: Day 2, Problem 9

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

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

Let \(\displaystyle Y_n=\max\{X_1,\ldots,X_n\}\). Show that

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

where \(\displaystyle \mathbb{E}[Y_n]\) is the expected value of \(\displaystyle Y_n\).

Jan Kuś and Jun Yan, University of Warwick

  Solution