Absorbing Markov chain 2026-10-20
A Markov chain with at least one absorbing state, such that from each state an absorbing state can be reached. In a finite such chain, absorption occurs with probability 1. Expected times to absorption satisfy a linear system obtained by conditioning on the first transition.
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.
Absorption time 2026-10-25
For a discrete-time Markov chain and a set of absorbing states, its absorption time is the hitting time . It is zero when the initial state already lies in , and infinite on a sample path that never enters . Finiteness almost surely need not imply a finite expected value. For a finite-state model, a uniform positive probability of absorption within a fixed number of steps gives a geometric series bound on the survival probabilities and proves that the mean is finite. The mean absorption time of a lazy symmetric random walk is an explicit example.
Acyclic Markov chain Created 2026-10-20 Updated 2026-11-05
On a finite state space, an acyclic Markov chain has no directed cycle among its nonabsorbing states. Order those states topologically by their possible transitions. Hitting probabilities and expected absorption times can then be calculated in reverse order, because a state's equations involve only later states.
For example, let go to or to an Absorbing state with equal probabilities, and let go directly to . The expected absorption times are , and . This is dynamic programming on the transition graph, rather than a general simultaneous linear solve.
If a convention permits self-transitions while forbidding cycles between distinct nonabsorbing states, the holding probabilities must be retained. Provided , the same backward calculation uses
A self-loop at of Probability , with probabilities each to , gives instead of . The finite-state assumption is substantive: an infinite deterministic chain is acyclic but has no terminal Absorbing state and no finite reverse recursion of this kind.
Birth-death recurrence classification Created 2026-09-24 Updated 2026-11-05
Consider a birth-death process on with constant birth rate , constant death rate at every positive state, and no deaths from zero. The reflecting boundary is essential: the result changes if zero is an absorbing state. Detailed balance would give
When , these weights normalize to a Geometric distribution, so the irreducible chain is positive recurrent. When , the embedded jump chain is the symmetric reflected random walk: it returns to zero almost surely, but its constant equilibrium weights have infinite sum, so the chain is null recurrent. When , its upward-biased embedded random walk has probability of hitting zero from state one, making the chain transient. The holding rates are bounded, so nonexplosion creates no additional qualification here.
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.
Cyclic imitation chain Created 2026-10-14 Updated 2026-11-05
In a population of playing rock paper scissors, let losers copy winners. With pair-selection events of rate , the proportion process has jumps , , at rates , , . Its fluid limit obeys , with indices interpreted cyclically. The product of numbers is conserved in this ordinary differential equation, whereas the finite chain eventually reaches a monochromatic absorbing state.
Diffusion approximation of a birth-death process Created 2026-09-24 Updated 2026-11-05
A birth-death process with unit upward and downward jumps and rates and has infinitesimal generator
If varies slowly over one jump, Taylor expansion through second order gives . Thus its diffusion approximation has drift coefficient and, in the convention
diffusion coefficient . Equivalently it solves , where is Brownian motion. The sum measures the variance of the short-time increment: births and deaths both add noise even when their mean drifts cancel.
For a population density with jump size and birth/death rates , the drift is and the diffusion coefficient is . Fluctuations therefore shrink as . A useful approximation requires many reaction events while the rates change little; it can fail near an absorbing state or when only a few individuals remain. A continuous diffusion can even visit negative values unless its boundary treatment is specified. The approximation replaces the discrete jump model rather than asserting equality of their laws.[ref]
Equilibrium distribution of a continuous-time Markov chain Created 2026-10-14 Updated 2026-11-05
An Equilibrium distribution of a continuous-time Markov chain is a probability row vector invariant under its transition semigroup:
It satisfies when the generator sums are defined. An invariant law is a property of the entire evolution, so formal generator equations must be interpreted with the process's nonexplosion and domain conditions.
For a finite irreducible chain, the equilibrium distribution is unique and every transition row converges to it. For a general finite chain, the limiting row from state is a mixture of the stationary distributions of its closed irreducible classes:
The chain eventually enters one of these classes and then mixes within it. If every closed class is a single absorbing state, this reduces to absorption probabilities at those states. Merely having some absorbing states does not exclude other closed classes.
Holding times explain the link to an embedded jump chain. For a finite irreducible chain with strictly positive exit rates and jump-chain Stationary distribution , the time-stationary distribution is
Visit frequency is multiplied by mean time per visit. In the countable setting, these time weights need a finite positive normalizer and a nonexplosive process before they define an equilibrium probability. For an alternating two-state jump chain, and rates give : slower holding rates increase time occupancy.
Extinction probability of a branching process Created 2026-10-07 Updated 2026-10-14
For a Galton-Watson process with one ancestor, the branching extinction probability is the probability that some generation is empty:
The equality uses the absorbing state at zero. The complementary branching survival probability is the probability that every generation is nonempty. The Galton-Watson extinction fixed point computes from the offspring distribution.
For , , one ancestor has . Starting instead from ancestors with independent descendant families gives
All families must die out. With three ancestors, eventual extinction has probability and survival has probability ; by generation two, extinction has probability . Extra ancestors change the extinction probability without changing the offspring distribution. [ref]
For finite offspring mean , the extinction classification is:
  • If , extinction has probability . For example , gives and ; its only fixed point in is .
  • If and , extinction also has probability . For example gives and , despite expected generation size in a Galton-Watson process remaining one.
  • If , extinction has probability . The value can be zero: if , every individual has at least one child, so an initially nonempty family never becomes empty. In particular gives and .
