| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
46 |
|
Paper 2, Section II, H |
2013 |
(i) Suppose $\left(X_{n}\right){n \geqslant 0}$ is an irreducible Markov chain and $f{i j}=P\left(X_{n}=j\right.$ for some $\left.n \geqslant 1 \mid X_{0}=i\right)$. Prove that $f_{i i} \geqslant f_{i j} f_{j i}$ and that
$$\sum_{n=0}^{\infty} P_{i}\left(X_{n}=i\right)=\sum_{n=1}^{\infty} f_{i i}^{n-1}$$
(ii) Let $\left(X_{n}\right){n \geqslant 0}$ be a symmetric random walk on the $\mathbb{Z}^{2}$ lattice. Prove that $\left(X{n}\right)_{n \geqslant 0}$ is recurrent. You may assume, for $n \geqslant 1$,
$$1 / 2<2^{-2 n} \sqrt{n}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)<1$$
(iii) A princess and monster perform independent random walks on the $\mathbb{Z}^{2}$ lattice. The trajectory of the princess is the symmetric random walk $\left(X_{n}\right){n \geqslant 0}$. The monster's trajectory, denoted $\left(Z{n}\right){n \geqslant 0}$, is a sleepy version of an independent symmetric random walk $\left(Y{n}\right){n \geqslant 0}$. Specifically, given an infinite sequence of integers $0=n{0}<n_{1}<\cdots$, the monster sleeps between these times, so $Z_{n_{i}+1}=\cdots=Z_{n_{i+1}}=Y_{i+1}$. Initially, $X_{0}=(100,0)$ and $Z_{0}=Y_{0}=(0,100)$. The princess is captured if and only if at some future time she and the monster are simultaneously at $(0,0)$.
Compare the capture probabilities for an active monster, who takes $n_{i+1}=n_{i}+1$ for all $i$, and a sleepy monster, who takes $n_{i}$ spaced sufficiently widely so that
$$P\left(X_{k}=(0,0) \text { for some } k \in\left{n_{i}+1, \ldots, n_{i+1}\right}\right)>1 / 2$$