Communicating class

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\ge 0$. 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 classThus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See 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.

For this constructed example, in state order $(s,c_1,c_2,a)$, the transition matrix isThere 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\ge 0}{2}^{-n}=2$. The two eventual destination classes each have probability ${\sum }_{k\ge 0}(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.

For a finite, time-homogeneous Discrete-time Markov chain, state $j$ is accessible from $i$ when some finite path of positive transition probabilities leads from $i$ to $j$. Equivalently, $(P^n{)}_{ij}>0$ for some $n\ge 0$, allowing a zero-step path when $i=j$. Accessibility is reflexive and transitive; communicating states require accessibility in both directions. See Ward Whitt's lecture notes of September 24, 2013, classification of states. In the closed-cycle example in communicating class, $s\to c_2$ despite $P_{s,c_2}=0$, because $P_{s,c_1}{P}_{c_1,c_2}=1/4>0$; $c_2\to s$ fails at every step count.

A communicating class of a Markov chain is open when a state in the class has positive probability of transitioning to a state outside it. Once a path leaves, it cannot return to the class: a return path would make the outside state communicate with the class. Every open class consists of transient states. Conversely, a finite transient communicating class is open; an infinite closed communicating class can be transient.

Two states of a Markov chain communicate when each can be reached from the other with positive probability in finitely many steps.

A communicating class is closed when no transition from it can reach a state outside it.

In a finite chain, a communicating class that is not closed is transient: after it is left, it need not be visited again and is eventually left almost surely.

The period of a state $i$ is the greatest common divisor of its positive-probability return times:A state is aperiodic when its period is one.

A state can have no positive-probability return at any positive time, for example when its transition-matrix column is zero. Its return-time set is empty. The convention $\gcd \varnothing =0$ assigns period zero; conventions defining period only for a nonempty return set instead leave it undefined. Such a state must not be called aperiodic merely because its communicating class is a singleton.

If communicating states $i,j$ can be joined in $r$ and $s$ steps, then $r+s$ is a return time to $i$, and adjoining any return loop of length $n$ at $j$ makes $r+n+s$ another. Their difference shows $d(i)\mid n$, hence $d(i)\mid d(j)$; symmetry gives equality.