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 , takeThe 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.
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 givesHere , , and . Solving these two pairs of linear equations yieldsStarting 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 asThus , 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.
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 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: , 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.
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 isThere 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.
Destination-dependent reset chain Created 2026-10-14 Updated 2026-11-05
For jump rates when , assume and . The positive-rate states form the unique Closed communicating class; every zero-rate state is an open singleton. The stationary law is , with Detailed balance . When at least two rates are positive, the embedded jump-chain law is proportional to . With only one positive rate, that state is absorbing and the genuine sequence of jump times stops there; an extended discrete chain can use an absorbing self-loop.
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 isVisit 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.
Five-state harmonic absorption example 2026-10-14
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.
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 giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values and , soFor 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 givesThis is a discrete Poisson equation, in the interior. The extra counts the step just taken. The quadratic valuessatisfy 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 givesThe 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.
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 identityFor 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 givesThe 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
Limiting distribution 2026-10-25
The probability distribution approached in convergence in distribution. It can depend on the initial state of a Markov chain when several closed communicating classes are accessible.
Nonuniqueness of invariant distributions of a finite Markov chain Created 2026-10-03 Updated 2026-11-05
Every Closed communicating class of a Finite Markov chain has its own invariant Probability distribution. All invariant distributions are convex combinations of those class distributions. In particular, a finite irreducible chain has a unique invariant distribution, while a reducible chain may have many.
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.
Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 2 26J d Solution Created 2026-09-24 Updated 2026-10-14
Let , nonempty since . Every pair of distinct states in communicates directly, and no transition leaves for a zero-rate state. Hence is the unique closed communicating class. Each zero-rate state forms an open singleton: it has total departure rate , goes into , and can never be revisited. This includes the case that itself is a single absorbing state.
Past exam of the mathematics course of the University of Cambridge 2008 ib Paper 4 9H Solution 2026-10-14
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 givesso 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 . Consequentlyso 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 .
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 30 1 c Solution Created 2026-10-03 Updated 2026-10-14
There is now no separate rate- clockwise transition. The only transitions areBoth preserve modulo . The initial state therefore selects the closed communicating class , on which . The population is a birth-death process with birth rate and death rate .
Define and for . The detailed balance for a birth-death process weights areWriting with , the product condition gives . Summing the resulting geometric series yieldsThis is also the law in part (b) conditioned on : the ratio of its weights at consecutive accessible populations is . The stability condition is , which uses the product of the periodic birth rates; it does not require for every .
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 2 20H a Solution Created 2026-09-24 Updated 2026-10-06
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.
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 2 20H b iii Solution Created 2026-09-24 Updated 2026-10-06
The only closed communicating class is ; the class is open and transient. Its one-step probability of staying inside is at most , so if is the entrance time into , then for an initial state in . Hence entrance occurs almost surely in finite time.
On it is an irreducible aperiodic Markov chain, because both states have positive self-loop probabilities. The finite irreducible aperiodic countable-state Markov chain convergence theorem says that its transition probabilities converge to its unique stationary distribution. The balance equation with gives and .
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 2 20H b i Solution Created 2026-09-24 Updated 2026-10-06
The states form a closed communicating class. Set . Within this class,Its fixed point is . Subtracting that fixed point and iterating gives the exact transition probability
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 2 27J Solution Created 2026-09-24 Updated 2026-10-14
For the finite state space , the generator or Q-matrix is defined byIts off-diagonal entries are nonnegative jump rates and . The Transition semigroup of a continuous-time Markov chain is .
An invariant distribution of a continuous-time Markov chain is a probability row vector satisfying for every . Differentiation at zero gives ; conversely, implies . ThusInvariant distributions need not be unique: each closed communicating class supports one, and their convex combinations are invariant. A finite irreducible chain has a unique invariant distribution.
Let be the arrival times of the independent rate- Poisson process. The increments are independent exponential variables of rate . Conditional on , the Markov property, time homogeneity, and independence of the next increment giveHence is a discrete-time Markov chain. Its transition matrix is the Poisson-sampled continuous-time Markov chain resolvent
If , then and integration gives . Conversely, if a probability row vector satisfies , multiplyingon the right by yields . Therefore the sampled chain and the original chain have exactly the same invariant distributions.
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 3 8H a Solution Created 2026-09-24 Updated 2026-09-25
States and communicate when each is accessible from the other: there exist withThis is an equivalence relation, and its equivalence classes are the communicating classes. A class is closed when no positive-probability transition leaves it.
DefineAn interior jump cannot go below or above , and every exterior reset lands in . Thus is closed.
To prove that it is one communicating class, start anywhere in . From or , a reset can reach with positive probability. From any state of , repeated steps reach some state of , after staying in up to the last step. A reset from this state can reach every point of the consecutive blockEvery integer has the form for some and an integer . Repeated steps from reach , with all departure states in until a possible last step into . This gives access to all of . Finally, each can be reached from . Every path described has strictly positive probability. Therefore every state in reaches every other state in .
Each state outside can only stay put or reset into , and no transition from returns to it. Different states outside cannot reach one another. Hence the complete list of communicating classes isThe finite class is the unique closed communicating class. The exterior singleton classes are transient communicating classes, since their self-transition probabilities are strictly less than one. Notice that this reachability proof does not require to be coprime.
(b)(i): communicating classes. Every increment is divisible by , so the residue class modulo is preserved. Conversely, if is divisible by , Bézout's identity applied to gives a path just as in (b)(i). Thus the original Markov chain is reducible on , with exactly the closed communicating classesThe specified walk starting at zero stays in .
(b)(ii): period of a state in a Markov chain. The return equation reduces to . Hence , . For every state, the period of a state in a Markov chain is thereforeThis is still at least two, so no state is aperiodic.
(b)(iii): stationary distribution. The conclusion is unchanged: there is no stationary distribution on . The maximum-mass proof in (b)(iii) applies verbatim, without using coprimality. Equivalently, each closed communicating class, after translating and dividing its state labels by , is the same centered random walk with step sizes and has no stationary distribution.
(b)(iv): occupation of zero. On , the rescaled walk has exactly the transition probabilities of the coprime walk with parameters . The return-probability argument in (b)(iv) therefore makes this class null recurrent. The renewal process proof of the occupation limit applies unchanged:Starting in another residue class would make every visit to zero impossible, also giving occupation proportion zero.
(c)(i): modified communicating classes. These are unchanged: is one finite closed communicating class, and all other states are transient singleton classes. The original proof used consecutive reset destinations and never used coprimality. Resetting to the consecutive integers connects different residue classes, so it would be incorrect to split according to residue classes modulo .
(c)(ii): limiting distribution. The column-sum calculation, the irreducible Markov chain property on a finite class, positive self-transition probabilities, and geometric entrance argument also required no coprimality. Thus for every initial state the same convergence in distribution holds:In particular, the denominator is unchanged; it is not divided by .



