uniolympiads Ελληνικά

IMC 2025, Day 2, Problem 9

Let nn be a positive integer. Consider the following random process which produces a sequence of nn distinct positive integers X1,X2,…,XnX_1, X_2, \dots, X_n.

First, X1X_1 is chosen randomly with P(X1=i)=2−i\mathbb{P}(X_1 = i) = 2^{-i} for every positive integer ii. For 1≤j≤n−11 \le j \le n-1, having chosen X1,…,XjX_1, \dots, X_j, arrange the remaining positive integers in increasing order as n1<n2<⋯n_1 < n_2 < \cdots, and choose Xj+1X_{j+1} randomly with P(Xj+1=ni)=2−i\mathbb{P}(X_{j+1} = n_i) = 2^{-i} for every positive integer ii.

Let Yn=max⁡{X1,…,Xn}Y_n = \max\{X_1, \dots, X_n\}. Show that

E[Yn]=∑i=1n2i2i−1\mathbb{E}[Y_n] = \sum_{i=1}^{n} \frac{2^i}{2^i - 1}

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

Original from the official PDFLet n be a positive integer. Consider the following random process which produces a sequence of n distinct positive integers X 1 , X 2 , . . . , X n . First, X 1 is chosen randomly with P(X 1 = i) = 2 −i for every positive integer i. For 1 ≤ j ≤ n − 1, having chosen X 1 , . . . , X j , arrange the remaining positive integers in increasing order as n 1 < n 2 < · · · , and choose X j+1 randomly with P(X j+1 = n i ) = 2 −i for every positive integer i. Let Y n = max{X 1 , . . . , X n }. Show that n X 2 i E[Y n ] = 2 i − 1 i=1 where E[Y n ] is the expected value of Y n .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Jan Kuś and Jun Yan, University of Warwick)

Solution 1. For each j∈[n]={1,2,…,n}j \in [n] = \{1, 2, \ldots, n\}, let Yj=max⁡{X1,…,Xj}Y_j = \max\{X_1, \ldots, X_j\}. We use induction on jj to show that

E[Yj]=∑i=1j2i2i−1for all j∈[n].\mathbb{E}[Y_j] = \sum_{i=1}^{j} \frac{2^i}{2^i - 1} \quad \text{for all } j \in [n].
The base case j=1j = 1 follows easily from definition.

For the inductive step, it suffices to show that E[Yj+1−Yj]=2j+12j+1−1\mathbb{E}[Y_{j+1} - Y_j] = \frac{2^{j+1}}{2^{j+1} - 1} for every j∈[n−1]j \in [n-1]. Note that Yj+1≠YjY_{j+1} \ne Y_j if and only if Xj+1>Yj=max⁡{X1,…,Xj}X_{j+1} > Y_j = \max\{X_1, \ldots, X_j\}, in which case Yj+1=Xj+1Y_{j+1} = X_{j+1}. Thus,

E[Yj+1−Yj]=P[Xj+1>Yj]⋅E[Xj+1−Yj∣Xj+1>Yj].\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 P[Xj+1>Yj]\mathbb{P}[X_{j+1} > Y_j], note that for any fixed pairwise distinct positive integers a1,…,aja_1, \ldots, a_j and a>max⁡{a1,…,aj}a > \max\{a_1, \ldots, a_j\},

P[(X1,…,Xj+1)=(a,a1,…,aj)]=P[(X1,…,Xj+1)=(a1,a,…,aj)]/2=P[(X1,…,Xj+1)=(a1,a2,a,…,aj)]/4=⋯=P[(X1,…,Xj+1)=(a1,…,aj,a)]/2j.\begin{aligned} \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{aligned}
Therefore, summing over all possible a1,…,aja_1, \ldots, a_j and a>max⁡{a1,…,aj}a > \max\{a_1, \ldots, a_j\}, we see that
P[Xj+1>Yj]=2j∑i=0j2i=2j2j+1−1.\mathbb{P}[X_{j+1} > Y_j] = \frac{2^j}{\sum_{i=0}^{j} 2^i} = \frac{2^j}{2^{j+1} - 1}.

To finish, it is easy to see that

E[Xj+1−Yj∣Xj+1>Yj]=∑t=1∞t⋅P[Xj+1=Yj+t∣Xj+1>Yj]=∑t=1∞t2t=2.\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 YnY_n takes values in Z>0\mathbb{Z}_{>0},

