91Ó°ÊÓ

Strong law for additive functionals. Suppose \(p\) is irreducible and has stationary distribution \(\pi .\) Let \(f\) be a function that has \(\sum|f(y)| \pi(y)<\infty\). Let \(T_{x}^{k}\) be the time of the \(k\) th return to \(x\). (i) Show that $$ V_{k}^{f}=f\left(X\left(T_{x}^{k}\right)\right)+\cdots+f\left(X\left(T_{x}^{k+1}-1\right)\right), \quad k \geq 1 \text { are i.i.d. } $$ with \(E\left|V_{k}^{f}\right|<\infty\). (ii) Let \(K_{n}=\inf \left\\{k: T_{x}^{k} \geq n\right\\}\) and show that $$ \frac{1}{n} \sum_{m=1}^{K_{n}} V_{m}^{f} \rightarrow \frac{E V_{1}^{f}}{E_{x} T_{x}^{1}}=\sum f(y) \pi(y) \quad P_{\mu}-\text { a.s } $$ (iii) Show that \(\max _{1 \leq m \leq n} V_{m}^{|f|} / n \rightarrow 0\) and conclude $$ \frac{1}{n} \sum_{m=1}^{n} f\left(X_{m}\right) \rightarrow \sum_{y} f(y) \pi(y) \quad P_{\mu}-\text { a.s. } $$ for any initial distribution \(\mu\).

Let \(X_{n}\) be a Markov chain with \(S=\\{0,1, \ldots, N\\}\) and suppose that \(X_{n}\) is a martingale and \(P_{x}\left(\tau_{0} \wedge \tau_{N}<\infty\right)>0\) for all \(x\). (i) Show that 0 and \(N\) are absorbing states, i.e., \(p(0,0)=p(N, N)=1 .\) (ii) Show \(P_{x}\left(\tau_{N}<\tau_{0}\right)=x / N\).

Suppose \(p\) is irreducible and positive recurrent. Then \(E_{x} T_{y}<\infty\) for all \(x, y\).

Compute the expected number of moves it takes a knight to return to its initial position if it starts in a corner of the chessboard, assuming there are no other pieces on the board, and each time it chooses a move at random from its legal moves. (Note: A chessboard is \(\\{0,1, \ldots, 7\\}^{2}\). A knight's move is \(L\)-shaped; two steps in one direction followed by one step in a perpendicular direction.)

For any transition matrix \(p\), define $$ \alpha_{n}=\sup _{i, j} \frac{1}{2} \sum_{k}\left|p^{n}(i, k)-p^{n}(j, k)\right| $$ The \(1 / 2\) is there because for any \(i\) and \(j\) we can define r.v.'s \(X\) and \(Y\) so that \(P(X=k)=p^{n}(i, k), P(Y=k)=p^{n}(j, k)\), and $$ P(X \neq Y)=(1 / 2) \sum_{k}\left|p^{n}(i, k)-p^{n}(j, k)\right| $$ Show that \(\alpha_{m+n} \leq \alpha_{n} \alpha_{m} .\) Here you may find the coupling interpretation may help you from getting lost in the algebra. Remark. Using \((9.1)\) in Chapter 1 , we can conclude that $$ \frac{1}{n} \log \alpha_{n} \rightarrow \inf _{m \geq 1} \frac{1}{m} \log \alpha_{m} $$ so if \(\alpha_{m}<1\) for some \(m\), it approaches 0 exponentially fast.