= Growth rate of two-column sticky deposition
{title2=$H_n/n\longrightarrow2/3\quad\text{almost surely}$}
Suppose each new unit block independently selects one of two columns with equal probability. On the taller column it increases the maximum height; on the shorter column it sticks level with the other column, leaving the maximum unchanged. If the columns have equal height, the next block increases the maximum. Their absolute height difference $D_n$ is the <reset-or-increment Markov chain> with $p=1/2$.
For the maximum height $H_n$, each increment obeys $H_n-H_{n-1}=\mathbf1_{\{D_n>0\}}$. The <stationary distribution> has $\pi_0=1/3$. Applying the <countable-state Markov chain ergodic theorem> to the bounded <indicator function> of the positive states gives
$$
\frac{H_n}{n}=\frac{H_0}{n}+\frac1n\sum_{m=1}^n\mathbf1_{\{D_m>0\}}\longrightarrow1-\pi_0=\frac23
$$
<almost surely>, from any fixed finite starting configuration. The reward average depends only on whether a reset occurred, even though the difference chain has infinitely many states.
\Image[/past-exam-of-the-probability-course-of-the-university-of-oxford/2017-sticky-column-markov-chain.png]
{title=Reset-or-increment differences determine the long-run column growth rate}
{description=Original calculations and simulations. The accompanying proof establishes the limiting result; finitely many simulated paths illustrate it.}
Back to article page
