Absorbing state Created 2026-10-03 Updated 2026-10-14
For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , a state is absorbing exactly when . Nonnegativity and the row sum then force for : once entered, is never left. Equivalently, is a closed communicating class. A larger closed communicating class may keep moving internally; closure means confinement to a set, whereas absorption at a state means remaining at one point.
An absorbing state is useful for recording a terminal outcome: after a toy routine finishes, keep its outcome in the state space so that the same transition matrix still describes subsequent steps. Calling a finite Markov chain absorbing usually also requires that some absorbing state be accessible from every state. Merely containing an absorbing state is insufficient: another closed communicating class could prevent absorption. See Grinstead and Snell, Introduction to Probability, section 11.2 for this convention.
Consider a constructed routine with unfinished modes and terminal outcomes . All the following transition probabilities are chosen for illustration, not estimated from observations. In state order , take
The communicating class is open, while and are closed communicating classes consisting of absorbing states. Both terminal outcomes are accessible from both unfinished modes, sometimes by an indirect path.
Figure 1.
A constructed four-state routine: arrows give transition probabilities, and the two absorbing outcomes have different eventual probabilities and waiting times.
Details.
Let be the terminal hitting time. Write for the absorption probability and for the expected hitting time, with the subscript denoting the starting state. First-step analysis gives
Here , , and . Solving these two pairs of linear equations yields
Starting at therefore ends at with probability and takes steps on average to reach either terminal state. The terminal hitting time counts the transition into the outcome, but no later self-transitions. Outcome and duration answer different questions: from , outcome is less likely, yet termination is faster on average.
The matrix power gives the probability distribution after two steps from as
Thus , and the probability of having already reached is , still below its eventual absorption probability . From either unfinished mode, each next step has terminal probability at least . Consequently , proving termination almost surely and finite expected hitting time directly. The Fundamental matrix of a finite absorbing Markov chain packages both calculations and counts visits to unfinished modes.
For a finite, time-homogeneous Discrete-time Markov chain, state is accessible from when some finite path of positive transition probabilities leads from to . Equivalently, for some , allowing a zero-step path when . 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, despite , because ; fails at every step count.
Closed communicating class Created 2026-09-24 Updated 2026-11-05
A Communicating class is closed when no transition from it can reach a state outside it.
Communicating class Created 2026-09-24 Updated 2026-10-14
In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , write when is accessible from , meaning for some . States communicate, written , when both and . Communication is an equivalence relation, and a communicating class is an entire equivalence class
Thus 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: , the identity matrix, makes true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from to with one from to , 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 for every and . 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.
Figure 1.
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.
Details.
For this constructed example, in state order , the transition matrix is
There are exactly three communicating classes: , , and . Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although via , the reverse accessibility fails. A direct matrix power check gives and .
Starting at , let be the first hitting time of either closed class. Staying at for steps has probability , so and . The two eventual destination classes each have probability . Hence the hitting probability of the absorbing state is only , and its unconditional expected hitting time from 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 is an irreducible Markov chain with period two; the restriction to 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.
Irreducible Markov chain Created 2026-09-24 Updated 2026-10-25
For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , irreducibility means
Equivalently, all states form one communicating class. The step count may depend on ; irreducibility does not require every one-step transition probability to be positive. Drawing an arrow whenever makes the condition exactly that of a strongly connected directed graph. It is a property of the entire chosen state space, independent of the initial probability distribution.
Irreducibility describes where the Markov chain can travel; aperiodicity describes the possible lengths of return paths. For example, restricting the second diagram in communicating class to its closed pair gives
where is the identity matrix. This Markov chain is irreducible, but each state's period of a state in a Markov chain is two. Every destination is reachable, yet a given destination cannot be reached at every sufficiently large step count. Starting at produces alternating one-time probability distributions. See Hao Wu's MIT lecture 2, irreducibility and periods for the definitions.
Adding a holding probability of a Markov chain at each state, with , gives
The arrows between the two states remain, so the Markov chain remains irreducible. A positive one-step return makes it an aperiodic Markov chain. At , both rows are and for every : the initial state is forgotten after one step. At , however, both states become absorbing states, giving two separate communicating classes and losing irreducibility.
For a finite Markov chain, irreducibility guarantees a unique stationary distribution with positive weight at every state. Adding aperiodicity guarantees convergence for every initial probability distribution; see Hao Wu's MIT lecture 4, convergence theorem. The Markov chain ergodic theorem gives convergence of empirical visit frequencies even for an irreducible periodic Markov chain. These results explain why checking connectivity is a useful first step before studying equilibrium. Conversely, any absorbing state prevents irreducibility if there is another state: it cannot reach that state. The one-state Markov chain is the exception.
Lazy Markov chain Created 2026-09-24 Updated 2026-11-05
Under the usual discrete-time convention, a Lazy Markov chain has holding probability at least at every state. Starting with transition matrix , its standard lazy version is
Toss a fair coin at each step: stay put on one outcome and perform a transition on the other. Every Stationary distribution of is stationary for , because . An irreducible class becomes aperiodic because of its self-loops.
More generally, adding the same holding probability at every state gives and preserves stationary distributions, although the conventional half-holding threshold need not hold. For a reversible chain, half-laziness sends each eigenvalue to , explaining why ordinary and absolute spectral gaps then coincide.
State-dependent holding can change stationarity. Begin with the alternating two-state chain, whose Stationary distribution is . Holding at state zero with Probability and at state one with Probability produces with Stationary distribution . Thus uniform slowing preserves the invariant law; arbitrary extra self-loops need not.
Open communicating class Created 2026-10-06 Updated 2026-11-05
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.
The directed positive-transition graph gives the communicating classes , and . The first and last classes are closed; is open. In particular the PDF's fourth row has all six entries equal to . The converted TeX incorrectly drops the last entry; that incomplete row is not a transition distribution.
The finite irreducible closed class reaches state six almost surely. For example, from every state in there is a uniformly positive probability of hitting six within a bounded number of steps, so the probability of avoiding it for successive blocks tends to zero. Put , with and . First-step conditioning at states two and four gives
Solving and yields , with .
Starting in state three, the chain remains in . In the order its transition matrix is
Its characteristic polynomial is . Thus, by the Cayley-Hamilton theorem, is a linear combination of . The initial values are , , and . Solving for the three coefficients gives
The limiting value agrees with the state-six probability of the stationary distribution of this closed class.
For a state , let and . If distinct states communicate, choose positive-probability paths and of lengths . Then is a return time to each. For every , concatenate , the -return loop, and to see that . Since divides this and , it divides . Thus , and interchanging the states gives . This proves period is constant on a communicating class.
Read the transition matrix from the original PDF; the converted TeX loses the location of the second row's final entry. The communicating classes are
Within the only internal cycle is . Return lengths are multiples of three, and length three has positive probability, so its period is three. This class is open because it has exits to other classes. The class is the closed deterministic two-cycle, of period two. The absorbing class is closed and has period one.
State 5 has outgoing transitions but no incoming transition at all, so it is an open singleton class and . For this return-free state in a Markov chain, the convention gives period zero; if period is defined only when positive return times exist, it is undefined instead. In particular, this singleton is not aperiodic: aperiodicity would require period one.
All four permitted hops have rate one: , , , and . Every state reaches every other, so the only communicating class is , and it is closed.
Figure 1.
Allowed frog hops and their rates
. Details.
Solving , , gives and . Thus
For the transient probability, let . The forward equations and give , . From , . Integrating , with , yields
It has derivative one at zero and tends to , as required.
Communication is reflexive because , and symmetric by its definition. If and , choose positive-probability paths in steps and in steps. The Chapman-Kolmogorov equation gives
Combining the reverse paths gives a positive-probability path as well. Thus communication is transitive and is an equivalence relation.
To transfer recurrence, first establish the recurrence criterion by return probabilities. Put and let under . After each return the Strong Markov property restarts the chain at , so . Therefore
For this equals ; for it is infinite. The expectation identity follows by summing the nonnegative indicators, so remains valid when the expectation is infinite. Consequently is a recurrent state exactly when its return-probability series diverges.
If , choose with and . For every ,
Summing over , recurrence of forces the return-probability series for to diverge. The proved criterion shows is recurrent, so recurrence is a property of the communicating class.
For , the chain has one communicating class exactly when every . Sufficiency follows from the positive direct transition rate between each distinct pair of states. For necessity, if and there is another state, no other state can jump to , either directly or as the final step of a path, so cannot communicate with them. The one-state case also satisfies the condition because . A single class containing the entire state space is automatically closed.
The communicating classes are , and . The class is open: it can reach or and cannot be reached from either. To remain in for two steps has probability , so for . Its states are transient states. All returns within have even length and a two-step return is possible, so their period of a state in a Markov chain is .
The closed communicating class alternates deterministically between and , and therefore consists of positive recurrent states of period . The class is finite, closed and irreducible, so its states are also positive recurrent states. The self-loop at gives period there, and the period is constant on a communicating class, so every state of has period .
For , solve the stationary distribution equations:
Hence . Finite irreducibility and aperiodicity imply convergence to this stationary distribution from any state of . If is the probability of eventually entering , the Markov property gives
so and . Conditioning on the finite entrance time and then letting the remaining time tend to infinity proves that the limiting probabilities in are . The probability of entrance after a large cutoff tends to zero, which justifies this conditioning limit.
For , convergence depends on the parity balance on entry to a period-two Markov class. Entry always occurs at . Starting from , the probabilities of first entry at time and at time are both . Each parity therefore has total probability , so both and tend to , despite the recurrent class being periodic. Starting from , the corresponding odd- and even-entry probabilities are and , with totals and . Consequently
so neither limit exists. From or , the probabilities at and alternate between zero and one; from they are identically zero. Finally every probability of being in tends to zero, from all starting states.
All requested conclusions are encoded below, with denoting a nonexistent limit:
The class classification is : transient, period ; : recurrent, period ; : recurrent, period .
Let be an open communicating class, and fix . There is a path of positive probability from to a state outside . Choose a shortest such path, so it does not revisit before exiting. No state reached outside can have a path back to : combined with the exit path and communication within , such a path would put it in the same communicating class. Thus with positive probability the chain never returns to . Its return probability is less than one, making a transient state. This proves transience throughout .
Conversely, suppose a finite communicating class were both closed and transient. Starting inside it, a path stays there forever. Since it has finitely many states, at least one state must be visited infinitely often. But a transient state is visited only finitely often almost surely, and the union of finitely many exceptional null events still has probability zero. This is a contradiction. Every finite transient communicating class is therefore open.
For the infinite counterexample, take the biased random walk on with independent increments of probability and of probability . All states communicate, so is one infinite closed communicating class. The strong law of large numbers gives almost surely. Consequently every fixed state is visited only finitely often, and the class is transient. Finiteness is exactly what fails in the preceding argument.
States communicate when each is accessible from the other: there exist nonnegative integers such that and . A communicating class is an equivalence class for this relation.
States and communicate when each is accessible from the other: there exist with
This is an equivalence relation, and its equivalence classes are the communicating classes. A class is closed when no positive-probability transition leaves it.
False. On the two-state space, take
Every positive entry of remains positive in . Under , both singleton states are closed communicating classes, so neither state is a transient state. Under , however, state one eventually moves to the absorbing state two and can never return after doing so. State one is therefore transient.
Two states lie in the same communicating class when each is reachable from the other by transitions of positive probability. Inspecting the directed transitions gives three classes:
State 1 has no incoming transition from another state and can leave, so its singleton class is open and transient. More explicitly, the probability of returning to 1 after time zero is only , since a departure can never be reversed.
States communicate: and are positive-probability paths. The class is open because, for example, and leave it; no transition from the class returns to it. Every state of is transient. One can see eventual exit directly: from each of its four states there is a positive-probability path of at most three steps to 8; the minimum of these four path probabilities is positive, so survival through repeated three-step blocks has a geometrically decreasing upper bound.
Finally shows that communicates, and every outgoing transition stays inside it. It is a closed finite irreducible class, so all its states are positive recurrent. Therefore the first two classes are open and transient; the last is closed and recurrent.
The Markov property says that conditional on the present state, the next-state law does not depend on the earlier history. For this time-homogeneous chain, whenever the conditioning event has positive probability.
States communicate when each is accessible from the other by a finite positive-probability path; the equivalence classes are the communicating classes. A class is closed if no one-step transition leaves it, and open otherwise. Probability nonnegativity adds the implicit restriction to the printed upper bound.
At , every state is absorbing, so the classes are the singletons, all closed. For , every neighbouring pair communicates, so the whole state space is one closed class, making the chain irreducible. There are no open classes in either case.
For and , detailed balance along the path gives , , and . After normalization,
For , the self-loops have positive probability; the finite irreducible chain is aperiodic, so for all fixed starting states and targets. For , every step changes parity. The chain has period two, and for each fixed one parity of times has probability zero while . Thus the stated convergence from a fixed starting state holds exactly when . This is the stationary law of a reflecting nearest-neighbor walk on a finite path.
Reading positive entries as directed edges, the communicating class decomposition is
For the first class, paths establish mutual reachability, and every transition from one of these states stays in this set. States 2 and 3 communicate, but state 2 can enter the first class and never return. States 4,6,7 communicate through , but state 6 can enter state 2 with no route back. These paths also exclude any larger communicating class. In a finite Markov chain, the closed class is recurrent and the two open classes are transient.