Why Compare Expected Visits?
A Markov chain may have many states, and deciding separately whether each one is transient can seem to require a separate return-time calculation. Communication changes the problem: if there is a positive-probability path from \(i\) to \(j\) and another from \(j\) to \(i\), then repeated opportunities to visit one state constrain the expected number of visits to the other. We make that comparison using sums of transition probabilities, including when the state space is countably infinite.
Let \((X_n)_{n\ge 0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Its rows sum to \(1\), and \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)\). We use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) when conditioning on the chain's history. A path of length \(m\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_m=j\) whose transition probabilities have positive product \(\prod_{\ell=0}^{m-1}p_{i_\ell i_{\ell+1}}\). States communicate, written \(i\leftrightarrow j\), if each is reachable from the other by such a path.
For the diagonal entry, \(G_{ii}\) counts the visit at time \(0\) as well as every return. After each return, the Markov property gives the same probability \(f_i\) of making another return. Thus \(G_{ii}\) is finite exactly when \(i\) is transient.
Derivation of the diagonal identity. Let \(R\) be the number of returns to \(i\) after time \(0\), allowing \(R=\infty\). For every integer \(k\ge1\), the Markov property at successive return times gives \(\mathbb{P}_i(R\ge k)=f_i^k\): each additional return has probability \(f_i\), conditional on the preceding return. Since the total number of visits including time \(0\) is \(1+R\), the tail-sum formula gives $$ G_{ii}=1+\sum_{k=1}^{\infty}\mathbb{P}_i(R\ge k) =1+\sum_{k=1}^{\infty}f_i^k. $$ For \(f_i<1\), this geometric series is \(1/(1-f_i)\); for \(f_i=1\), its partial sums are unbounded. Therefore $$ G_{ii}=\frac{1}{1-f_i}\quad\text{if }f_i<1, \qquad G_{ii}=\infty\quad\text{if }f_i=1. $$ This also explains why expected visits, rather than a comparison of individual return-time probabilities, are useful here.
Comparing Visit Counts Along Paths
A path in one direction supplies a lower bound on a Green-series entry. A path in the reverse direction supplies a second bound, which is what makes communication decisive. The inequalities below use only the Markov property and nonnegativity of transition probabilities.
Proof. The chosen path from \(i\) to \(j\) ensures \(p_{ij}^{(m)}\ge\alpha\). By the Chapman–Kolmogorov equations, for every \(n\ge0\), $$ p_{ij}^{(m+n)} =\sum_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)} \ge p_{ij}^{(m)}p_{jj}^{(n)} \ge\alpha p_{jj}^{(n)}. $$ Summing over \(n\ge0\), the left side is a subseries of \(G_{ij}\), because its indices \(m+n\) are distinct and all terms are nonnegative. Hence \(\alpha G_{jj}\le G_{ij}\). For the reverse path, \(p_{ji}^{(r)}\ge\beta\). Applying Chapman–Kolmogorov after first being at \(j\) gives, for every \(n\ge0\), $$ p_{ii}^{(n+r)} \ge p_{ij}^{(n)}p_{ji}^{(r)} \ge\beta p_{ij}^{(n)}. $$ Summing again uses distinct indices on the left, now a subseries of \(G_{ii}\), and yields \(\beta G_{ij}\le G_{ii}\). Both arguments remain valid if a sum is infinite, since the terms are nonnegative. \(\square\)
Proof. If \(i=j\), the assertion is immediate. Otherwise choose a positive-probability path from \(i\) to \(j\) and one from \(j\) to \(i\), and let their probabilities be \(\alpha>0\) and \(\beta>0\). If \(i\) is transient, the diagonal identity gives \(G_{ii}<\infty\). The path comparison lemma implies $$ \alpha\beta G_{jj}\le\beta G_{ij}\le G_{ii}<\infty. $$ Since \(\alpha\beta>0\), it follows that \(G_{jj}<\infty\). The diagonal identity then gives \(f_j<1\), so \(j\) is transient. Interchanging \(i\) and \(j\) proves the converse: the same argument applies because communication provides positive-probability paths in both directions. Thus the two states have the same transience status. \(\square\)
Worked Comparisons
Worked Example: Two Transient States in a Three-State Chain
Consider \(S=\{0,1,2\}\), with state \(2\) absorbing and transition matrix $$ P= \begin{bmatrix} 0&\tfrac12&\tfrac12\\ \tfrac13&0&\tfrac23\\ 0&0&1 \end{bmatrix}. $$ The row sums are \(0+\tfrac12+\tfrac12=1\), \(\tfrac13+0+\tfrac23=1\), and \(0+0+1=1\). States \(0\) and \(1\) communicate: the one-step path \(0\to1\) has probability \(\tfrac12\), and \(1\to0\) has probability \(\tfrac13\).
First calculate \(G_{00}\). Starting at \(0\), a return to \(0\) requires the two transitions \(0\to1\to0\); their probability is \(\tfrac12\cdot\tfrac13=\tfrac16\). No other path returns to \(0\), because a transition to \(2\) stays there. Thus \(f_0=\tfrac16\), and the diagonal identity gives \(G_{00}=1/(1-\tfrac16)=\tfrac65\). For the path comparison, \(\alpha=\tfrac12\) and \(\beta=\tfrac13\), so $$ \tfrac12 G_{11}\le G_{01}, \qquad \tfrac13 G_{01}\le\tfrac65. $$ Together these give \(G_{11}\le 36/5\), which is finite and therefore already proves that state \(1\) is transient.
Check by direct calculation. The return path from \(1\) is \(1\to0\to1\), with probability \(\tfrac13\cdot\tfrac12=\tfrac16\). Therefore \(G_{11}=1/(1-\tfrac16)=\tfrac65\), consistent with the bound. To check the cross-entry, first-step equations for expected visits to \(1\) give \(G_{01}=\tfrac12G_{11}=\tfrac35\): from \(0\), the chain must move to \(1\), while a move to \(2\) produces no visits to \(1\). Substitution gives \(\tfrac12G_{11}=\tfrac35=G_{01}\) and \(\tfrac13G_{01}=\tfrac15\le\tfrac65=G_{00}\). The bound need not be sharp to establish finiteness.
Worked Example: Paths of Different Lengths
Take \(S=\{0,1,2,z\}\) and $$ P= \begin{bmatrix} 0&\tfrac12&0&\tfrac12\\ 0&0&\tfrac13&\tfrac23\\ \tfrac14&0&0&\tfrac34\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are \(\tfrac12+\tfrac12=1\), \(\tfrac13+\tfrac23=1\), \(\tfrac14+\tfrac34=1\), and \(1=1\). States \(0\) and \(2\) communicate. The path \(0\to1\to2\) has length \(2\) and probability \(\alpha=\tfrac12\cdot\tfrac13=\tfrac16\); the path \(2\to0\) has length \(1\) and probability \(\beta=\tfrac14\).
Starting from \(0\), a return to \(0\) requires the cycle \(0\to1\to2\to0\), whose probability is \(\tfrac12\cdot\tfrac13\cdot\tfrac14=\tfrac1{24}\). A move to \(z\) prevents return, so \(G_{00}=1/(1-\tfrac1{24})=\tfrac{24}{23}\). The lemma gives \(\tfrac16G_{22}\le G_{02}\) and \(\tfrac14G_{02}\le\tfrac{24}{23}\), hence \(G_{22}\le\tfrac{576}{23}\), which is finite.
Check by direct calculation. The only return cycle from \(2\) is \(2\to0\to1\to2\), also of probability \(\tfrac14\cdot\tfrac12\cdot\tfrac13=\tfrac1{24}\), so \(G_{22}=\tfrac{24}{23}\). To find \(G_{02}\), a visit to \(2\) from \(0\) requires first moving to \(1\), then from \(1\) to \(2\). In terms of expected visits, \(G_{12}=\tfrac13G_{22}=\tfrac8{23}\), and \(G_{02}=\tfrac12G_{12}=\tfrac4{23}\). Substitution checks the two inequalities: \(\tfrac16G_{22}=\tfrac4{23}=G_{02}\), while \(\tfrac14G_{02}=\tfrac1{23}\le\tfrac{24}{23}=G_{00}\). The chain has paths of unequal lengths in the two directions, but the comparison is unchanged.
Why Communication Matters
Worked Example: One-Way Reachability Is Not Enough
Let \(S=\{0,1\}\), with \(0\) moving to \(1\) with probability \(1\), and \(1\) staying at \(1\) with probability \(1\): $$ P= \begin{bmatrix} 0&1\\ 0&1 \end{bmatrix}. $$ The row sums are \(0+1=1\) and \(0+1=1\). Starting from \(0\), there is no return to \(0\), so \(f_0=0\) and \(G_{00}=1/(1-0)=1\); state \(0\) is transient. Starting from \(1\), every time is a visit to \(1\), so \(p_{11}^{(n)}=1\) for all \(n\ge0\) and \(G_{11}=\sum_{n=0}^{\infty}1=\infty\). Thus state \(1\) is recurrent. Although \(0\) can reach \(1\), state \(1\) cannot reach \(0\), so the states do not communicate.
Common mistake. It is incorrect to argue that “if \(i\) can reach \(j\), then \(i\) and \(j\) have the same transience status.” This example disproves that claim: \(0\) reaches \(1\), but their classifications differ. In the path comparison, using only the path \(0\to1\) gives \(\alpha G_{11}\le G_{01}\); it does not give a finite upper bound on \(G_{11}\). The reverse path is needed for \(\beta G_{01}\le G_{00}\). Together, and only with \(\alpha,\beta>0\), they imply \(\alpha\beta G_{11}\le G_{00}\).
The practical consequence is that transience can be checked once per communicating class: if one state has finite expected total visits to itself, the path bounds force the same for every state that communicates with it. The argument does not require a finite state space, nor does it require the class to be closed. It requires only a discrete-time Markov chain, positive-probability paths in both directions, and the nonnegative transition-probability sums used in the comparison.
Check Your Understanding
Use the definitions and path comparison to answer the following. When checking a path, multiply the transition probabilities along its specified edges.
- If \(G_{ii}=5\), and paths from \(i\) to \(j\) and from \(j\) to \(i\) have probabilities \(\tfrac12\) and \(\tfrac14\), respectively, what upper bound does the path comparison give for \(G_{jj}\)?
- Why does \(G_{ii}<\infty\) imply that \(i\) is transient?
- In the four-state example, identify the two path lengths and their path probabilities between \(0\) and \(2\).
- Which direction of the path comparison fails to be available in the one-way example, and why does that matter?
- Does the proof require the communicating class to be closed or finite? State the assumptions it uses instead.