Past exam of the mathematics course of the University of Cambridge / 2007 / ib / Paper 4 / 9C (Markov Chains)

For a time-homogeneous Markov chain with transition matrix $P$, two states are communicating states when each can be reached from the other with positive probability in finitely many steps:The convention $P^0=I$ includes communication of a state with itself.

Let $T_i^{+}=\inf \{n\ge 1:X_n=i\}$ be the first positive return time. A recurrent state is one for whichThe subscript means that the Markov chain starts at $i$. The positive-time condition distinguishes a genuine return from the automatic visit at time zero.

Communication is reflexive because $(P^0{)}_{ii}=1$, and symmetric by its definition. If $i\leftrightarrow j$ and $j\leftrightarrow k$, choose positive-probability paths $i\to j$ in $m$ steps and $j\to k$ in $n$ steps. The Chapman-Kolmogorov equation givesCombining the reverse paths gives a positive-probability path $k\to i$ as well. Thus communication is transitive and is an equivalence relation.

To transfer recurrence, first establish the recurrence criterion by return probabilities. Put $r_i={\mathbb{P}}_i(T_i^{+}<\infty )$ and let $N_i={\sum }_{n\ge 0}{1}_{\{X_n=i\}}$ under ${\mathbb{P}}_i$. After each return the Strong Markov property restarts the chain at $i$, so ${\mathbb{P}}_i(N_i\ge k+1)=r_i^k$. ThereforeFor $r_i<1$ this equals $(1-r_i{)}^{-1}$; for $r_i=1$ it is infinite. The expectation identity follows by summing the nonnegative indicators, so remains valid when the expectation is infinite. Consequently $i$ is a recurrent state exactly when its return-probability series diverges.

If $i\leftrightarrow j$, choose $a,b$ with $(P^a{)}_{ji}>0$ and $(P^b{)}_{ij}>0$. For every $n\ge 0$,Summing over $n$, recurrence of $i$ forces the return-probability series for $j$ to diverge. The proved criterion shows $j$ is recurrent, so recurrence is a property of the communicating class.