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 1. For each \(\displaystyle j \in [n] = \{1,2,\ldots,n\}\), let \(\displaystyle Y_j=\max\{X_1,\ldots,X_j\}\). We use induction on \(\displaystyle j\) to show that

\(\displaystyle \mathbb{E}[Y_j] = \sum\limits_{i=1}^{j}\frac{2^i}{2^i-1} \text{ for all }j\in[n] . \)

The base case \(\displaystyle j=1\) follows easily from definition.

For the inductive step, it suffices to show that \(\displaystyle \mathbb{E}[Y_{j+1}-Y_j] = \frac{2^{j+1}}{2^{j+1}-1}\) for every \(\displaystyle j\in[n-1]\). Note that \(\displaystyle Y_{j+1} \neq Y_j\) if and only if \(\displaystyle X_{j+1}>Y_j = \max\{X_1,\ldots,X_j\}\), in which case \(\displaystyle Y_{j+1}=X_{j+1}\). Thus,

\(\displaystyle \mathbb{E}[Y_{j+1}-Y_j]=\mathbb{P}[X_{j+1}>Y_j]\cdot\mathbb{E}[X_{j+1}-Y_j\mid X_{j+1}>Y_j]. \)

To compute \(\displaystyle \mathbb{P}[X_{j+1}>Y_j]\), note that for any fixed pairwise distinct positive integers \(\displaystyle a_1,\ldots,a_j\) and \(\displaystyle a>\max\{a_1,\ldots,a_j\}\),

$$\begin{align*} \mathbb{P}[(X_1,\ldots,X_{j+1}) = (a,a_1,\ldots,a_j)] & = \mathbb{P}[(X_1,\ldots,X_{j+1}) = (a_1,a,\ldots,a_j)] / 2 \\ & = \mathbb{P}[(X_1,\ldots,X_{j+1}) = (a_1,a_2,a,\ldots,a_j)] / 4 \\ & = \cdots = \mathbb{P}[(X_1,\ldots,X_{j+1}) = (a_1,\ldots,a_j,a)] / 2^j. \end{align*}$$

Therefore, summing over all possible \(\displaystyle a_1,\ldots,a_j\) and \(\displaystyle a>\max\{a_1,\ldots,a_j\}\), we see that

\(\displaystyle \mathbb{P}[X_{j+1}>Y_j] = \frac{2^j}{\sum_{i=0}^j2^i} = \frac{2^j}{2^{j+1}-1}. \)

To finish, it is easy to see that

\(\displaystyle \mathbb{E}[X_{j+1}-Y_j\mid X_{j+1}>Y_j] = \sum_{t=1}^\infty t\cdot\mathbb{P}[X_{j+1} = Y_j+t \mid X_{j+1} > Y_j] = \sum_{t=1}^\infty\frac t{2^t} = 2. \)

Solution 2. Since \(\displaystyle Y_n\) takes values in \(\displaystyle \mathbb{Z}_{>0}\),

\(\displaystyle \mathbb{E}[Y_n] = \sum_{k=1}^\infty\mathbb{P}[Y_n\geq k] . \)

For each \(\displaystyle k\in[n]\), \(\displaystyle \mathbb{P}[Y_n\geq k]=1\), while for each \(\displaystyle k>n\),

\(\displaystyle \mathbb{P}[Y_n\geq k] = 1-\mathbb{P}[Y_n<k] = 1-\mathbb{P}[X_1,\ldots,X_n<k] = 1-\prod_{i=1}^n\left(1-\frac1{2^{k-i}}\right) . \)

Note that this formula also works for every \(\displaystyle k\in[n]\), as the \(\displaystyle i=k\) term in the product is 0. Thus, it suffices to show that

\(\displaystyle \sum_{i=1}^{n}\frac{2^i}{2^i-1}=\sum_{k=1}^\infty\left(1-\prod_{i=1}^n\left(1-\frac1{2^{k-i}}\right)\right). \)

