Characterizing Closed Classes by Outgoing Edges

From Transition Probabilities to Outgoing Edges

A communicating class is determined by mutual accessibility: every pair of its states can be reached from one another along positive-probability paths. Closedness asks a different question. It concerns whether the chain can move from that class to any state outside it. The distinction matters in a transition graph: internal paths establish communication, while even one positive-probability edge leaving the class prevents it from being closed.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable 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\in S\). A transition edge \(i\to j\) is present exactly when \(p_{ij}>0\). A communicating class \(C\subseteq S\) is an equivalence class under mutual accessibility. It is closed if, starting from any state in \(C\), the chain stays in \(C\) at the next step with probability one.

Proof. First suppose that \(C\) is closed. For each \(i\in C\), closedness means \(\mathbb{P}_i(X_1\in C)=1\). Since \(\mathbb{P}_i(X_1=j)=p_{ij}\), every \(j\notin C\) must have \(p_{ij}=0\). Thus there is no positive-probability transition edge from \(C\) to its complement. Conversely, suppose there is no such edge. For every \(i\in C\), \(p_{ij}=0\) for all \(j\notin C\), so \(\sum_{j\in C}p_{ij}=\sum_{j\in S}p_{ij}=1\). Hence \(\mathbb{P}_i(X_1\in C)=1\) for every \(i\in C\), which is exactly the definition of closedness. The argument also covers a singleton class and a class equal to all of \(S\): in the latter case there are no outside states to check. \(\square\)

The criterion is local: it only requires checking one-step transitions from states in \(C\). Its consequence is global in time. If no edge leaves \(C\), then a chain started in \(C\) remains there at every later time with probability one. Conversely, an edge leaving \(C\) is enough to disprove closedness, even if it is unlikely or the chain can also move back into \(C\).

Proof. If \(C\) has an outgoing edge \(i\to j\), then the one-step path from \(i\in C\) to \(j\notin C\) has probability \(p_{ij}>0\), so a positive-probability path leaves \(C\). In the other direction, consider any finite path \(i_0,i_1,\ldots,i_m\) that starts in \(C\) and ends outside \(C\), with positive probability. Its probability is \(\prod_{r=0}^{m-1}p_{i_r i_{r+1}}\), so every factor is positive. There is a first index \(r\) for which \(i_r\in C\) and \(i_{r+1}\notin C\); this gives an outgoing edge. Therefore, if there are no outgoing edges, no such path exists. Together with the theorem, this proves the equivalence. \(\square\)

Applying the Criterion to a Transition Graph

For a transition matrix, form the directed graph by drawing \(i\to j\) precisely for entries \(p_{ij}>0\). The communicating classes are the strongly connected components: within each such component, every state can reach every other state by a directed path. Once a class is identified, test only edges that start in that class and end outside it. Internal edges do not threaten closedness, and entries equal to zero do not represent edges.

Here “outgoing” is relative to a particular class, not to the whole graph. A vertex may have an outgoing edge from its class and still belong to a communicating class; the edge simply shows that this class is not closed. Also, the size of a transition probability does not change the test: any strictly positive value counts, while zero does not.

Common Graph and Matrix Pitfalls

A frequent mistake is to treat a zero entry as an edge. In the last example, suppose someone reports that \(\{1,2\}\) is not closed because “there is a transition from 1 to 3.” The matrix entry used for that claim is \(p_{13}=0\). The corrected test is \(p_{13}>0\); since \(0\) is not strictly positive, there is no edge \(1\to3\). The same check must be made for every state in the class and every state outside it.

A different mistake is to require that a class have no outgoing edges in order to be a communicating class. That confuses two separate properties. Communication concerns whether states within the class can reach one another; closedness concerns whether transitions can leave. In the first example, \(\{1,2\}\) is a communicating class even though the edge \(2\to3\) makes it nonclosed.

Finally, do not replace “positive probability” with “large probability” or “likely.” In the second example, the edge with probability \(\tfrac17\) is decisive. If a class has even one outgoing edge of positive probability, it is not closed, regardless of the other transition probabilities. Conversely, a visual arrow drawn without a positive matrix entry cannot disqualify a class.