Past exam of the probability course of the University of Oxford / 2017 / 3

A transition matrix $P$ defines an irreducible Markov chain if every state is accessible from every other state:Equivalently, all states belong to one communicating class. When $i\ne j$, a positive number of steps is necessarily used.

A stationary distribution is a nonnegative row vector $\pi =({\pi }_i{)}_{i\in S}$ with total mass one that is preserved by one transition:In matrix notation, $\pi P=\pi$. If the initial state has distribution $\pi$, so does the state at each later time.

For an irreducible Markov chain on a countable state space, the set has either zero or one element. By uniqueness of stationary distributions for an irreducible countable chain, a stationary probability distribution exists exactly in the positive recurrent case, and thenfor the first return time $T_i^{+}$. The right-hand side fixes every entry, proving uniqueness.

For a finite state space, existence is guaranteed, so there is exactly one. A countably infinite state space can have none: the simple symmetric random walk on the integers is irreducible and null recurrent. Periodicity does not affect this existence-and-uniqueness statement.

The difference process $D_n$ is a Markov chain. If the columns are equal, the next block creates a height difference of one. If the difference is $k\ge 1$, landing in the taller column increases it to $k+1$, while landing in the shorter column makes it zero. Therefore its only nonzero transition probabilities areThese probabilities depend only on the present difference, not on the absolute heights or their history. This is the reset-or-increment Markov chain with $p=1/2$.

For its stationary distribution, the incoming-flow equations give ${\pi }_1={\pi }_0$ and ${\pi }_k={\pi }_{k-1}/2$ for $k\ge 2$. Normalization uses a geometric series:ThusThe remaining balance equation is also satisfied: the flow into zero is $(1-{\pi }_0)/2=1/3$. Every state can reach zero and every positive state can be reached from zero, so it is an irreducible Markov chain. Its invariant probability distribution makes it positive recurrent, and that distribution is unique.

The maximum-height process $H_n$ is not Markov. Starting empty, condition first on the positive-probability history $(H_1,H_2,H_3)=(1,1,2)$. After two blocks the columns were equal, so after three their difference is one. Hence $\mathbb{P}(H_4=3\mid H_1=1,H_2=1,H_3=2)=1/2$.

For the history $(1,2,2)$, the first two blocks built one column and the third caught the other column up, leaving equal heights. Hence $\mathbb{P}(H_4=3\mid H_1=1,H_2=2,H_3=2)=1$. Both histories have the same time and present height $H_3=2$, but different predictions. This violates the Markov property and illustrates why a function of a Markov chain need not be Markov.

The precise conclusion isTo prove it, observe that the maximum rises exactly when the new height difference is positive: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 givesThe 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\ge 1}{\pi }_k=1-{\pi }_0=2/3$, giving the asserted almost sure convergence. No aperiodicity assumption is needed for this time average. This establishes the growth rate of two-column sticky deposition.