E[Yn]=∑k=1∞P[Yn≥k].\mathbb{E}[Y_n] = \sum_{k=1}^{\infty} \mathbb{P}[Y_n \ge k].
For each k∈[n]k \in [n], P[Yn≥k]=1\mathbb{P}[Y_n \ge k] = 1, while for each k>nk > n,
P[Yn≥k]=1−P[Yn<k]=1−P[X1,…,Xn<k]=1−∏i=1n(1−12k−i).\mathbb{P}[Y_n \ge k] = 1 - \mathbb{P}[Y_n < k] = 1 - \mathbb{P}[X_1, \ldots, X_n < k] = 1 - \prod_{i=1}^{n}\left(1 - \frac{1}{2^{k-i}}\right).
Note that this formula also works for every k∈[n]k \in [n], as the i=ki = k term in the product is 00. Thus, it suffices to show that
∑i=1n2i2i−1=∑k=1∞(1−∏i=1n(1−12k−i)).\sum_{i=1}^{n} \frac{2^i}{2^i - 1} = \sum_{k=1}^{\infty}\left(1 - \prod_{i=1}^{n}\left(1 - \frac{1}{2^{k-i}}\right)\right).
The case of n=1n = 1 is easy to verify. Using induction on nn, it suffices to show that for every n≥2n \ge 2,
11−12n=∑k=1∞(∏i=1n−1(1−12k−i)−∏i=1n(1−12k−i))=∑k=1∞(12k−n∏i=1n−1(1−12k−i)).\frac{1}{1 - \frac{1}{2^n}} = \sum_{k=1}^{\infty}\left(\prod_{i=1}^{n-1}\left(1 - \frac{1}{2^{k-i}}\right) - \prod_{i=1}^{n}\left(1 - \frac{1}{2^{k-i}}\right)\right) = \sum_{k=1}^{\infty}\left(\frac{1}{2^{k-n}}\prod_{i=1}^{n-1}\left(1 - \frac{1}{2^{k-i}}\right)\right).
Indeed, for every N>nN > n, after multiplying by 1−12n1 - \frac{1}{2^n}, the sum on the right telescopes as
(1−12n)∑k=1N(12k−n∏i=1n−1(1−12k−i))=∑k=1N((12k−n−12k)∏i=1n−1(1−12k−i))==∑k=1N(∏i=1n(1−12k+1−i)−∏i=1n(1−12k−i))=∏i=1n(1−12N+1−i).\begin{aligned} \left(1 - \frac{1}{2^n}\right)\sum_{k=1}^{N}\left(\frac{1}{2^{k-n}}\prod_{i=1}^{n-1}\left(1 - \frac{1}{2^{k-i}}\right)\right) &= \sum_{k=1}^{N}\left(\left(\frac{1}{2^{k-n}} - \frac{1}{2^k}\right)\prod_{i=1}^{n-1}\left(1 - \frac{1}{2^{k-i}}\right)\right) = \\ = \sum_{k=1}^{N}\left(\prod_{i=1}^{n}\left(1 - \frac{1}{2^{k+1-i}}\right) - \prod_{i=1}^{n}\left(1 - \frac{1}{2^{k-i}}\right)\right) &= \prod_{i=1}^{n}\left(1 - \frac{1}{2^{N+1-i}}\right). \end{aligned}
Taking NN to infinity finishes the proof.

Solution 3 (sketch). It can be shown by induction or another method that for any sequence of positive integers a1<a2<⋯<ana_1 < a_2 < \cdots < a_n,

P[{X1,…,Xn}={a1,…,an}]=2−∑i=1nai∏i=1n(2i−1).\mathbb{P}[\{X_1, \ldots, X_n\} = \{a_1, \ldots, a_n\}] = 2^{-\sum_{i=1}^{n} a_i}\prod_{i=1}^{n}(2^i - 1).
For any a1<a2<⋯<ana_1 < a_2 < \cdots < a_n, let d1=a1d_1 = a_1 and di+1=ai+1−aid_{i+1} = a_{i+1} - a_i for i∈[n−1]i \in [n-1], so
P[{X1,…,Xn}={d1,d1+d2,…,d1+⋯+dn}]=2−∑i=1n(n+1−i)di∏i=1n(2i−1).\mathbb{P}[\{X_1, \ldots, X_n\} = \{d_1, d_1 + d_2, \ldots, d_1 + \cdots + d_n\}] = 2^{-\sum_{i=1}^{n}(n+1-i)d_i}\prod_{i=1}^{n}(2^i - 1).
Note that (a1,…,an)↦(d1,…,dn)(a_1, \ldots, a_n) \mapsto (d_1, \ldots, d_n) is a bijection between strictly increasing sequences in Z>0\mathbb{Z}_{>0} of length nn and (Z>0)n(\mathbb{Z}_{>0})^n, so, using ∑i≥1xi=x/(1−x)\sum\limits_{i\ge1} x^i = x/(1-x) and ∑i≥1ixi=x/(1−x)2\sum\limits_{i\ge1} ix^i = x/(1-x)^2, we get
E[Yn]=∏i=1n(2i−1)∑d1,…,dn≥1(∑i=1ndi)2−∑j=1n(n+1−j)dj=∏i=1n(2i−1)∑i=1n(∑di≥1di2−(n+1−i)di)∏j≠i(∑dj≥12−(n+1−j)dj)=⋯=∑i=1n2i2i−1.\begin{aligned} \mathbb{E}[Y_n] &= \prod_{i=1}^{n}(2^i - 1)\sum_{d_1,\ldots,d_n\ge1}\left(\sum_{i=1}^{n} d_i\right)2^{-\sum_{j=1}^{n}(n+1-j)d_j} \\ &= \prod_{i=1}^{n}(2^i - 1)\sum_{i=1}^{n}\left(\sum_{d_i\ge1} d_i 2^{-(n+1-i)d_i}\right)\prod_{j\ne i}\left(\sum_{d_j\ge1} 2^{-(n+1-j)d_j}\right) = \cdots = \sum_{i=1}^{n} \frac{2^i}{2^i - 1}. \end{aligned}

Transcribed from the official solutions, pages 4–6. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?