IMC 2025 · Day 2 · P9

For each $j \in [n] = \{1, 2, \dots, n\}$, let $Y_j = \max\{X_1, \dots, X_j\}$. We use induction on $j$ to show that $$\mathsf{E}[Y_j] = \sum_{i=1}^{j} \frac{2^i}{2^i - 1} \quad \text{for all } j \in [n].$$ The base case $j = 1$ follows easily from definition.

For the inductive step, it suffices to show that $\mathsf{E}[Y_{j+1} - Y_j] = \frac{2^{j+1}}{2^{j+1} - 1}$ for every $j \in [n-1]$. Note that $Y_{j+1} \ne Y_j$ if and only if $X_{j+1} > Y_j = \max\{X_1, \dots, X_j\}$, in which case $Y_{j+1} = X_{j+1}$. Thus, $$\mathsf{E}[Y_{j+1} - Y_j] = \mathsf{P}[X_{j+1} > Y_j] \cdot \mathsf{E}[X_{j+1} - Y_j \mid X_{j+1} > Y_j].$$ To compute $\mathsf{P}[X_{j+1} > Y_j]$, note that for any fixed pairwise distinct positive integers $a_1, \dots, a_j$ and $a > \max\{a_1, \dots, a_j\}$, $$\begin{align*} \mathsf{P}[(X_1, \dots, X_{j+1}) = (a, a_1, \dots, a_j)] &= \mathsf{P}[(X_1, \dots, X_{j+1}) = (a_1, a, \dots, a_j)] / 2 \\ &= \mathsf{P}[(X_1, \dots, X_{j+1}) = (a_1, a_2, a, \dots, a_j)] / 4 \\ &= \dots = \mathsf{P}[(X_1, \dots, X_{j+1}) = (a_1, \dots, a_j, a)] / 2^j. \end{align*}$$ Therefore, summing over all possible $a_1, \dots, a_j$ and $a > \max\{a_1, \dots, a_j\}$, we see that $$\mathsf{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 $$\mathsf{E}[X_{j+1} - Y_j \mid X_{j+1} > Y_j] = \sum_{t=1}^{\infty} t \cdot \mathsf{P}[X_{j+1} = Y_j + t \mid X_{j+1} > Y_j] = \sum_{t=1}^{\infty} \frac{t}{2^t} = 2.$$

Since $Y_n$ takes values in $\mathbb{Z}_{>0}$, $$\mathsf{E}[Y_n] = \sum_{k=1}^{\infty} \mathsf{P}[Y_n \ge k].$$ For each $k \in [n]$, $\mathsf{P}[Y_n \ge k] = 1$, while for each $k > n$, $$\mathsf{P}[Y_n \ge k] = 1 - \mathsf{P}[Y_n < k] = 1 - \mathsf{P}[X_1, \dots, 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 \in [n]$, as the $i = k$ term in the product is 0. Thus, it suffices to show that $$\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 = 1$ is easy to verify. Using induction on $n$, it suffices to show that for every $n \ge 2$, $$\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} \frac{1}{2^{k-n}} \prod_{i=1}^{n-1} \left( 1 - \frac{1}{2^{k-i}} \right).$$ Indeed, for every $N > n$, after multiplying by $1 - \frac{1}{2^n}$, the sum on the right telescopes as $$\begin{align*} \left( 1 - \frac{1}{2^n} \right) \sum_{k=1}^{N} \frac{1}{2^{k-n}} \prod_{i=1}^{n-1} \left( 1 - \frac{1}{2^{k-i}} \right) &= \sum_{k=1}^{N} \left( \frac{1}{2^{k-n}} - \frac{1}{2^k} \right) \prod_{i=1}^{n-1} \left( 1 - \frac{1}{2^{k-i}} \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{align*}$$ Taking $N$ to infinity finishes the proof.

(sketch) It can be shown by induction or another method that for any sequence of positive integers $a_1 < a_2 < \dots < a_n$, $$\mathsf{P}[\{X_1, \dots, X_n\} = \{a_1, \dots, a_n\}] = 2^{-\sum_{i=1}^{n} a_i} \prod_{i=1}^{n} (2^i - 1).$$ For any $a_1 < a_2 < \dots < a_n$, let $d_1 = a_1$ and $d_{i+1} = a_{i+1} - a_i$ for $i \in [n-1]$, so $$\mathsf{P}[\{X_1, \dots, X_n\} = \{d_1, d_1 + d_2, \dots, d_1 + \dots + d_n\}] = 2^{-\sum_{i=1}^{n} (n+1-i) d_i} \prod_{i=1}^{n} (2^i - 1).$$ Note that $(a_1, \dots, a_n) \mapsto (d_1, \dots, d_n)$ is a bijection between strictly increasing sequences in $\mathbb{Z}_{>0}$ of length $n$ and $(\mathbb{Z}_{>0})^n$, so, using $\sum_{i \ge 1} x^i = x / (1 - x)$ and $\sum_{i \ge 1} i x^i = x / (1 - x)^2$, we get $$\begin{align*} \mathsf{E}[Y_n] &= \prod_{i=1}^{n} (2^i - 1) \sum_{d_1, \dots, d_n \ge 1} \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 \ge 1} d_i 2^{-(n+1-i) d_i} \right) \prod_{j \ne i} \left( \sum_{d_j \ge 1} 2^{-(n+1-j) d_j} \right) = \dots = \sum_{i=1}^{n} \frac{2^i}{2^i - 1}. \end{align*}$$