Ehrenfest urn model Created 2026-10-06 Updated 2026-11-05
The Ehrenfest urn model moves one uniformly chosen ball between two boxes at each step. For balls, the count in one box is a Markov chain on . Its stationary distribution is , and detailed balance makes it a reversible Markov chain. The chain has period two, but its mean recurrence time to the all-in-one-box state is still .
Kac's lemma Created 2026-09-24 Updated 2026-11-05
For an irreducible positive recurrent discrete-time Markov chain with stationary distribution , the expected return time to state is . More generally, expected occupation rewards in a return cycle equal their stationary rate times the expected cycle length.
Mean recurrence time Created 2026-09-24 Updated 2026-11-05
The mean recurrence time of is . In a finite irreducible Markov chain with stationary distribution , it equals .
Null recurrent Markov chain Created 2026-10-31 Updated 2026-11-05
An irreducible Markov chain is null recurrent when every state is a null recurrent state: it returns to that state almost surely, but its mean recurrence time is infinite. Such a countable-state chain has no stationary distribution.
Ordered-state visit times in a reversible chain Created 2026-10-07 Updated 2026-11-05
Let a Reversible Markov chain start in its Stationary distribution , and let . Define to be the first time an occurrence of has been followed strictly later by an occurrence of :For each fixed , the event says that the path segment contains before . Reversing that segment changes the event into the existence of before . Stationary reversibility therefore gives for every , so the two completion times have the same distribution.
For a finite irreducible chain, all these expected hitting times are finite. Let and , with . The Strong Markov property at gives . Applying the same argument with reversed yieldsIf the diagonal is instead defined by the positive mean return time , its contribution to each stationary-weighted mean is one by Kac's lemma. Those equal additions cancel in the displayed difference.
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 4 9H b Solution Created 2026-09-24 Updated 2026-10-06
A finite irreducible Markov chain is positive recurrent. Its mean recurrence time to state , starting at and counting the first positive return, is . This identity comes from the long-run fraction of time spent at that state: successive return cycles each contain one visit at their start, so the fraction is the reciprocal of the mean cycle length. It remains valid for a periodic chain.
Past exam of the mathematics course of the University of Cambridge 2017 ib Paper 2 20H b Solution Created 2026-09-24 Updated 2026-10-05
Starting at zero, the next renewal is at time , and there are no intervening renewals because . Thus the first return time obeys in distribution, indeed under the original renewal construction. Its mean recurrence time isThe chain returns to zero almost surely and has a finite expected return time, so zero is a positive recurrent state. The assumption is what upgrades recurrence to positive recurrence.
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 2 20H i Solution Created 2026-09-24 Updated 2026-10-03
For a finite irreducible Markov chain with invariant distribution , the mean recurrence time of state isThe simple random walk on the hypercube has the uniform invariant distribution because the hypercube graph is regular, so every vertex has mass . Therefore the expected first positive return time to the initial vertex is
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 2 18H a i Solution Created 2026-09-24 Updated 2026-09-25
A distribution is an invariant distribution whenfor every state . The pair satisfies detailed balance whenfor every . Summing this identity over givesso detailed balance implies invariance.
For an irreducible positive recurrent Markov chain, Kac's lemma relates the invariant mass to the mean recurrence time:
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 2 18H b ii Solution Created 2026-09-24 Updated 2026-09-25
Normalizing the invariant distribution found in part (i) givesThe mean recurrence time formula now yields
Past exam of the mathematics course of the University of Cambridge 2023 ib Paper 2 18H d Solution Created 2026-09-24 Updated 2026-10-03
False. Again use two states, but now takeThe support condition holds. Under , the first return time to state one is identically one, so . Under , the chain is irreducible with stationary distribution . The mean recurrence time formula givesThus enlarging transition support does not imply a smaller mean return time.
For the chain is irreducible, and the normalized stationary distribution in (i) makes it positive recurrent. The mean-return-time formula givesHere includes a return at time one when the chain stays at zero. This convention is essential. Equivalently the mean hitting time of zero from one is , so a first-step decomposition gives , the same result. For the population remains zero and the next zero is at time one, also agreeing with the formula.
Preservation under enlargement of transition support Created 2026-09-24 Updated 2026-11-05
Suppose two finite Markov chains on the same state space have transition matrices satisfyingEvery positive-probability path and return cycle for is also possible for . Thus irreducibility passes from to . For a state aperiodic under , its positive return lengths under contain those under , so their greatest common divisor is still one. Hence aperiodicity also passes to .
Individual-state recurrence need not be preserved when the original chain is reducible. For example, take on andState zero is recurrent under but transient under : once the chain leaves it, it never returns. The added transition opens an escape from its former closed class. If is finite and irreducible, however, then is also finite and irreducible, so every state remains positive recurrent. Mean recurrence times can still change because the Stationary distribution depends on transition probabilities, not merely on their support.
Recurrent Markov chain Created 2026-09-24 Updated 2026-11-05
A Recurrent Markov chain returns to its states rather than eventually leaving them forever. A state is recurrent if its positive first return time satisfies . A chain is recurrent when every state is recurrent. Within an irreducible class, recurrence is shared by every state, so testing one state suffices.
The Strong Markov property at successive return times shows that a Recurrent state is visited infinitely often almost surely when starting there. If its return Probability is , the number of visits including time zero has a geometric distribution on the positive integers, with mean . Consequently the Green-function criterion isTonelli's theorem identifies this sum with the expected number of visits. recurrence does not require a finite mean return time: null recurrence and positive recurrence distinguish infinite from finite mean recurrence time. simple symmetric random walk on the integers is null recurrent, whereas every finite irreducible chain is positive recurrent.
Reset-or-increment Markov chain 2026-10-31
For , consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing , its stationary distribution isThe balance equations give and for ; the geometric series normalizes the result, and the zero-state equation agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability , so its mean recurrence time is . Return paths of lengths two and three also make it aperiodic.
Stationary distribution of a regenerative countdown chain Created 2026-10-06 Updated 2026-11-05
For the geometric-jump countdown Markov chain, regeneration at zero givesA cycle visits positive state precisely when its jump reaches at least , with Probability . Dividing this expected occupation by the mean cycle length proves the formula. Mean recurrence times are , and the limiting Probability away from zero is .
An irreducible Markov chain on a finite or countably infinite state space has at most one stationary distribution. On a countably infinite state space it exists exactly when the chain is positive recurrent. In that case, for every state ,where is the first return time. The expression determines every component uniquely. The formula follows by dividing the one visit to in each return cycle by the mean recurrence time; the strong law of large numbers for successive cycles makes this occupation fraction precise.
Every irreducible finite Markov chain is positive recurrent and has exactly one stationary distribution. On an infinite state space, an irreducible null recurrent Markov chain or transient Markov chain has none. For example, the simple symmetric random walk on the integers is null recurrent. Aperiodicity affects convergence of the one-time laws, but is unnecessary for existence or uniqueness of a stationary distribution.