Past exam of the mathematics course of the University of Cambridge / 2013 / ib / Paper 2 / 20H (Markov Chains)

Let $T_j=\inf \{n\ge 1:X_n=j\}$. By the Strong Markov property, the probability of hitting $j$ and subsequently returning to $i$ is $f_{ij}{f}_{ji}$. This event implies a return to $i$, so $f_{ii}\ge f_{ij}{f}_{ji}$. For $i=j$, interpret the event as two successive returns.

Set $T_i^{(0)}=0$ and let $T_i^{(r)}$ be the $r$th successive return. Repeated use of the Strong Markov property gives ${\mathbb{P}}_i(T_i^{(r)}<\infty )=f_{ii}^r$. The total number $N_i$ of visits, including time zero, is both ${\sum }_{n\ge 0}{1}_{\{X_n=i\}}$ and ${\sum }_{r\ge 0}{1}_{\{T_i^{(r)}<\infty \}}$. By Tonelli theorem,The identity is valid with value $+\infty$. In particular, divergence of the return-probability sum is equivalent to Markov-chain recurrence.

For a planar simple symmetric random walk write its coordinates as $(S_n,T_n)$ and rotate to $(S_n+T_n,S_n-T_n)$. Each step now has four equally likely values $(1,1),(1,-1),(-1,1),(-1,-1)$. Thus the two rotated coordinates are independent one-dimensional simple symmetric random walks.

A return is impossible at odd times, and at time $2n$ its probability isFor $n\ge 2$, the supplied estimate gives $1/(4n)<p_{2n}(0,0)<1/n$. At $n=1$ the lower bound is actually equality, $p_2(0,0)=1/4$; this harmless strict-endpoint typo does not affect the argument. The harmonic series diverges, so the criterion proved above shows that the origin is recurrent, in the terminology of a recurrent Markov chain. Translation invariance gives the same conclusion for every state. The Markov chain is irreducible, so from any starting point it hits any fixed state almost surely and revisits it infinitely often. One can see the hitting assertion directly: repeated returns to the starting point give repeated positive-probability opportunities to follow a finite path to the target.

For an active monster, independence givesBoth probabilities vanish before time $100$ and at odd times. By convolution and Cauchy-Schwarz, $p_{2m}(a,0)\le p_{2m}(0,0)<1/m$: indeed, write the $2m$-step probability as the inner product of two translates of the $m$-step probability mass function. ThereforePositivity follows by prescribing $100$ simultaneous steps taking both walkers straight to the origin; that event has probability $4^{-200}$. An active monster thus leaves a positive escape probability.

For a sleepy monster, the origin capture by a sufficiently sleepy planar random walk can be proved using the printed schedule: during $I_j=\{n_j+1,\dots ,n_{j+1}\}$ it occupies $Y_{j+1}$. For any $M$, let $J_M$ be the first $j\ge M$ with $Y_{j+1}=0$. Markov-chain recurrence of $Y$ makes $J_M$ finite almost surely, and it is independent of $X$. By conditioning on $J_M$ and using the stated block bound,As $M\to \infty$, continuity of probability for decreasing events shows that the event $C_{\infty }$ of infinitely many simultaneous origin visits has probability at least $1/2$. Regard the independent trajectories as continuing even after a possible first capture.

To turn this into probability one, use the eventual coupling of planar symmetric random walks; the block events need not be independent. Two planar simple symmetric random walks begun at sites of the same parity can be coupled to agree eventually. Run them independently until they meet. Their difference walk is irreducible on the even-parity sublattice, and its $m$-step return probability is $p_{2m}(0,0)$, by convolution and symmetry. The preceding divergent-series criterion makes this difference walk a recurrent Markov chain, so it hits zero almost surely. After that stopping time, use identical increments for both copies, preserving their marginal laws by the Strong Markov property.

Fix any finite calendar time $N$ and any two possible histories up to that time. Corresponding princess positions have the same parity, as do the corresponding monster positions at its internal walk time. Apply the eventual probabilistic coupling separately to the two princess futures and the two monster futures, keeping the princess and monster walks independent in each pair. Both the calendar clock and the monster's internal clock tend to infinity. Hence after a finite calendar time the two pairs of trajectories agree, so either both realize $C_{\infty }$ or neither does. The conditional probability of $C_{\infty }$ is therefore the same for every possible finite history.

Consequently $\mathbb{E}(1_{C_{\infty }}\mid {\mathcal{F}}_N)=\mathbb{P}(C_{\infty })$ for every $N$. By the Martingale convergence theorem, these conditional expectations converge to $1_{C_{\infty }}$ as the histories exhaust the trajectories. Thus $\mathbb{P}(C_{\infty })$ is zero or one. Since it is at least $1/2$, it is one. In particular,This argument uses the supplied unconditional block probabilities; it does not silently strengthen them to conditional probabilities given past failures.