Proof. Reflexive: \(P_{ii}^{(0)} = 1\), so \(i\leftrightarrow i\). Symmetric: the definition is symmetric in \(i\) and \(j\). Transitive: suppose \(P_{ij}^{(m)}>0\) and \(P_{jk}^{(n)}>0\). By theorem 3.2.1, \[P_{ik}^{(m + n)} = \sum _rP_{ir}^{(m)}P_{rk}^{(n)}\geq P_{ij}^{(m)}P_{jk}^{(n)}>0,\] keeping only the term \(r = j\) of a sum of non-negative terms. So \(i\to k\), and in the same way \(k\to i\). □

Solution.

(i)

\(0\to 1\to 2\) and \(2\to 1\to 0\), so all states communicate and the chain is irreducible, although \(P_{02} = 0\): a state need only be reachable in some number of steps.

(ii)

\(0\leftrightarrow 1\). State \(2\) leads to \(0\), \(1\) and \(3\), but nothing leads back to \(2\), and state \(3\) is absorbing. The classes are \(\{0, 1\}\), \(\{2\}\) and \(\{3\}\). The chain leaves \(\{2\}\) at the first step that it does not stay, and then remains in \(\{0, 1\}\) or in \(\{3\}\) for ever.

Proof. Each time the chain is at \(i\), by the Markov property and homogeneity it behaves afresh as a chain started at \(i\): it returns again with probability \(f_{ii}\) and never returns with probability \(1 - f_{ii}\). So the returns are a sequence of independent trials, and \(N_i\) counts the successes before the first failure. This gives (i) and, when \(f_{ii} = 1\), (ii). For (iii), let \(I_n = 1\) if \(X_n = i\) and \(0\) otherwise. Then \(N_i = \sum _{n\geq 1}I_n\) and \[E(N_i\mid X_0 = i) = \sum _{n=1}^\infty P(X_n = i\mid X_0 = i) = \sum _{n=1}^\infty P_{ii}^{(n)} .\] By (i) and (ii) this is finite exactly when \(i\) is transient. □

Proof. Choose \(k\) and \(m\) with \(P_{ji}^{(k)}>0\) and \(P_{ij}^{(m)}>0\). Going from \(j\) to \(i\) in \(k\) steps, returning to \(i\) in \(n\) steps and then going to \(j\) in \(m\) steps is one way of returning to \(j\) in \(k + n + m\) steps, so \[P_{jj}^{(k + n + m)}\geq P_{ji}^{(k)}P_{ii}^{(n)}P_{ij}^{(m)} .\] Summing over \(n\), \(\sum _nP_{jj}^{(k + n + m)}\geq P_{ji}^{(k)}P_{ij}^{(m)}\sum _nP_{ii}^{(n)} = \infty \), and \(j\) is recurrent by theorem 3.4.5(iii). □

Proof. Suppose the states are \(0, 1, \dots , M\) and all are transient. By theorem 3.4.5 each state is visited only finitely many times, so after some finite time \(T_0\) state \(0\) is never visited, after \(T_1\) state \(1\) is never visited, and so on. After time \(\max (T_0, \dots , T_M)\) the chain is in no state at all, which is impossible. □

Solution. The classes are \(\{0, 1\}\) and \(\{4, 5\}\), each closed (no transitions out), and \(\{2, 3\}\), from which the chain can leave and never come back. The two closed classes are finite and irreducible, so their states are recurrent by theorem 3.4.7; states \(2\) and \(3\) are transient.

Let \(f_{11}^{(n)}\) be the probability that the first return to \(1\) happens at step \(n\). Staying put gives \(f_{11}^{(1)} = \frac 34\). For \(n\geq 2\) the chain must go to \(0\), stay there for \(n - 2\) steps and then come back: \(f_{11}^{(n)} = \frac 14\left (\frac 12\right )^{n - 2}\frac 12 = \frac 14\left (\frac 12\right )^{n - 1}\). So \[f_{11} = \frac 34 + \frac 14\sum _{n=2}^\infty \left (\frac 12\right )^{n - 1} = \frac 34 + \frac 14 = 1,\] confirming that state \(1\) is recurrent. The mean recurrence time is \[\mu _1 = \sum _{n=1}^\infty nf_{11}^{(n)} = \frac 34 + \frac 14\sum _{n=2}^\infty n\left (\frac 12\right )^{n - 1} = \frac 34 + \frac 14\left (\frac {1}{(1 - \frac 12)^2} - 1\right ) = \frac 34 + \frac 34 = \frac 32 .\] The limiting distribution of the class \(\{0, 1\}\), found by the method of section 3.6, is \(\left (\frac 13, \frac 23\right )\), and indeed \(\mu _1 = 1\big /\frac 23\).