The case of \(\displaystyle n=1\) is easy to verify. Using induction on \(\displaystyle n\), it suffices to show that for every \(\displaystyle n\geq 2\),

\(\displaystyle \frac{1}{1-\frac1{2^n}} = \sum_{k=1}^\infty\left(\prod_{i=1}^{n-1}\left(1-\frac1{2^{k-i}}\right)-\prod_{i=1}^n\left(1-\frac1{2^{k-i}}\right)\right) = \sum_{k=1}^\infty\left(\frac1{2^{k-n}}\prod_{i=1}^{n-1}\left(1-\frac1{2^{k-i}}\right)\right). \)

Indeed, for every \(\displaystyle N>n\), after multiplying by \(\displaystyle 1-\frac1{2^n}\), the sum on the right telescopes as

$$\begin{align*} & \phantom{=} \left(1-\frac1{2^n}\right)\sum_{k=1}^{N}\left(\frac1{2^{k-n}}\prod_{i=1}^{n-1}\left(1-\frac1{2^{k-i}}\right)\right) = \sum_{k=1}^{N}\left(\left(\frac1{2^{k-n}}-\frac1{2^k}\right)\prod_{i=1}^{n-1}\left(1-\frac1{2^{k-i}}\right)\right) = \\ & = \sum_{k=1}^{N}\left(\prod_{i=1}^{n}\left(1-\frac1{2^{k+1-i}}\right)-\prod_{i=1}^{n}\left(1-\frac1{2^{k-i}}\right)\right) = \prod_{i=1}^{n}\left(1-\frac1{2^{N+1-i}}\right). \end{align*}$$

Taking \(\displaystyle N\) to infinity finishes the proof.

Solution. [3 (sketch)] It can be shown by induction or another method that for any sequence of positive integers \(\displaystyle a_1 < a_2 < \cdots < a_n\),

\(\displaystyle \mathbb{P}[\{X_1,\ldots,X_n\} = \{a_1,\ldots,a_n\}] = 2^{-\sum\limits_{i=1}^n a_i}\prod_{i=1}^n(2^i-1). \)

For any \(\displaystyle a_1 < a_2 < \cdots < a_n\), let \(\displaystyle d_1 = a_1\) and \(\displaystyle d_{i+1} = a_{i+1}-a_i\) for \(\displaystyle i\in[n-1]\), so

\(\displaystyle \mathbb{P}[\{X_1,\ldots,X_n\} = \{d_1,d_1+d_2,\ldots,d_1+\cdots+d_n\}] = 2^{-\sum\limits_{i=1}^n(n+1-i)d_i}\prod_{i=1}^n(2^i-1). \)

Note that \(\displaystyle (a_1,\ldots,a_n)\mapsto(d_1,\ldots,d_n)\) is a bijection between strictly increasing sequences in \(\displaystyle \mathbb{Z}_{>0}\) of length \(\displaystyle n\) and \(\displaystyle (\mathbb{Z}_{>0})^n\), so, using \(\displaystyle \sum\limits_{i\geq1}x^i = x/(1-x)\) and \(\displaystyle \sum\limits_{i\geq1}ix^i = x/(1-x)^2\), we get

$$\begin{align*} \mathbb{E}[Y_n] & = \prod_{i=1}^n(2^i-1)\sum_{d_1,\ldots,d_n\geq 1}\left(\sum_{i=1}^nd_i\right)2^{-\sum\limits_{j=1}^n(n+1-j)d_j} \\ & = \prod_{i=1}^n(2^i-1)\sum_{i=1}^n\left(\sum_{d_i\geq 1}d_i2^{-(n+1-i)d_i}\right)\prod_{j\not=i}\left(\sum_{d_j\geq 1}2^{-(n+1-j)d_j}\right) = \cdots = \sum_{i=1}^n\frac{2^i}{2^i-1} . \end{align*}$$