Why a Single Edge Can Matter
A Markov chain’s classification depends on which transitions have positive probability, not on their precise positive values. Changing one transition can therefore have a structural effect: two communicating classes may merge, one class may split, a closed class may acquire an exit, or the possible return times to a state may change. Periods are especially sensitive: adding a self-loop can change a period from greater than one to one.
Consider a discrete-time Markov chain \((X_n)_{n\ge0}\) on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The support graph has one directed edge \(i\to j\) exactly when \(p_{ij}>0\). A path of length \(n\) from \(i\) to \(j\) is a sequence of \(n\) such edges; a path of length zero from a state to itself is allowed.
The path characterization follows from the transition-matrix multiplication rule: \(p_{ij}^{(n)}\) is the sum, over all intermediate states, of the products of the \(n\) transition probabilities along the corresponding paths. Every term is nonnegative, so the sum is positive exactly when at least one such path has all its edges positive. For \(n=0\), the transition matrix is the identity, matching the length-zero path.
To compare chains, distinguish a support change from an arbitrary numerical change. We say that edges are added if every old positive edge remains positive and some previously zero entries become positive; other entries may be adjusted to keep each row sum equal to one. Edges are removed if some old positive edges become zero and all remaining positive entries are adjusted as needed. These comparisons do not cover changes that also delete old edges while adding new ones. Always check that a proposed matrix is row-stochastic before using it.
What Edge Inclusion Guarantees
Proof. Every old path still consists of positive edges after the change, so each old accessibility relation remains. If two states communicated before, paths in both directions remain; they still communicate afterward. Consequently, a new communicating class cannot contain only part of an old class: if it contains one state from an old class, it contains every state in that class. New paths may connect old classes in both directions, joining them into a larger class, but cannot separate states that already communicated. Finally, closure is a separate condition about all edges leaving a class. An added edge from a state in a class to a state outside it violates that condition. \(\square\)
Proof. A positive-probability return in \(n\) steps corresponds to a length-\(n\) path from \(i\) back to \(i\). Under edge addition every old path remains, so \(R_i\subseteq R_i'\). The new gcd divides every member of \(R_i'\), hence every member of \(R_i\); it therefore divides the greatest common divisor of \(R_i\), which is the old period. Under edge removal every new path was already an old path, so \(R_i'\subseteq R_i\). The old gcd divides every member of \(R_i\), and therefore every member of \(R_i'\); it divides their greatest common divisor. These arguments require a nonempty return-length set for the gcd in question to be a positive integer. \(\square\)
In particular, an added edge cannot increase a defined period, and a removed edge cannot decrease a defined period. The period need not change: an edge may add no new return lengths, or the added or removed lengths may leave the gcd unchanged. These divisibility statements compare the same state across nested supports; they do not assert that every state has a return path.
Worked Comparisons
Worked Example: An Added Edge Merges Classes
On \(S=\{1,2,3\}\), compare the following matrices. The only support change is the added edge \(2\to1\); the probability formerly assigned to the self-loop at state \(2\) is adjusted so its row still sums to one.
Every row of \(P\) sums to \(0+1+0=1\), \(0+1+0=1\), and \(1+0+0=1\). Every row of \(P'\) sums to \(0+1+0=1\), \(\tfrac12+\tfrac12+0=1\), and \(1+0+0=1\).
In the first chain, state \(1\) leads to \(2\), and state \(2\) stays at \(2\); there is no path from \(2\) to \(1\). State \(3\) leads to \(1\), from which the chain can reach \(2\), but neither \(1\) nor \(2\) can reach \(3\). Thus all three communicating classes are singletons. The class \(\{2\}\) is closed because its only outgoing edge is \(2\to2\); \(\{1\}\) and \(\{3\}\) are not closed because \(1\to2\) and \(3\to1\), respectively.
In the modified chain, \(1\to2\) and the new edge \(2\to1\) show that \(1\leftrightarrow2\). No edge leads from either state to \(3\), so \(\{1,2\}\) is a communicating class. It is closed: from \(1\) the chain goes to \(2\), and from \(2\) it goes only to \(1\) or \(2\). State \(3\) remains its own, nonclosed class. The added edge has merged two classes, and the resulting class is closed. This also shows why adding edges does not invariably destroy closedness: the class’s new edges can stay inside the enlarged class.
Worked Example: Removing a Self-Loop Changes the Period
On \(S=\{1,2,3\}\), start with a directed three-cycle and a self-loop at state \(1\), then remove the self-loop. Check the row sums in both matrices before analyzing return times.
The rows of \(P\) sum to \(\tfrac12+\tfrac12+0=1\), \(0+0+1=1\), and \(1+0+0=1\). The rows of \(P'\) sum to \(0+1+0=1\), \(0+0+1=1\), and \(1+0+0=1\).
Both chains are irreducible: the edges \(1\to2\), \(2\to3\), and \(3\to1\) provide paths around the cycle, so every state can reach every other. For \(P\), state \(1\) returns in one step with probability \(\tfrac12>0\); its period is therefore \(1\), since a positive integer dividing the return length \(1\) must equal \(1\).
For \(P'\), each step deterministically advances around the three-cycle. Starting at state \(1\), the chain is at \(2\) after one step, at \(3\) after two, and back at \(1\) after three. It then repeats this pattern, so the return lengths are exactly \(3,6,9,\ldots\), whose gcd is \(3\). The period changes from \(1\) to \(3\) when the self-loop is removed. In particular, deleting an edge can increase a period even though irreducibility is preserved.
Worked Example: Removing an Edge Splits a Class
On \(S=\{1,2,3,4\}\), consider a directed cycle in which state \(2\) also has a self-loop. Remove only the edge \(2\to3\), assigning its probability to the self-loop instead.
The rows of \(P\) sum to \(0+1+0+0=1\), \(0+\tfrac12+\tfrac12+0=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\). The rows of \(P'\) sum to \(0+1+0+0=1\), \(0+1+0+0=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\).
Before removal, the cycle \(1\to2\to3\to4\to1\) makes all four states communicate, so the chain is irreducible. After removal, state \(2\) is absorbing and cannot reach any other state; \(\{2\}\) is a closed class. States \(1\), \(3\), and \(4\) are each singleton communicating classes: \(1\to2\), \(3\to4\to1\to2\), and \(4\to1\to2\), and none has a path back from \(2\). The singleton classes \(\{1\}\), \(\{3\}\), and \(\{4\}\) are not closed because their states have positive-probability edges leading outside their respective classes. Thus removal has split the original class and made one of the resulting classes closed.
Reading Class and Closure Changes Carefully
Communication is mutual accessibility, so a one-way edge between two classes does not merge them. For example, if an edge is added from class \(C\) to class \(D\), but there is still no path from \(D\) back to \(C\), the classes remain distinct. To establish a merge, verify paths in both directions between the old classes.
Closure must also be checked against the whole class, not one representative state. A class is closed only when no positive-probability edge leaves it from any of its states. Under pure edge addition, an old closed class can lose that property if an added edge exits it. Under pure edge removal, a closed class remains closed because removing edges cannot create an exit; a previously nonclosed class can become closed if all its exits are removed. A change that both adds and removes edges has neither simple monotonicity guarantee.
Common mistake. A tempting but incorrect calculation in the second example is to retain the old probability \(\tfrac12\) on the self-loop after deleting \(1\to1\), while leaving the probability on \(1\to2\) unchanged at \(\tfrac12\). That proposed first row would be \((\tfrac12,\tfrac12,0)\), which still has a self-loop; it has not removed the edge. If instead one sets both entries to zero, the row sum becomes \(0\), so the result is not a transition matrix. The valid removal sets the self-loop probability to zero and assigns the full row probability \(1\) to \(1\to2\), as in \(P'\). Only after checking the modified row sums should its support and period be classified.
The practical sequence is therefore: identify the old and new positive edges; verify the rows still sum to one; trace paths in both directions to find communicating classes; inspect every edge leaving each class to decide closure; and compare return-length sets before taking their gcd. This separates effects that are guaranteed by support inclusion from effects that depend on the particular paths created or destroyed.
Check Your Understanding
For each question, distinguish the positive-edge graph from the numerical transition probabilities, and state any row-sum check you use.
- If a support change retains every old edge and adds one edge, can two states that previously communicated cease to communicate? Explain using paths.
- In the second worked example, what are the return lengths to state \(2\) after the self-loop is removed, and what is their gcd?
- Can adding an edge make a previously nonclosed class closed? Give the relevant condition on the class’s outgoing edges.
- A state has old return-length set \(\{2,4,6,\ldots\}\). If edge addition makes return length \(3\) possible, what must be true of the new period?
- Why does removing a one-way edge between two communicating classes not necessarily split either class?