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.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 1 c Solution Created 2026-10-03 Updated 2026-10-06
Let interchange the two complete graphs, sending to and fixing . This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts at , keeps until the hitting time of , and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at . The coupling inequality for total variation gives
There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For , write and for . From every clique vertex there is a positive chance of reaching within two steps, uniformly over the finite state space for each fixed , so has finite expected value. First-step analysis, using the degree of a vertex at and at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is , the hitting time of the bridge vertex between two cliques formula.
We must also handle arbitrary starting states, including , before applying the mirror argument. Identify related vertices and consider the lumped Markov chain on . Its transition matrix has for , , for and , and , with all other entries zero. Here the row for only ranges over .
For and , direct two-step calculation givesAll these entries are at least . Thus for every , where is the uniform distribution on a finite set and . This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from with probability , using the residual probability distributions otherwise. The first successful block has expected value at most , so the alignment time has . Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.
At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time satisfying for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least : for two ordinary indices it is ; for one attachment index it is . A maximal coupling therefore aligns those indices with probability , as suggested. The two-step argument above additionally covers .
The nonlazy walk is an aperiodic Markov chain for , because the connected graph contains a triangle. For it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass , and the walk stays on a single class at each time. Hence and the mixing time is infinite. The asymptotic conclusion is valid for .
The first Markov chain is a finite irreducible Markov chain: its positive-probability directed cycle reaches all four states. The self-loop at state 1 makes it an aperiodic Markov chain. Convergence to an invariant distribution therefore givesThe second chain alternates between the sets and . It is a periodic Markov chain with period two, so . From either state 2 or state 4 the next-step probability of entering state 1 is . Therefore for every . The subsequences have different limits, so the second return-probability sequence does not converge.
Periodic Markov chain Created 2026-09-24 Updated 2026-11-05
For a state of a Markov chain, its period is the greatest common divisor of the positive return lengths,A state is periodic when . All states in an irreducible class have the same period: paths connecting two states transfer return cycles between them. A reducible chain can have classes of different periods, so a single period for the whole chain requires qualification.
The deterministic two-state chain has period two: its distributions alternate forever despite the existence of the uniform Stationary distribution. More generally, an irreducible nearest-neighbour walk on a bipartite graph alternates its two vertex classes. A positive holding probability at any state of an irreducible class supplies a one-step return and makes the entire class aperiodic. Aperiodicity therefore concerns possible return lengths rather than merely the existence of an invariant law.
Stationary cycle occupation formula Created 2026-09-24 Updated 2026-11-05
For an irreducible positive recurrent Discrete-time Markov chain with Stationary distribution , fix a state and its positive first return . The Stationary cycle occupation formula isThe cycle includes the initial visit to and excludes the returning visit. Thus for the left side is exactly one, consistent with the ratio.
Successive return cycles are independent with the same law by the Strong Markov property. The renewal reward ratio gives the long-run visit fraction as expected cycle occupation divided by expected cycle length. Kac's lemma supplies , so the ergodic visit fraction gives the displayed identity. positive recurrence ensures the cycle length and all its occupation rewards are integrable.
For distinct , the Two-state excursion visit law gives the same expected occupation as , where and . ConsequentlyThis identity does not require reversibility: it follows from return-cycle occupation. It also does not require aperiodicity, since time averages still converge in a periodic positive recurrent chain.