Absolute relaxation time 2026-10-06
For a finite irreducible Markov chain with at least two states that is an aperiodic Markov chain and a reversible Markov chain, put and . This is the reciprocal of the absolute L2 spectral gap of a reversible Markov chain. It agrees with the reciprocal of the ordinary spectral gap for a lazy Markov chain, but need not agree when there are negative eigenvalues.
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.
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 , withThe upward event exchanges a blue ball from the first urn with a red ball from the second; the downward event reverses the colors. HenceStarting 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 distributionIt 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.
Suppose a Markov kernel satisfies for a measurable . For and , the sublevel set gives . If is a small set, this is a geometric drift condition. The hypotheses of an irreducible Markov chain and an aperiodic Markov chain are also required for the usual geometric ergodicity theorem.
A countable nonexplosive continuous-time Markov chain which is an irreducible Markov chain and has an invariant distribution is positive recurrent; its transition probabilities tend to from every initial Markov chain state.
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.
Convergence to an invariant distribution Created 2026-09-24 Updated 2026-11-05
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.
Fixed-temperature law of simulated annealing 2026-10-18
On a finite state space with finite objective function values, the fixed- target is a Boltzmann distribution:The partition function normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric and ,Summing over gives , so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing by ensures this. For asymmetric , require connectivity through bidirectional proposals: one-way proposals are rejected.[ref]
In the five-state barrier example for simulated annealing, gives exact Boltzmann weights . Multiplying by givesFor the uphill edge, detailed balance is visible numerically:Thus the global minimum has the largest individual stationary probability, , but is far from certain at this positive . At the exact stationary distribution is .
Lower temperature concentrates equilibrium weights while suppressing uphill acceptance
. Exact Boltzmann distributions for the chosen five-state objective function, and the uphill acceptance probability conditional on the proposal . The one-step transition probability is half that acceptance probability. The bars describe equilibrium at each fixed temperature, not the evolving probability distribution during cooling. Details.For any finite , let be the set of global minima and the smallest objective function value. Cancelling from numerator and denominator shows that each nonminimal state's weight tends to zero as , while every state in has equal weight. Therefore tends to the uniform distribution on . This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.
Hitting time of the bridge vertex between two cliques Created 2026-10-06 Updated 2026-11-05
For simple random walk on two disjoint complete graphs of size joined through one new vertex , let be the expected hitting time of from either vertex attached to , and the expected hitting time from any other clique vertex. First-step analysis gives and , so and . The expected hitting time from is zero. In discrete time the random walk is an aperiodic Markov chain only for .
Immigration chain with complete population resets Created 2026-10-31 Updated 2026-11-05
Fix . The immigration chain with complete population resets has states : from zero it moves to one, and from a positive state it moves to zero with Probability or to with Probability . Its Stationary distribution isStationarity gives and for . Summing the geometric tail yields total mass , giving the normalization.
Every state communicates with zero, and a return from zero takes one initial step plus a positive-support geometric waiting time of mean . Thus the chain is irreducible and positive recurrent. Return lengths two and three have positive Probability, making it aperiodic. The ergodic occupation fraction above a positive integer is the stationary tail .
The endpoint cases have different behavior. At , the closed class alternates deterministically and is periodic; the full countable chain is not irreducible. At , the chain increases forever and the displayed zero weights do not normalize. The strict parameter interval is therefore needed for the irreducibility and aperiodicity claims.
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 meansEquivalently, 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 giveswhere 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 , givesThe 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 isToss 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.
Markov chain ergodic theorem Created 2026-10-14 Updated 2026-11-05
For an irreducible finite Markov chain with stationary distribution , the fraction of visits to any state converges almost surely to , for every initial state. More generally, the empirical average of a function of the state converges to its average under . Aperiodicity is needed for convergence of the one-time distributions, but not for this empirical-frequency conclusion. Regeneration at returns to a state proves the conclusion by applying the strong law to independent excursion lengths and excursion rewards.
Noisy voter model Created 2026-10-03 Updated 2026-11-05
The Noisy voter model combines copying with spontaneous opinion changes. On a finite connected undirected graph with vertices, give each vertex a spin in . At each discrete step choose a vertex uniformly. With Probability , replace its spin by an independent fair bit; otherwise copy a uniformly chosen neighbour. This is a Markov chain on spin configurations.[ref]
Positive noise makes the finite chain irreducible: a sequence of refreshes can produce any configuration with positive Probability. There is also a positive holding probability, so it is aperiodic and has a unique Stationary distribution. At zero noise, the two consensus configurations are absorbing; they cease to be absorbing under positive noise.
A weighted coupling explains convergence even when the graph is not regular. Let be the simple-random-walk transition matrix and its Stationary distribution. For two spin configurations use the weighted Hamming distanceCouple the two chains with the same updated vertex, refresh decision, fresh bit and copied neighbour. If is the current disagreement indicator, the expected one-step change in issince . Thus . With , a remaining disagreement costs at least , so coupling with a stationary chain yields worst-case total variation distance at most . The time here counts single-vertex updates; switching to a rate-one clock at each vertex changes time by a factor of .
Past exam of the mathematics course of the University of Cambridge 2007 ib Paper 2 20C Solution Created 2026-09-24 Updated 2026-10-14
Let be independent with for . The transition law is realized by the geometric-arrival single-service queueThe chain is an irreducible Markov chain: repeated zero arrivals reach zero from every state, and any state can be reached from zero in one step. It is an aperiodic Markov chain because the zero state has self-transition probability .
Starting with one customer, serve one customer per step and regard the arriving customers as that customer's offspring. The number of steps until the queue empties is the total progeny of a Galton-Watson process with offspring probability generating functionHere is the extinction argument needed for recurrence. The probability of extinction by generation is : condition on the first generation and iterate. These probabilities increase to the smallest fixed point in . The fixed-point equation has roots and . Thus the queue started at one hits zero almost surely when , but with probability only when .
If , every finite initial queue empties almost surely, since it represents finitely many family trees. Starting from zero, the first step gives a finite , so the return probability to zero is one. If , the first step has positive probability of producing one customer, whose probability of never emptying is positive; thus the return probability is below one. Communication in this irreducible Markov chain then makes every state a transient state.
For , the expected total progeny from one customer issince conditioning on a generation gives . Nonnegativity justifies interchanging the expectation and sum. For this equals . After the first step from zero the mean number of initial customers is , so the mean return time isThe chain is therefore positive recurrent. At extinction still occurs almost surely, but the expected progeny, and hence the mean return time, is infinite. The chain is null recurrent.
For the stationary distribution in the positive recurrent case, let . Stationarity and the transition realization implyMultiplying through and factoring givesNormalization yields . Expanding the geometric series gives the complete classification and invariant probabilities:For the ratio cannot define a summable probability distribution, consistently with the absence of a stationary probability law. The displayed recurrence proof distinguishes the critical null recurrent case from the transient case; failure of normalizability alone would not do so.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 45 4 Solution Created 2026-10-03 Updated 2026-10-14
Let be the discount level during policy year , with . Under the usual assumption of independent successive annual accidents and repair costs with the same laws each year, the submitted-claim decision depends only on and that year's cost. Consequently the conditional distribution of depends on the past only through : this is the Markov property. The no claims discount system is therefore a time-homogeneous Discrete-time Markov chain. Stationarity of accident probabilities alone, without this independence assumption, would not by itself establish the Markov property.
At level one a claim keeps the policyholder at one, while no submitted claim moves them to two. At level two, a submitted claim moves them to one and no claim to three. At level three, a claim moves them to two and no claim keeps them at three. Thus in the specified transition matrix is the annual probability of a submitted claim at current level , not merely of an accident. A small accident paid privately counts as no claim for these transitions.
Let denote the undiscounted annual premium. It is not specified numerically in the source; costs can instead be measured in units of that premium, giving . The actual premium payments at the three levels are , , and . Compare the two future paths, assuming no further accidents, to obtain the two-year premium-loss claim threshold. From level one, a current claim leads to future levels , whereas no claim leads to , giving extra premiumFrom level two the two paths are and , and from level three they are and . HenceThese are all strictly positive. The PDF's discount fractions are and ; the converted TeX has lost these factors in the percentages.
For a repair cost with the specified lognormal distribution, . Putwhere is the standard normal distribution function. Conditional on an accident, the submitted-claim probability is . Multiplying by the accident probability givesSet for the premium-unit convention. Without a monetary premium scale, discount percentages alone cannot determine a numerical threshold for a monetary repair cost.
This nearest-neighbour Markov chain is a finite birth-death chain. Its stationary distribution satisfies the endpoint balance equationsThese detailed balance equations also imply the middle-state balance equation. The three-level no claims discount equilibrium is thereforewhereSince each lies strictly between zero and one, this is an irreducible Markov chain. Positive holding probabilities at the endpoints also make it an aperiodic Markov chain. Its unique stationary distribution is the limiting distribution even from the initial level one, and gives the steady-state proportions for a homogeneous population of such policyholders.
A submitted claim at level one conditions the repair cost on . The accident probability cancels in this conditional expectation. For , the truncated lognormal moment follows by completing the square:Dividing by yields the expected size of an actual submitted claim:The unconditional expected amount paid per year from level one would instead multiply its tail first moment by ; it is not the conditional claim size requested here.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 6 i d Solution Created 2026-10-03 Updated 2026-10-06
Apply the Monte Carlo estimator to the observable :The theoretical justification is the ergodic theorem for a positive Harris recurrent Markov chain, not an independent-sample law of large numbers. The Markov chain has finite state space, is irreducible, and has the strictly positive posterior distribution as invariant law, so it is positive recurrent and Harris recurrent with counting measure. The observable is bounded: . Thus the estimator converges almost surely to the posterior expected value from any initial configuration.
Each state also has positive self-transition probability, so the chain is an aperiodic Markov chain. Finiteness then gives geometric convergence and the relevant central limit theorem; serial dependence determines the Markov chain Monte Carlo asymptotic variance if error bars are required. A fixed finite burn-in can be discarded without changing consistency, but independence of the retained states should not be assumed.
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 2017 ib Paper 2 20H c Solution Created 2026-09-24 Updated 2026-10-05
Every reachable state reaches zero deterministically in steps. For , choose a supported lifetime ; zero can jump to and then count down to . Thus the chain is an irreducible Markov chain on . Its positive-probability first return lengths are exactly the support of ; all other return lengths are sums of such lengths. Their greatest common divisor is therefore one by assumption, so the chain is an aperiodic Markov chain.
The equilibrium residual-life distribution isIt is a probability distribution because the tail-sum identity gives . With zero masses outside ,so it is a stationary distribution. This also displays why finite mean is needed for normalization.
Use the countable-state Markov chain convergence theorem: an irreducible, aperiodic, positive recurrent discrete-time chain on a countable state space has a unique stationary distribution and for every pair of states. All hypotheses were verified, including positive recurrence in part (b). Since and ,The finite-state convergence theorem alone would not suffice when the lifetimes are unbounded. The gcd hypothesis is also necessary for this ordinary limit: deterministic lifetime 2, for example, produces alternating renewal probabilities rather than convergence.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 1 a Solution Created 2026-10-03 Updated 2026-10-06
For probability distributions on a finite set, the total variation distance isThe equality follows by taking : the positive and negative parts of have the same mass, since its total mass is zero.
Use the stationary distribution identity . For each initial state ,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over proves . This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.
