 Solution

ID: past-exam-of-the-probability-course-of-the-university-of-oxford/2017/3/b/ii/solution

The precise conclusion is

P (n \to \infty lim \frac{H _{n}}{n} = \frac{2}{3}) = 1.

To prove it, observe that the maximum rises exactly when the new height difference is positive:

H_{m} - H_{m - 1} = 1_{{D_{m} > 0}} .

A block landing in a shorter column produces

D_{m} = 0

and no rise; every other case raises the maximum and leaves

D_{m} > 0

. Starting from

H_{0} = 0

, telescoping gives

\frac{H _{n}}{n} = \frac{1}{n} \sum_{m = 1}^{n} 1_{{D_{m} > 0}} .

The difference chain is irreducible and positive recurrent by part (i). Apply the countable-state Markov chain ergodic theorem to the bounded indicator function

g (k) = 1_{{k > 0}}

. Its stationary mean is

\sum_{k \geq 1} π_{k} = 1 - π_{0} = 2/3

 New to topics? Read the docs here!