= Communicating class
{wiki}
In a finite, time-homogeneous <Discrete-time Markov chain> with row-stochastic <transition matrix> $P$, write $i\to j$ when $j$ is accessible from $i$, meaning $(P^n)_{ij}>0$ for some $n\geq0$. States communicate, written $i\leftrightarrow j$, when both $i\to j$ and $j\to i$. Communication is an <equivalence relation>, and a communicating class is an entire <equivalence class>
$$
C(i)=\{j\in S:i\leftrightarrow j\}.
$$
Thus <communicating classes> form a <partition of a set>[partition] of the <state space>; a smaller mutually communicating subset is not itself a class. See https://math.umd.edu/~mariakc/REU2023/Tutorials/MarkovChains.pdf[Maria Cameron's Markov Chains notes, section 1.2].
The allowance of zero steps matters: $P^0=I$, the <identity matrix>, makes $i\to i$ true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-<probability> path from $i$ to $j$ with one from $j$ to $k$, and do the same in reverse. These observations prove the <equivalence relation> directly. One-way accessibility alone is not symmetric and does not define the classes; see <Accessible state of a Markov chain>.
A <closed communicating class> satisfies $P_{ij}=0$ for every $i\in C$ and $j\notin C$. Once entered, it cannot be left. A singleton class is an <absorbing state> exactly when it is closed. An <open communicating class> has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.
\Image[/markov-classes-absorption-closed-cycle.png]
{title=A constructed chain has three communicating classes: an open singleton, a closed alternating pair, and a closed absorbing singleton; dashed outlines group states into classes.}
For this constructed example, in state order $(s,c_1,c_2,a)$, the <transition matrix> is
$$
P=\begin{pmatrix}
1/2&1/4&0&1/4\\
0&0&1&0\\
0&1&0&0\\
0&0&0&1
\end{pmatrix}.
$$
There are exactly three <communicating classes>: $\{s\}$, $\{c_1,c_2\}$, and $\{a\}$. Only the first is open. The second is closed but neither of its states is an <absorbing state>; they alternate deterministically. Although $s\to c_2$ via $c_1$, the reverse accessibility fails. A direct <matrix power> check gives $(P^2)_{s,c_2}=1/4$ and $(P^2)_{c_2,s}=0$.
Starting at $s$, let $\tau$ be the first <hitting time> of either closed class. Staying at $s$ for $n$ steps has <probability> $2^{-n}$, so $\mathbb P_s(\tau>n)=2^{-n}$ and $\mathbb E_s\tau=\sum_{n\geq0}2^{-n}=2$. The two eventual destination classes each have <probability> $\sum_{k\geq0}(1/2)^k(1/4)=1/2$. Hence the <hitting probability> of the <absorbing state> $a$ is only $1/2$, and its unconditional <expected hitting time> from $s$ is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an <absorbing state> with certainty.
Classifying the <state space> separates two questions: which closed region will eventually be entered, and how does the <Markov chain> move inside that region? In this example the restriction to $\{c_1,c_2\}$ is an <irreducible Markov chain> with period two; the restriction to $\{a\}$ is a one-state <irreducible Markov chain> with period one. The whole <Markov chain> is reducible. The <absorbing state> example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.
Back to article page
