Accessibility Is Not Communication

Reachability Has a Direction

A positive-probability path from state \(i\) to state \(j\) answers a one-way question: can the chain get from \(i\) to \(j\)? It does not answer whether the chain can get back. Confusing these questions can lead to incorrect communicating classes and incorrect conclusions about irreducibility. The distinction is visible in a directed transition graph: an arrow \(i\to j\) records a possible move from \(i\) to \(j\), not a two-way connection.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on the probability space \((\Omega,\mathcal{F},\mathbb{P})\), with finite or countable state space \(S\) and row-stochastic transition matrix \(P=(p_{ij})\). Thus \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row sums to \(1\). Write \(p_{ij}^{(n)}\) for the \((i,j)\) entry of \(P^n\); \(P^0\) is the identity matrix.

Allowing \(n=0\) means every state is accessible from itself. For distinct states, accessibility requires a positive-length path. In a transition graph, an edge \(i\to j\) means \(p_{ij}>0\). A finite directed path \(i=i_0,i_1,\ldots,i_n=j\) with positive transition probabilities has probability \(\prod_{r=0}^{n-1}p_{i_r i_{r+1}}>0\), so it gives accessibility. Conversely, \(p_{ij}^{(n)}>0\) means at least one length-\(n\) path from \(i\) to \(j\) has positive probability. Thus a path in the directed graph tests accessibility, while a path in each direction tests communication.

What One-Way Accessibility Does—and Does Not—Tell You

Proof. By definition, \(i\leftrightarrow j\) requires both \(i\to j\) and \(j\to i\). The assumption \(j\not\to i\) rules out the second requirement, so \(i\not\leftrightarrow j\). \(\square\)

This direct implication is worth stating because the most common error is to see a path in one direction and conclude that the states belong to the same communicating class. A path back may exist, but it must be checked independently. It might be a direct transition, a longer route, or no route at all.

Communication Classes and One-Way Edges

A communicating class is a set of states that communicate with one another and is maximal with respect to that property. Equivalently, it is an equivalence class under communication. A chain can therefore contain several classes even when some states in one class can reach states in another. Reaching another class does not merge the two: the return direction is required as well.

Proof. First suppose \(c\in C\), \(d\in D\), and \(c\to d\). If there were states \(d'\in D\) and \(c'\in C\) with \(d'\to c'\), then \(d\to d'\) because states in \(D\) communicate, and \(c'\to c\) because states in \(C\) communicate. Concatenating these paths gives \(d\to c\). Together with \(c\to d\), this says \(c\leftrightarrow d\), contradicting that \(C\) and \(D\) are distinct communicating classes. Hence there is no path back from any state in \(D\) to any state in \(C\).

Now suppose the class graph had a directed cycle \(C_0\to C_1\to\cdots\to C_{r-1}\to C_0\), with distinct consecutive classes and \(r\ge2\). For each edge \(C_s\to C_{s+1}\), with indices taken cyclically, there are states \(x_s\in C_s\) and \(y_{s+1}\in C_{s+1}\) such that \(x_s\to y_{s+1}\). Since \(y_{s+1}\) and \(x_{s+1}\) belong to the same communicating class, \(y_{s+1}\to x_{s+1}\). Concatenating gives a path from \(x_s\) to \(x_{s+1}\) along every edge of the cycle. Following the cycle reaches each class from the preceding one, and continuing around the cycle gives paths back. In particular, representatives in \(C_0\) and \(C_1\) can reach one another, so they communicate. That contradicts \(C_0\ne C_1\). Thus the class graph has no directed cycles. \(\square\)

The theorem makes the direction important. If a class \(C\) reaches a class \(D\), draw \(C\to D\), not \(D\to C\). The edge describes the direction of travel along the path. A reversed arrow would assert the opposite accessibility claim.

Indirect Paths Still Count

Checking only the entries of \(P\) tests one-step transitions. Accessibility permits paths of any finite length. Consequently, \(p_{ij}=0\) does not imply that \(j\) is inaccessible from \(i\); a longer path may connect them. The correct test is whether some entry \(p_{ij}^{(n)}\) is positive for some \(n\ge0\), or, equivalently, whether the directed transition graph contains a finite path from \(i\) to \(j\).

A Common Mistake and a Reliable Test

Common mistake: “Since \(p_{12}=\tfrac12>0\), states 1 and 2 communicate.” This is an incorrect calculation because it checks only the direction from 1 to 2. In the three-state chain in the first worked example, \(p_{12}=\tfrac12>0\), but \(p_{21}=0\), and no path from 2 to 1 exists: from 2 the chain can only stay at 2 or move to 3, and from 3 it stays at 3. Thus \(1\to2\), but \(2\not\to1\), so \(1\not\leftrightarrow2\).

The correction is to test both directions separately. For each ordered pair, look for a finite directed path, allowing paths longer than one step. Then declare two states to communicate only if each has a path to the other. This procedure prevents both errors: treating a one-way path as mutual access, and treating a missing one-step transition as proof that no path exists.