Mutual Accessibility
A transition graph records which moves a Markov chain can make with positive probability. A path in one direction says that one state is accessible from another; communication requires paths in both directions. The two paths may have different lengths. This distinction lets us compare states even when there is no direct transition between them.
Let \((X_n)_{n\ge0}\) 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})\). The matrix is row-stochastic: \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row sums to \(1\). Write \(P^{(n)}=P^n\) for the \(n\)-step transition matrix. In particular, \(P^{(0)}\) is the identity matrix, so \(p_{ij}^{(0)}=1\) when \(i=j\), and \(p_{ij}^{(0)}=0\) otherwise.
For distinct states, accessibility can be read from a path in the transition graph: draw an edge \(i\to j\) exactly when \(p_{ij}>0\). A path of length \(n\) is a sequence of \(n\) such edges. The path need not be unique, and its edges need not have equal probabilities. What matters is that the probability of following at least one such path is positive.
A Path Criterion for Communication
Proof. By definition, \(i\leftrightarrow j\) means that \(j\) is accessible from \(i\) and \(i\) is accessible from \(j\). The first condition is exactly the existence of an \(r\ge0\) with \(p_{ij}^{(r)}>0\); the second is exactly the existence of an \(s\ge0\) with \(p_{ji}^{(s)}>0\). This proves the first assertion in both directions.
Now suppose \(i\ne j\), \(S\) has \(m\) states, and \(j\) is accessible from \(i\). For some \(n\ge1\), \(p_{ij}^{(n)}>0\). The path expansion for \(p_{ij}^{(n)}\) is a sum of nonnegative products of one-step transition probabilities. Since the sum is positive, at least one product is positive. Thus there is a path \(i=x_0,x_1,\ldots,x_n=j\) whose every edge has positive probability. If a state occurs twice in this path, say \(x_a=x_b\) with \(a<b\), delete the segment from just after \(x_a\) through \(x_b\). If \(b<n\), the next edge remains valid because \(x_a=x_b\); if \(b=n\), the shortened path ends at \(x_a=x_n=j\). The resulting path still has positive-probability edges and has smaller length. Repeating this deletion produces a path with no repeated states. A path with no repeated states among \(m\) states has at most \(m-1\) edges. Apply the same argument to a path from \(j\) to \(i\). This proves the finite bound for both directions. \(\square\)
This criterion separates the two checks: find a positive-probability path from \(i\) to \(j\), then find one from \(j\) to \(i\). A direct edge is sufficient for one direction but is not required. Nor must the two paths have equal lengths. In a finite chain, the theorem gives a finite search: for distinct states, no path longer than \(m-1\) is needed.
Worked Example: Reading Mutual Accessibility from a Graph
On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), consider a discrete-time Markov chain with state space \(S=\{a,b,c,d\}\) and transition matrix
The row sums are \(0+1+0+0=1\), \(\tfrac12+0+\tfrac12+0=1\), \(0+0+0+1=1\), and \(0+0+1+0=1\), so the matrix is row-stochastic. Its positive-probability edges are \(a\to b\), \(b\to a\), \(b\to c\), \(c\to d\), and \(d\to c\).
There is a one-step path \(a\to b\), and a one-step path \(b\to a\), so \(a\leftrightarrow b\). There is also a one-step path in each direction between \(c\) and \(d\), so \(c\leftrightarrow d\). However, \(b\) can reach \(c\) in one step, while neither \(c\) nor \(d\) has a path back to \(a\) or \(b\). Thus no state among \(a,b\) communicates with a state among \(c,d\). In particular, accessibility in one direction alone does not establish communication.
Worked Example: Finding Paths Using Matrix Powers
On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let a discrete-time chain have state space \(S=\{1,2,3\}\) and transition matrix
Its row sums are \(0+1+0=1\), \(0+0+1=1\), and \(\tfrac12+\tfrac12+0=1\). The two-step matrix, computed by multiplying each row of \(P\) by \(P\), is
For example, row 1 of \(P^2\) is row 2 of \(P\), namely \((0,0,1)\). Row 2 of \(P^2\) is row 3 of \(P\), namely \((\tfrac12,\tfrac12,0)\). Row 3 is \(\tfrac12\) times row 1 of \(P\) plus \(\tfrac12\) times row 2 of \(P\), giving \((0,\tfrac12,\tfrac12)\).
For states \(1\) and \(3\), \(p_{13}^{(2)}=1>0\), while \(p_{31}=\tfrac12>0\). Hence \(1\leftrightarrow3\). For \(1\) and \(2\), \(p_{12}=1>0\), and a two-step path from \(2\) to \(1\) has probability \(p_{23}p_{31}=1\cdot\tfrac12=\tfrac12>0\). Thus \(1\leftrightarrow2\). Finally, \(p_{23}=1>0\) and \(p_{32}=\tfrac12>0\), so \(2\leftrightarrow3\). Every distinct pair communicates.
Check: the computed entries agree with the path probabilities: \(p_{13}^{(2)}=1\), \(p_{21}^{(2)}=\tfrac12\), and \(p_{32}=\tfrac12\). Each is positive, as required for its stated direction of accessibility.
Worked Example: A Graph with Different Path Lengths
On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), consider a discrete-time chain on \(S=\{1,2,3,4\}\). From state \(1\), the chain moves to \(2\) or \(3\), each with probability \(\tfrac12\). From state \(2\) it moves to \(4\), from state \(3\) it moves to \(4\), and from state \(4\) it moves to \(1\), all with probability \(1\). The matrix is
The row sums are \(0+\tfrac12+\tfrac12+0=1\), \(0+0+0+1=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\). To test whether \(1\) and \(4\) communicate, use the path \(1\to2\to4\), which has probability \(\tfrac12\cdot1=\tfrac12>0\). In the reverse direction, \(4\to1\) is a one-step path of probability \(1>0\). Therefore \(1\leftrightarrow4\), although the displayed paths have lengths two and one.
In fact, every distinct pair communicates. From any state, one can reach \(1\): from \(4\) in one step, and from \(2\) or \(3\) by first reaching \(4\), then \(1\). From \(1\), one can reach \(2\) or \(3\) in one step and \(4\) in two steps. Concatenating these paths gives a positive-probability path from any state to any other. For example, \(2\to4\to1\to3\) has probability \(1\cdot1\cdot\tfrac12=\tfrac12>0\), while \(3\to4\to1\to2\) also has probability \(1\cdot1\cdot\tfrac12=\tfrac12>0\).
Common Mistake: Checking Only One Step
A zero entry \(p_{ij}=0\) means there is no one-step transition from \(i\) to \(j\); it does not rule out accessibility in multiple steps. In the three-state example, \(p_{13}=0\), but \(p_{13}^{(2)}=1\), so state \(3\) is accessible from state \(1\). Checking only entries of \(P\) can therefore miss communication that appears in powers of \(P\). The correction is to search for paths of any finite length in each direction, or, for distinct states in a finite chain, to use the bound of \(m-1\) steps proved above.
A second error is to require a path of the same length in both directions. Communication asks for a path from \(i\) to \(j\) and a path from \(j\) to \(i\); it does not require \(p_{ij}^{(n)}>0\) and \(p_{ji}^{(n)}>0\) for one shared \(n\). In the last example, the paths used between \(1\) and \(4\) have different lengths, yet establish communication.
These tests use only positive probabilities, not their magnitudes beyond positivity. If a path has positive-probability edges, the product of those probabilities is positive, so that path contributes positive probability to the corresponding transition over its length. Conversely, the path expansion of a positive \(n\)-step transition contains at least one positive-probability path. Thus graph inspection and matrix-power inspection express the same accessibility test.
Check Your Understanding
For each question, distinguish accessibility in one direction from communication, and use positive-probability paths.
- If \(p_{ij}=0\) but \(p_{ij}^{(2)}>0\), what can you conclude about accessibility from \(i\) to \(j\)?
- In the first worked example, is \(c\) accessible from \(b\)? Is \(b\) accessible from \(c\)? Do \(b\) and \(c\) communicate?
- For the three-state matrix, give a positive-probability path from \(2\) to \(1\), and compute its probability.
- Why can communication hold when the path from \(i\) to \(j\) and the path from \(j\) to \(i\) have different lengths?
- A finite chain has \(m\) states and two distinct states communicate. What maximum path length in each direction is sufficient when testing this pair?