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.
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.
Binary Markov source 2026-10-14
Take the alphabet , fair initial bit , and transition matrix
The stationary distribution is . Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability . For , repeating the previous symbol is the better one-step prediction; for , predicting its opposite is better. The resulting minimum next-symbol error probability is , compared with when no history is used.
Given either state, the next-symbol information entropy is . Thus
At , the best next-symbol prediction succeeds with probability , and the entropy rate is about bits per symbol. The adjacent symbols share mutual information bits. This is useful structure even though the single-symbol counts reveal no bias.
Figure 1.
A persistent fair-bit source reveals its new randomness through the flip sequence
. Original simulated sample paths with a fixed random seed. The top row is a stationary binary Markov source with ; the middle row records innovations in a binary Markov source, marking whether each symbol differs from its predecessor. The bottom row is an independent fair-bit comparison. The marginal theoretical probabilities are for both displayed source processes; finite empirical counts need not be exactly equal. These traces illustrate the stipulated models and are not measured data or a proof of the entropy rate. Details.
At , the random initial bit is repeated forever; at , it alternates forever. Both have and zero entropy rate. At , the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.
Here , , and the upward step is either a birth or immigration, the latter having conditional probability . At zero immigration occurs with probability one. Put , and . The stationary weights of a reflected birth-death chain are
Their successive ratio tends to , so they are summable for . For , makes the weights strictly increasing, ruling out a stationary distribution. Thus positive recurrence holds exactly for . In that case the binomial series gives , and
Every step reverses parity and a two-step return has positive probability, so the period of a state in a Markov chain is two. Starting at zero, , whereas .
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.
Brownian zero mode of a fluctuating interface Created 2026-10-05 Updated 2026-11-05
An unpinned uniform height driven by Gaussian white noise is Brownian motion. Its variance grows as and it has no stationary distribution on the real height axis for . Indeed, a stationary characteristic function would obey , incompatible with continuity at zero. Quotienting out the uniform height can still leave stationary shape fluctuations.
Burke theorem for an M-M-infinity queue Created 2026-09-24 Updated 2026-11-05
In stationarity, the departure process of an queue is a Poisson process of rate . By time reversibility, the departures before any fixed time are independent of the occupancy at that time.
Burn-in 2026-10-20
The initial segment of a Markov chain Monte Carlo run discarded to reduce dependence on its starting state. A fixed discarded count is a choice to assess using Markov chain Monte Carlo convergence diagnostics, not a proof that the retained sample has reached its stationary distribution.
Canonical paths comparison theorem Created 2026-09-28 Updated 2026-11-05
The Canonical paths comparison theorem transfers a spectral-gap estimate from a reference Reversible Markov chain to another chain by routing reference transitions along allowed target transitions. Let and be finite reversible transition matrices with the same positive Stationary distribution . For every ordered pair with and , choose a path from to using positive transitions. Let count occurrences of a directed edge and put
Then for every real-valued function . Indeed, telescope along the path and apply the Cauchy-Schwarz inequality, multiply by , and sum over ordered pairs. Collecting the contribution of each directed edge gives the stated capacity-normalized congestion.
The variational Poincare inequality for a reversible Markov chain now gives for the ordinary spectral gaps. Choosing the reference chain gives and , recovering the Canonical paths Poincare bound. This makes a local-transition chain comparable to a chain that resamples its entire state in one step. The common invariant distribution and directed-edge counting convention are part of this formulation.
Conductance profile 2026-11-05
The conductance profile records bottlenecks at different stationary sizes in a finite irreducible Markov chain with at least two states. With stationary distribution and stationary flow , one convention is
This domain ensures that the minimizing family is nonempty. Other normalizations use the smaller side of a cut, so a convention must accompany a quoted profile.
For a lazy nearest-neighbor walk on an -cycle, holding with probability , a consecutive block of vertices has boundary flow and stationary mass , hence conductance . A profile therefore reveals how bottlenecks change with set size rather than retaining only one global minimum.[ref]
In the consecutive-clearance inspection model, a run of consecutive good items is required to leave full inspection. With , , its Markov chain has transitions , for , and , . Thus every defect in the clearance phase resets the count, rather than preserving the cumulative total.
Writing , the stationary distribution is
To prove this, balance at gives , while balance at gives . Summing the geometric series and normalizing gives ; balance at zero follows as well. The inspected fraction is . The fraction of all production that is both defective and uninspected is ; the fraction among defective items alone is . All these long-run limits follow from the Markov chain ergodic theorem and the independent inspection coins. The distinction from cumulative clearance matters already at .
Continuous-time Markov chain Created 2026-09-24 Updated 2026-11-05
A Continuous-time Markov chain on a finite or countable state space is specified by transition rates for , with finite total exit rate . At a state with , it waits an exponential time of rate and then moves to with probability . A state with is absorbing: it has infinite holding time rather than a zero-rate exponential waiting law.
Its transition-rate matrix is , with off-diagonal entries and diagonal entries , so each row sums to zero. The rates describe first-order transition probabilities: for . On a finite state space, the transition semigroup is and explosion is impossible. On a countably infinite state space, finite individual exit rates do not alone exclude infinitely many jumps in finite time; nonexplosion must be checked separately.
For two states with rates and , the mean holding times are and . Detailed balance gives Stationary distribution , and
This starts at one and relaxes to the stationary mass of state zero. Changing holding rates can preserve an embedded jump chain while changing the proportions of elapsed time spent in its states.
To see why continuous time removes periodicity, fix . Every finite sequence of Markov chain states connected by positive transition intensities has positive probability of finishing before , followed by no further transition until . Consequently the transition matrix has positive entries between every pair of communicating Markov chain states, including its diagonal. It is an irreducible Markov chain and an aperiodic Markov chain with stationary distribution . The countable-state Markov chain convergence theorem gives convergence at times , also in total variation distance. For , , applying contracts total variation distance and preserves , giving the full continuous-time limit.
For an irreducible Markov chain on a finite or countable state space, a positive recurrent state implies a unique stationary distribution . If the chain is also an aperiodic Markov chain, its transition probabilities satisfy the displayed limit for every pair of states. The same limit holds from any initial probability distribution by bounded convergence. Positive recurrence cannot be omitted in the countably infinite case, and aperiodicity is required for ordinary, rather than averaged, convergence. This is the standard discrete-time convergence theorem; the finite-state statement alone does not cover unbounded renewal countdowns.
Countable-state Markov chain ergodic theorem Created 2026-10-25 Updated 2026-11-05
For an irreducible Markov chain on a countable state space with positive recurrence and stationary distribution , the displayed almost sure convergence holds from every initial state whenever . In particular, the empirical fraction of visits to converges to . No aperiodicity is needed. Regeneration at successive returns to a state reduces the result to the strong law of large numbers for independent excursion lengths and rewards. This extends the finite-state Markov chain ergodic theorem.
Cutoff for Markov chains Created 2026-09-24 Updated 2026-11-05
A sequence of chains exhibits cutoff when its distance from stationarity drops from near one to near zero in a time window negligible compared with its mixing-time scale.
David A. Levin Created 2026-10-13 Updated 2026-11-05
Coauthor of a textbook on Markov chains and mixing times. The subject asks how repeated random transitions approach a stationary distribution and how rapidly initial-state information is lost.[ref]
Detailed balance Created 2026-09-24 Updated 2026-11-05
For a Markov chain with transition matrix , Detailed balance with a probability distribution means
The left side is the equilibrium Probability of the directed transition ; Detailed balance equates it to the reverse flow. Summing over gives , so Detailed balance implies stationarity. Under the stationary initial law, repeated application of the pairwise identity equates a finite path's Probability to that of its reversal, establishing reversibility.[ref]
For example, take
The off-diagonal flows are both , which verifies Detailed balance and the Stationary distribution directly. A directed three-state cycle has a uniform Stationary distribution but no reverse transitions, so it is not reversible. Stationarity alone therefore does not imply Detailed balance, and Detailed balance alone does not imply rapid convergence.
Detailed balance without rapid convergence Created 2026-10-25 Updated 2026-11-05
Detailed balance does not imply that a Markov chain is an irreducible Markov chain: the identity transition matrix is reversible for every probability distribution. Even for an irreducible Markov chain with aperiodicity, the two-state matrix with diagonal and off-diagonal , , has uniform stationary distribution and nontrivial eigenvalue . From either fixed state its total variation distance after steps is , so convergence can be arbitrarily slow. Invariance, reachability and mixing time are distinct questions.