The critical exception is : every individual has exactly one child, , and forever from one ancestor. Thus but ; a blanket claim that every critical Galton-Watson process becomes extinct would be false. These cases concern the Galton-Watson process with its common offspring distribution and independence assumptions. [ref]
This probability answers whether any lineage persists, which the offspring mean alone cannot quantify in the supercritical case. A branching process conditioned on extinction uses the same fixed point to reweight reproduction and describe families known eventually to die out.
Take a birth-death chain on . At each interior state, move up one state with probability and down one state with probability . The endpoints are absorbing states: . This is a small gambler's ruin model in which the state can represent capital, and reaching is success.
Figure 1.
Five states with fair interior transitions and absorbing endpoints; each displayed value is the probability of reaching 4 before 0.
Details.
Let be the hitting time of endpoint , and let be the first endpoint hitting time. The desired hitting probability is . First-step analysis and the Markov property give
The interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values and , so
For example, from state the hitting probability is , and its one-step average is . Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.
Now ask how long it takes to reach either endpoint. The expected hitting time counts steps, including the transition that first reaches an endpoint. First-step analysis gives
This is a discrete Poisson equation, in the interior. The extra counts the step just taken. The quadratic values
satisfy the equations; from state , steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.
For a biased random walk with upward and downward, keep the same absorbing states. The interior harmonic equation becomes . Using biased gambler's ruin probability with these boundary values gives
The three interior hitting probabilities are approximately , , and . Thus starting at now succeeds about of the time. A direct check is . The curved profile reflects the unequal transition weights: its successive increments shrink by the factor . The formula, with the endpoint denoted there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.
Figure 2.
Hitting 4 before 0 for fair and upward-biased walks, compared with the fair walk's expected number of steps to either endpoint; lines join discrete state values.
Details.
Why does harmonic averaging produce the correct hitting probability? With the natural filtration , the Markov property gives the conditional expectation identity
For a function harmonic everywhere, this makes a martingale whenever it is integrable. For a function harmonic only in the interior, is a stopped martingale. In either five-state example, . Also, from any interior state at most three consecutive upward steps reach , with probability at least . Repeated three-step blocks give , so is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at and then the bounded convergence theorem gives
The boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.
Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.
// Target: markov-process.bigb
For a finite Markov chain in which an absorbing state is accessible from every state, order the nonabsorbing states first and write
Here is the identity matrix and is the matrix inverse of . With the first hitting time of the absorbing set,
Thus gives the expected occupation count before absorption, including the initial visit; is the absorption probability of state ; and is the expected hitting time of the absorbing set. The vector has every entry one. See Grinstead and Snell, section 11.2, theorems 11.4-11.6.
For the toy routine in absorbing state, direct matrix multiplication gives
The first row of says that starting at gives visits to and to before termination. Their sum is the mean duration . The identities , , and independently verify the inverse, outcome, and duration calculations. The absorbing set must be reachable from every state for these finite formulas: applying them to all nonabsorbing states in the closed-cycle example would leave a persistent cycle in and make singular.
Galton-Watson extinction fixed point Created 2026-09-24 Updated 2026-10-14
For a Galton-Watson process with one ancestor and offspring probability generating function , the branching extinction probability is the smallest fixed point of in . A direct way to find it is to compute extinction by generation :
Zero is an absorbing state, so extinction by generation is exactly the event . [ref]
For , the equation is
Both and are fixed points, but iteration from zero selects . The first values are , , , and . Iteration started at would stay at forever and would give the wrong extinction answer for this offspring distribution.
Figure 1.
The smallest extinction fixed point selected by iteration from zero
. Details.
The vertical steps in the figure apply the offspring probability generating function; horizontal steps return to the diagonal to start the next iteration. This gives a useful numerical calculation even when solving explicitly is difficult. For the displayed law, every finite iteration is a lower bound for the eventual branching extinction probability; at generation six, about additional extinction probability remains beyond the current empty families.
Why the smallest fixed point? The ancestor's children's descendant families are independent; given children, all are empty generations later with probability . Averaging gives . The increasing extinction events give the limit , and continuity of the probability generating function yields . For any other fixed point , and monotonicity of imply at every step; hence . [ref]
Galton-Watson process Created 2026-09-24 Updated 2026-10-13
A Galton-Watson process is a branching process that counts individuals by generation. Start with one ancestor, , and let all offspring counts be independent and identically distributed random variables taking nonnegative integer values with a common offspring distribution. Then
The empty sum is zero: zero is an absorbing state, so once a generation is empty every later generation is empty. The same offspring distribution applies to every individual in every generation. [ref]
For a concrete offspring distribution, take , , , and for . An individual has no children with probability , one with probability , and two with probability . The offspring expected value is . A possible sequence of generation sizes is : two children need not lead to a permanently growing family.
The probability generating function gives the exact generation probability distributions through branching-process generating-function iteration. With and , the second generation has
Thus and . The figure shows full generation probability mass functions, computed by polynomial function composition, through generation six; no simulated frequencies are used.
Figure 1.
Exact Galton-Watson generation distributions: growing means and increasing extinction mass
. Details.
The contrast is striking: the expected generation size in a Galton-Watson process grows as , while the branching extinction probability is . By generation six, although . Larger surviving families carry the rising expected value; that mean is an average over possible families, not a forecast of one family's path. The Galton-Watson extinction fixed point turns an unbounded number of future generations into a single equation for this probability.
The historical question was the disappearance of surnames passed through male descendants. In Watson and Galton, On the Probability of the Extinction of Families, pages 139–140, Francis Galton formulates a constant-law model counting sons who reach adulthood, and Watson computes later generation probability distributions by composing generating functions. Those are assumptions of their model, rather than a claim that actual human reproduction follows this offspring distribution.
Gillespie algorithm Created 2026-09-28 Updated 2026-11-05
The Gillespie algorithm samples statistically exact trajectories of a well-mixed chemical reaction network modeled by a continuous-time Markov chain. At copy-number state , each reaction propensity function is a nonnegative event rate and each stoichiometric vector specifies the update. Assume the rates have no explicit time dependence. Put . If , no further chemical reaction can occur: the state is an absorbing state.
For , sample a waiting time from the exponential distribution with rate , independently choose channel with probability , and update . Recompute the reaction propensity functions and repeat. The no-event probability is because ; multiplying by gives the joint waiting-time/channel probability density function . This factorization explains the two draws.[ref]
For with reaction propensity function , the waiting time has mean , and is an absorbing state. Exactness concerns the specified chemical master equation; spatial mixing errors and explicitly time-varying rates require a different model or sampling rule.
Harmonic function for a Markov chain Created 2026-10-14 Updated 2026-10-20
A harmonic function assigns a value to each state of a Markov chain such that one transition leaves its expected value unchanged. This turns a question about many possible future sample paths, such as which endpoint is reached first, into a local averaging rule. For a transition matrix , a real-valued function is harmonic at state when
Here means expected value conditional on starting at ; on a countable state space the sum must be absolutely convergent. If this holds at every state, write . At an absorbing state the equation is automatic, so prescribed boundary conditions supply information that the averaging rule cannot.
For a finite Markov chain, choose a boundary set that can be reached from every state, and assign boundary values . If is its first hitting time, the harmonic extension is
Choosing to be the indicator function of one target within gives a hitting probability. This is a discrete Dirichlet problem: enforce the averaging rule outside and fix the values on . See Hao Wu's MIT lecture 8, harmonic extension, slide 5. The construction extends the mean-value idea of a harmonic function; for a random walk on a graph it is a discrete harmonic function.
The holding rate at state of a continuous-time Markov chain with generator matrix is
For a conservative chain with finite , its holding time has exponential distribution: and . Conditional on a jump, the next state is with probability . Thus the rate determines when departure occurs, while normalized outgoing rates determine where it goes.
If the outgoing rates are and for two distinct other states, the total rate is five, the mean holding time is , and departure chooses them with probabilities and . A zero rate gives an absorbing state with infinite holding time. Statewise finite rates alone do not rule out explosion of a continuous-time Markov chain.
Holding time Created 2026-09-29 Updated 2026-11-05
The holding time of a continuous-time Markov chain is the time spent in its current state before the next jump. For it has an exponential distribution of total outgoing rate ; at an absorbing state with it is infinite.
Invariant measures of the two-dimensional voter model Created 2026-10-14 Updated 2026-11-05
In a nearest-neighbor voter model on the square lattice, any two ancestral coalescing random walks meet almost surely. For an invariant probability measure of a Markov process, the disagreement probability is constant in time but bounded by the vanishing probability of noncoalescence. Hence every pair of sites agrees almost surely. Countability concentrates the measure on the two constant configurations; both are absorbing state, so every mixture of their Dirac measures is invariant. Translation invariance need not be assumed.
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.