Proving Communication Is an Equivalence Relation

From Finite Paths to Communication

In a Markov chain, one state may be reachable from another after a finite number of transitions. Mutual reachability is a natural way to identify states that belong together: each can be reached from the other, though the two routes need not have the same length. The key fact is that this mutual-reachability relation has the three properties of an equivalence relation. The proof uses the zero-step transition for reflexivity and the Chapman–Kolmogorov equations for transitivity.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a nonempty finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix is \(P=(p_{ij})\), where \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\); each row sums to \(1\). Write \(P^{(n)}=P^n\) and \(p_{ij}^{(n)}\) for its \(n\)-step transition probabilities. In particular, \(P^{(0)}\) is the identity matrix, so \(p_{ij}^{(0)}=1\) if \(i=j\) and \(0\) otherwise. For a countable state space, the Chapman–Kolmogorov equation is \(p_{ik}^{(m+n)}=\sum_{\ell\in S}p_{i\ell}^{(m)}p_{\ell k}^{(n)}\); its terms are nonnegative.

Accessibility allows paths of length zero or greater, and a path of length zero does not mean that the chain makes an actual transition. It records the identity \(p_{ii}^{(0)}=1\). For a positive length \(n\), accessibility means that the probability of being at \(j\) after \(n\) steps, starting from \(i\), is positive. The proof below needs no assumption that the chain is irreducible, finite, or stationary.

Two Properties of Accessibility

Proof. For each \(i\in S\), \(p_{ii}^{(0)}=1>0\), so the definition gives \(i\to i\). Now suppose \(i\to j\) and \(j\to k\). By the definition, there are nonnegative integers \(m,n\) such that \(p_{ij}^{(m)}>0\) and \(p_{jk}^{(n)}>0\). Apply Chapman–Kolmogorov at time \(m+n\). The sum for \(p_{ik}^{(m+n)}\) contains the term with intermediate state \(j\), and every term in the sum is nonnegative. Therefore \(p_{ik}^{(m+n)}=\sum_{\ell\in S}p_{i\ell}^{(m)}p_{\ell k}^{(n)}\ge p_{ij}^{(m)}p_{jk}^{(n)}>0\). Thus \(i\to k\), as required. This also covers \(m=0\) or \(n=0\), since the zero-step probabilities are defined by the identity matrix. \(\square\)

In this proof, the positive product is a lower bound for a Chapman–Kolmogorov sum, not generally the whole sum. Other intermediate states can contribute additional positive terms. This distinction is important when calculating transition probabilities as well as when proving transitivity.

Communication Is an Equivalence Relation

Proof. For reflexivity, accessibility is reflexive by the proposition: \(i\to i\) for every \(i\). Hence both requirements in the definition of \(i\leftrightarrow i\) hold. For symmetry, if \(i\leftrightarrow j\), then \(i\to j\) and \(j\to i\). These same two statements, in reversed order, give \(j\leftrightarrow i\). For transitivity, suppose \(i\leftrightarrow j\) and \(j\leftrightarrow k\). The first assumption gives \(i\to j\) and \(j\to i\); the second gives \(j\to k\) and \(k\to j\). By transitivity of accessibility, \(i\to k\) follows from \(i\to j\) and \(j\to k\), while \(k\to i\) follows from \(k\to j\) and \(j\to i\). Thus \(i\leftrightarrow k\). All three defining properties hold, so communication is an equivalence relation. \(\square\)

Symmetry here comes directly from the definition of communication: it requires accessibility in both directions. Accessibility itself need not be symmetric. Transitivity is the part that depends on combining paths, which is why the Chapman–Kolmogorov equation matters.

Equivalence Classes Partition the State Space

An equivalence relation gives a precise way to group elements. For each \(i\in S\), define its equivalence class by \(C(i)=\{j\in S:j\leftrightarrow i\}\). A partition of \(S\) is a collection of nonempty subsets whose union is \(S\) and such that any two distinct subsets in the collection are disjoint.

Proof. Every class \(C(i)\) is nonempty because \(i\leftrightarrow i\), so \(i\in C(i)\). Each state \(x\in S\) belongs to \(C(x)\), which proves that the classes cover \(S\). To show that any two classes that overlap are equal, suppose \(C(i)\cap C(j)\) contains a state \(x\). Then \(x\leftrightarrow i\) and \(x\leftrightarrow j\). By symmetry, \(i\leftrightarrow x\); by transitivity with \(x\leftrightarrow j\), \(i\leftrightarrow j\). Now take any \(y\in C(i)\). Then \(y\leftrightarrow i\), and \(i\leftrightarrow j\), so transitivity gives \(y\leftrightarrow j\), which means \(y\in C(j)\). Hence \(C(i)\subseteq C(j)\). Interchanging \(i\) and \(j\) gives \(C(j)\subseteq C(i)\), so \(C(i)=C(j)\). Therefore, distinct classes are disjoint, and the nonempty classes cover \(S\). They form a partition. \(\square\)

This conclusion concerns the set-theoretic structure induced by communication. It does not require a finite state space: the proof applies to any nonempty finite or countable \(S\), because it uses only the equivalence-relation properties.

A Calculation Pitfall: A Product Is Not Usually the Whole Sum

A common error in using Chapman–Kolmogorov is to replace its sum over intermediate states by just one product. Suppose a route from \(i\) to \(j\) takes \(m\) steps and a route from \(j\) to \(k\) takes \(n\) steps. Their product \(p_{ij}^{(m)}p_{jk}^{(n)}\) is one contribution to \(p_{ik}^{(m+n)}\); it need not equal the full probability, since other intermediate states may also contribute.

For a proof of transitivity, it is the positive lower bound that matters. For an exact probability calculation, every intermediate state in the Chapman–Kolmogorov sum must be included. Keeping those two uses distinct avoids both a logical gap in the proof and an incorrect numerical answer.