Putnam 2024, Problem B-4

Let \( n \) be a positive integer. Set \( a_{n,0} = 1 \). For \( k \geq 0 \), choose an integer \( m_{n,k} \) uniformly at random from the set \( \{1, \ldots, n\} \), and let
\[ a_{n,k+1} = \begin{cases} 
a_{n,k} + 1, & \text{if } m_{n,k} > a_{n,k}; \\
a_{n,k}, & \text{if } m_{n,k} = a_{n,k}; \\
a_{n,k} - 1, & \text{if } m_{n,k} < a_{n,k}.
\end{cases} \]
Let \( E(n) \) be the expected value of \( a_{n,n} \). Determine \( \lim_{n \to \infty} E(n)/n \).

Solution:
The limit equals $\frac{1-e^{-2}}{2}$.

**First solution.** We first reformulate the problem as a Markov chain. Let $v_k$ be the column vector of length $n$ whose $i$-th entry is the probability that $a_{n,k} = i$, so that $v_0$ is the vector $(1,0,\ldots,0)$. Then for all $k \geq 0$, $v_{k+1} = Av_k$ where $A$ is the $n \times n$ matrix defined by
$$A_{ij} = \begin{cases} 
\frac{1}{n} & \text{if } i = j \\
\frac{j-1}{n} & \text{if } i = j-1 \\
\frac{n-j}{n} & \text{if } i = j+1 \\
0 & \text{otherwise.}
\end{cases}$$

Let $w$ be the row vector $(1,\ldots,n)$; then the expected value of $a_{n,k}$ is the sole entry of the $1 \times 1$ matrix $wv_k = wA^k v_0$. In particular, $E(n) = wA^n v_0$.

We compute some left eigenvectors of $A$. First,
$$w_0 := (1,\ldots,1)$$
satisfies $Aw_0 = w_0$. Second,
$$w_1 := (n-1,n-3,\ldots,3-n,1-n) = (n-2j+1 : j = 1,\ldots,n)$$
satisfies $Aw_1 = \frac{n-2}{n}w_1$: the $j$-th entry of $Aw_i$ equals
$$\frac{j-1}{n}(n+3-2j) + \frac{1}{n}(n+1-2j) + \frac{n-j}{n}(n-1-2j) = \frac{n-2}{n}(n-2j+1).$$

By the same token, we obtain
$$w = \frac{n+1}{2}w_0 - \frac{1}{2}w_1;$$
we then have
$$\frac{E(n)}{n} = \frac{n+1}{2n}w_0 A^n v_0 - \frac{1}{2n}w_1 A^n v_0$$
$$= \frac{n+1}{2n}w_0 v_0 - \frac{1}{2n}\left(1 - \frac{2}{n}\right)^n w_1 v_0$$
$$= \frac{n+1}{2n} - \frac{n-1}{2n}\left(1 - \frac{2}{n}\right)^n.$$

In the limit, we obtain
$$\lim_{n \to \infty} \frac{E(n)}{n} = \frac{1}{2} - \frac{1}{2} \lim_{n \to \infty} \left(1 - \frac{2}{n}\right)^n = \frac{1}{2} - \frac{1}{2}e^{-2}.$$

**Remark.** With a bit more work, one can show that $A$ has eigenvalues $\frac{n-2j}{n}$ for $j = 0,\ldots,n-1$, and find the corresponding left and right eigenvectors. In particular, it is also possible (but much more complicated) to express $v_0$ as a linear combination of right eigenvectors and use this to calculate $A^n v_0$.

**Second solution.** We reinterpret the Markov chain in combinatorial terms. Consider an apparatus consisting of one red light bulb, which is initially lit, plus $n-1$ white light bulbs, which are initially unlit. We then repeatedly perform the following operation. Pick one light bulb uniformly at random. If it is the red bulb, do nothing; otherwise, switch the bulb from lit to unlit or vice versa. After $k$ operations of this form, the random variable $a_{n,k}$ is equal to the number of lit bulbs (including the red bulb).

We may then compute the expected value of $a_{n,k}$ by summing over bulbs. The red bulb contributes $1$ no matter what. Each other bulb contributes $1$ if it is switched an odd number of times and $0$ if it is switched an even number of times, or equivalently $\frac{1}{2}(1 - (-1)^j)$ where $j$ is the number of times this bulb is switched. Hence each bulb other than the red bulb contributes
$$n^{-n} \sum_{i=0}^{n} \frac{1}{2}(1 - (-1)^i) \binom{n}{i} (n-1)^{n-i}$$
$$= \frac{n^{-n}}{2} \left( \sum_{i=0}^{n} \binom{n}{i} (n-1)^{n-i} - \sum_{i=0}^{n} (-1)^i \binom{n}{i} (n-1)^{n-i} \right)$$
$$= \frac{n^{-n}}{2} \left( ((1 + (n-1))^n - (-1 + (n-1))^n \right)$$
$$= \frac{n^{-n}}{2} (n^2 - (n-2)^n)$$
$$= \frac{1}{2} - \frac{1}{2}\left(1 - \frac{2}{n}\right)^n.$$

This tends to $\frac{1-e^{-2}}{2}$ as $n \to \infty$. Since $E(n)$ equals $n-1$ times this contribution plus $1$, $\frac{E(n)}{n}$ tends to the same limit.

**Third solution.** We compare the effect of taking $a_{n,0} = j$ versus $a_{n,0} = j+1$ for some $j \in \{1,\ldots,n-1\}$. If $m_{n,0} \in \{j,j+1\}$ then the values of $a_{n,1}$ coincide, as then do the subsequent values of $a_{n,k}$; this occurs with probability $\frac{2}{n}$. Otherwise, the values of $a_{n,1}$ differ by $1$ and the situation repeats.

Iterating, we see that the two sequences remain $1$ apart (in the same direction) with probability $\left(\frac{n-2}{n}\right)^n$ and converge otherwise. Consequently, changing the start value from $j$ to $j+1$ increases the expected value of $a_{n,n}$ by $\left(\frac{n-2}{n}\right)^n$.

Now let $c$ be the expected value of $a_{n,n}$ in the original setting where $a_{n,0} = 1$. By symmetry, if we started with $a_{n,0} = n$ the expected value would change from $c$ to $n+1-c$; on the other hand, by the previous paragraph it would increase by $(n-1)\left(\frac{n-2}{n}\right)^n$. We deduce that
$$c = \frac{1}{2}\left(n+1 - (n-1)\left(\frac{n-2}{n}\right)^n\right)$$
and as above this yields the claimed limit.