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.
A function of the current state of a Markov chain can discard information needed to predict its next value. A sufficient condition preserving the Markov property is strong lumpability: all original states with the same recorded value must give the same transition probabilities to every recorded class.
For the two-column model in growth rate of two-column sticky deposition, the pair of column heights is Markov, but its maximum alone is not. Starting empty, the maximum-height histories and both end at height two. The former leaves unequal columns, so the next height increases with probability ; the latter leaves equal columns, so it increases with probability one. Each history has positive probability. Their different predictions at the same time and current value violate the Markov property. By contrast, the absolute height difference retains exactly the information needed for its own transitions.
Alternative routing Created 2026-10-05 Updated 2026-10-14
Alternative routing lets a call try another resource path when its preferred route is blocked. Overflow onto longer paths can create feedback and multiple solutions of the Erlang fixed point approximation, even though an exact finite irreducible occupancy Markov chain has a unique stationary distribution.
Alternative-routing triangle with three Erlang fixed points Created 2026-10-07 Updated 2026-10-14
On a three-node loss network, each pair offers direct calls of load to its link of capacity . If blocked, the call tries the two-link path through the remaining node. The symmetric reduced-load approximation gives a link its direct load and two overflow contributions , hence the displayed equation. For , , its residual has alternating signs at , giving at least three distinct roots. This multiplicity belongs to the Erlang fixed point approximation, not to the exact stationary law of a finite reachable Markov chain.
Aperiodic Markov chain Created 2026-09-24 Updated 2026-11-05
A state is aperiodic when the greatest common divisor of its positive-probability return times is one. A Markov chain is aperiodic when all its states are aperiodic.
Augmented Markov chain Created 2026-09-24 Updated 2026-11-05
An augmented Markov chain adds state information so that the future depends on the present augmented state rather than an unrecorded part of the past. For a second-order process with , the pairs form a Markov chain. A transition from goes only to pairs . This converts finite-memory dynamics into first-order dynamics, often at the cost of a larger state space.
An average-reward optimal policy maximizes long-run expected reward per time step. In a finite recurrent Markov chain, a stationary policy's gain is its expected one-step reward under the stationary distribution. Initial-state effects are encoded by a bias function rather than by the gain. In a communicating finite control problem, the average-reward Bellman equation certifies a policy that is optimal from every initial state.
Bernoulli-Laplace diffusion model Created 2026-10-25 Updated 2026-11-05
In the Bernoulli-Laplace diffusion model, two urns each contain balls, with red and blue balls in total. Independently choose one ball uniformly from each urn and exchange them. The red count in the first urn is a Markov chain on , with
The upward event exchanges a blue ball from the first urn with a red ball from the second; the downward event reverses the colors. Hence
Starting from , the mean is , with the initial value understood separately if the geometric factor is zero. For , this mean tends to . For , however, the only two configurations alternate and the expected imbalance does not decay.
The Stationary distribution is the hypergeometric distribution
It counts uniformly allocated red/blue configurations. The ratio verifies Detailed balance with the displayed transitions. The chain is irreducible; for an interior holding Probability also makes it aperiodic, while the chain has period two. This model separates convergence of an average imbalance from the full probability law and its periodicity.
Take independent steps, each with probability and with probability . Reverse a step sequence by reading it backward and changing each sign; use the same biased law for both experiments. With positive steps, the forward sequence weight is and its reversed weight is . Their logarithm ratio is
Here is dimensionless entropy production, not an entropy in joules per kelvin. A Markov chain on a three-state ring gives a state-space realization: start uniformly, take a clockwise step with probability and a counterclockwise step with probability . The uniform stationary distribution makes endpoint weights cancel. A physical interpretation as exchanged heat requires local detailed balance with bath entropy per directed step; the abstract model alone specifies path probabilities.
For an allowed value , the binomial distribution gives
This is an exact same-law finite fluctuation theorem, with no long-time approximation. For , and , and . The positive mean is , although the all-negative path has nonzero probability . Directly, .
Figure 1.
Exact biased-step model: discrete entropy-production probabilities and their log ratio at nine steps
. Details.
The left panel shows exact probability masses for , with negative values highlighted; the right panel tests the logarithm ratio against . These are model values, without experimental measurements or simulated measurement noise.
Birth-death chain Created 2026-09-24 Updated 2026-11-05
A Birth-death chain is a discrete-time Markov chain on nonnegative integers that can move only to the same state or a neighbouring state.
Boltzmann machine 2026-10-18
A Boltzmann machine is a stochastic neural network that learns a probability distribution specified by pairwise energies. To compare it directly with a Hopfield network, use the bipolar energy . Here controls the preference for low energy, and the partition function normalizes all states. In a computational model, is an algorithmic inverse temperature; interpreting it as additionally requires physical energy units.
A random single-unit Gibbs sampling update has conditional probability
Indeed, the two possible energies differ by ; their normalized Boltzmann weights give this logistic function. Random selection of one unit at a time satisfies detailed balance. For finite weights and finite positive , all conditional probabilities lie strictly between zero and one, so the finite Markov chain can reach every state and can remain in place. Its unique stationary distribution is . A short run need not yet sample that distribution accurately.
As , a nonzero field selects its sign, approaching asynchronous Hopfield energy descent. At zero field the stochastic rule remains a fair coin, whereas the deterministic convention above retains the old value. At finite inverse temperature, uphill moves permit exploration beyond one local minimum. Recall and learning are different operations: sampling changes the units at fixed weights; learning changes the weights to fit the training data.
For an aperiodic positive Harris recurrent Markov chain with geometric ergodicity, an observable with stationary moment for some satisfies a central limit theorem. Its asymptotic variance is , with stationary covariances. Ergodicity alone does not guarantee this theorem.
Charles M. Grinstead Created 2026-10-14 Updated 2026-11-05
Charles M. Grinstead coauthored Introduction to Probability by Charles M. Grinstead and J. Laurie Snell with J. Laurie Snell. The institutional publication record identifies the1997 second revised edition and its authors.[ref] The text develops probability from concrete models through tools such as conditional probability, expectation and Markov chains. For example, counting length- sequences of independent fair coin tosses gives probability for exactly heads, connecting discrete counting with a probability model rather than treating either in isolation.
Coalescing coupling Created 2026-10-06 Updated 2026-10-14
A coalescing coupling of probability distributions of two Markov chains keeps them identical after a meeting time . The coupling inequality for total variation gives . A uniform bound on , combined with Markov inequality, bounds the mixing time of a Markov chain.
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.
Communicating states Created 2026-09-24 Updated 2026-11-05
Two states of a Markov chain communicate when each can be reached from the other with positive Probability in finitely many steps.
Commute time identity Created 2026-09-24 Updated 2026-11-05
For a finite connected loopless undirected electrical network without killing, give each edge a positive electrical conductance , put , and use transition probabilities , where . Then the commute time identity is
The factor is total electrical conductance, not total electrical resistance. A killed random walk can fail to reach its target and is outside this statement.
Here is a direct proof. Let and define the network operator . First-step analysis gives off . Summing over all graph vertices gives zero, so . Therefore has divergence at , at , and zero elsewhere. Its voltage drop is , which is the effective resistance for unit electric current.
For an unweighted path with edges, and endpoint effective resistance is , giving commute time . Uniformly multiplying all electrical conductances changes and effective resistance inversely and leaves the Markov chain unchanged. [ref]
Conditional mutual information Created 2026-09-24 Updated 2026-10-14
For finite discrete random variables, conditional mutual information measures the average reduction in uncertainty about from observing , when is already known. With base-two logarithms, it is measured in bits:
The second expression follows from the chain rule for conditional entropy and makes the symmetry in visible. Equivalently, compute the mutual information separately in each conditional probability distribution and then average:
Here is the Kullback-Leibler divergence, also computed with base-two logarithms; zero-probability terms contribute zero. The Gibbs inequality gives , with equality exactly when and have conditional independence given : the conditional joint probability mass function factors for every of positive probability.[ref]
For a fully computed example, take independent random variables that are fair bits, and let , where is exclusive or. The complete joint probability distribution has only these four positive entries:
Table 1.
Joint probabilities for two independent fair bits and their exclusive or
.
Every pair has probability , so . But . Given , the pairs each have conditional probability , while both conditional marginals are fair. Thus
Given , the pairs give the same calculation. Therefore
The conditional entropy calculation tells the same story: because either value of leaves fair, whereas because . Learning the exclusive or does not reveal either bit alone; it reveals whether they agree, so learning one then determines the other.
Figure 1.
Conditioning on the exclusive or reveals one bit of dependence between independent fair bits
. Details.
This example distinguishes conditional independence from ordinary independence. It also disproves the claim that conditioning always reduces mutual information, despite conditioning reduces entropy. There is no general ordering between and : the example above increases it from zero to one, while taking and for a fair bit decreases it from one to zero. The chain rule for mutual information explains why both are possible.[ref]
Conditional mutual information is useful for asking whether an additional observation tells us anything after information already available has been accounted for. Its zero case expresses conditional independence exactly; in a Markov chain, this is the step that turns the chain rule for mutual information into the data processing inequality.