From Mutual Accessibility to Classes
In a finite Markov chain, two states belong together when each can be reached from the other in a finite number of steps. Grouping states this way gives a partition: each state belongs to exactly one group, and no two groups overlap. The key condition is mutual reachability. A route from one state to another in only one direction is not enough to put them in the same class.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic, so \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). Write \(P^{(n)}=P^n\), where \(p_{ij}^{(n)}\) is the probability of being in state \(j\) after \(n\) steps when starting in state \(i\). We take \(P^{(0)}=I\), the identity matrix. Thus every state is accessible from itself in zero steps, whether or not it has a self-transition.
The distinction between accessibility and communication is important. Accessibility is directional; communication requires accessibility in both directions. The class \([i]\) is defined by mutual accessibility, not by sharing a direct transition with \(i\). Paths can take several steps, and their probabilities are read from the corresponding powers of \(P\).
The earlier material on communication establishes that \(\leftrightarrow\) is an equivalence relation. For completeness, its three properties follow directly from the definitions and the Chapman–Kolmogorov equations.
Proof. Reflexivity: \(p_{ii}^{(0)}=1>0\), so \(i\) is accessible from itself and \(i\leftrightarrow i\). Symmetry: the definition of \(i\leftrightarrow j\) requires both \(i\) accessible from \(j\) and \(j\) accessible from \(i\); exchanging \(i\) and \(j\) leaves that requirement unchanged. Transitivity: suppose \(i\leftrightarrow j\) and \(j\leftrightarrow k\). There are nonnegative integers \(m,n,r,s\) such that \(p_{ij}^{(m)}>0\), \(p_{ji}^{(n)}>0\), \(p_{jk}^{(r)}>0\), and \(p_{kj}^{(s)}>0\). By Chapman–Kolmogorov, \(p_{ik}^{(m+r)}=\sum_{\ell\in S}p_{i\ell}^{(m)}p_{\ell k}^{(r)}\ge p_{ij}^{(m)}p_{jk}^{(r)}>0\). The same argument gives \(p_{ki}^{(s+n)}\ge p_{kj}^{(s)}p_{ji}^{(n)}>0\). Hence \(i\leftrightarrow k\). \(\square\)
Why the Classes Form a Partition
Proof. For every \(i\in S\), reflexivity gives \(i\leftrightarrow i\), so \(i\in[i]\). Therefore the classes cover \(S\). Now take any \(i,k\in S\). If \([i]\cap[k]\) is nonempty, choose \(x\in[i]\cap[k]\). Then \(i\leftrightarrow x\) and \(k\leftrightarrow x\). Symmetry gives \(x\leftrightarrow k\), and transitivity gives \(i\leftrightarrow k\). If \(y\in[i]\), then \(y\leftrightarrow i\) and \(i\leftrightarrow k\), so transitivity gives \(y\leftrightarrow k\), meaning \(y\in[k]\). This proves \([i]\subseteq[k]\). Reversing the roles of \(i\) and \(k\) gives \([k]\subseteq[i]\), so the classes are equal. Thus two classes that intersect are equal; otherwise they are disjoint. Since every state lies in a class, and intersecting classes coincide, every state belongs to exactly one class. \(\square\)
This also gives a useful maximality description. A communicating class is a set in which every pair of states communicates, and it cannot be enlarged while keeping that property. Indeed, if \(j\in[i]\), then every state in \([i]\) communicates with \(j\), by symmetry and transitivity. Conversely, any set containing \(i\) in which every pair communicates must be contained in \([i]\), since each of its states communicates with \(i\). So classes are not just convenient groups: they are the largest mutually communicating groups.
Worked Example: Three Classes in a Five-State Chain
Consider \(S=\{1,2,3,4,5\}\) and the transition matrix
Each row sums to \(1\): the row sums are \(1,1,1,1,1\), respectively. States \(1\) and \(2\) move to each other, so each is accessible from the other in one step. Thus \([1]=[2]=\{1,2\}\). States \(4\) and \(5\) also move to each other, giving \([4]=[5]=\{4,5\}\). From state \(3\), the chain moves to \(4\), then alternates between \(4\) and \(5\); it never returns to \(3\). No other state can reach \(3\), so \([3]=\{3\}\).
In particular, \(p_{33}=0\) does not prevent state \(3\) from being in its own class. The zero-step probability is \(p_{33}^{(0)}=1\), so \(3\leftrightarrow3\). The three classes are \(\{1,2\}\), \(\{3\}\), and \(\{4,5\}\). They are disjoint and their union is all five states.
A useful way to organize a classification is to ask, for each state, which other states are reachable from it and which can reach it. Only the intersection of those two collections belongs to its communicating class. The next example shows why checking only one direction gives the wrong grouping.
Worked Example: One-Way Accessibility Does Not Merge Classes
Let \(S=\{1,2,3,4\}\) and
The row sums are \(\tfrac12+\tfrac12=1\), \(1=1\), \(1=1\), and \(1=1\), so this is a valid transition matrix. States \(1\) and \(2\) communicate: \(p_{12}=\tfrac12>0\) and \(p_{21}=1>0\). States \(3\) and \(4\) communicate: \(p_{34}=1>0\) and \(p_{43}=1>0\).
There is also accessibility from the first pair to the second: \(p_{13}=\tfrac12>0\). But there is no path from either \(3\) or \(4\) back to \(1\) or \(2\): from \(3\) and \(4\), every transition remains in \(\{3,4\}\). Thus accessibility from \(\{1,2\}\) to \(\{3,4\}\) is possible, but accessibility in the reverse direction is not. The communicating classes are exactly the two classes \(\{1,2\}\) and \(\{3,4\}\), not one merged class.
Finding Classes Through Longer Paths
A state need not have a direct transition to every other member of its class. To determine communication, it is enough to establish positive-probability paths in both directions; the path lengths in the two directions need not be equal. In a finite chain, these paths can be checked using powers of \(P\), or by tracing the possible transitions while keeping track of direction.
Worked Example: Indirect Paths Put Four States in One Class
Consider the chain on \(S=\{1,2,3,4\}\) with transition matrix
The row sums are \(1\), \(\tfrac12+\tfrac12=1\), \(1\), and \(\tfrac12+\tfrac12=1\). To verify that all states communicate, it suffices to trace positive-probability routes. There is a cycle \(1\to2\to3\to4\to1\): the transition probabilities along these four edges are \(1,\tfrac12,1,\tfrac12\), whose product is \(\tfrac14>0\). Thus each state can reach the next state in the cycle, and by following the cycle further can reach every state. In particular, \(1\) reaches \(3\) in two steps with probability \(\tfrac12\), and reaches \(4\) in three steps with probability \(\tfrac12\). State \(4\) reaches \(1\) in one step with probability \(\tfrac12\), and reaches \(2\) by way of \(1\) in two steps with probability \(\tfrac12\). The cycle provides the corresponding routes for all starting states. Hence every pair communicates, and there is exactly one class: \(\{1,2,3,4\}\).
Check: every row has total probability \(1\), and the cycle probability is \(1\cdot\tfrac12\cdot1\cdot\tfrac12=\tfrac14>0\). The positive probability confirms that each displayed route is genuinely possible, rather than merely a sequence of transitions with a zero-probability step.
A Reliable Classification Procedure
For a finite state space, the following procedure keeps the two directions of communication separate.
For each starting state \(i\), identify every \(j\) for which \(p_{ij}^{(n)}>0\) for at least one \(n\ge0\). Include \(i\) itself by the zero-step convention.
Put \(j\) in \([i]\) only when \(j\) is accessible from \(i\) and \(i\) is accessible from \(j\).
If two classes share a state, they are the same class. Finally check that each state appears in one class and that the listed classes cover \(S\).
Common mistake. In the second example, one might see \(p_{13}=\tfrac12>0\) and put states \(1\) and \(3\) in the same class. That calculation establishes only that \(3\) is accessible from \(1\). It does not establish the reverse. Starting from either \(3\) or \(4\), the chain stays in \(\{3,4\}\), so \(p_{31}^{(n)}=p_{41}^{(n)}=0\) for every \(n\ge0\). Therefore \(1\) and \(3\) do not communicate. The correction is to test both directions before assigning class membership.
Once the partition is known, later questions can be asked class by class. The partition itself says which states are mutually reachable; it does not, on its own, assert that a class has no transitions leaving it or describe long-run behavior. Those are separate properties and require separate analysis.
Check Your Understanding
For each question, distinguish positive-probability paths from direct one-step transitions, and use mutual accessibility when deciding class membership.
- Why does every state belong to its own communicating class even if \(p_{ii}=0\)?
- In the second worked example, which direction of accessibility fails between \(\{1,2\}\) and \(\{3,4\}\)?
- Suppose \(i\) communicates with \(j\), and \(j\) communicates with \(k\). Which property of communication guarantees that \(i\) and \(k\) belong to the same class?
- Can two communicating classes overlap in exactly one state without being identical? Explain using the partition theorem.
- For the third worked example, give a positive-probability route from state \(2\) to state \(4\), and compute the probability of following that route.