Basis Lab

Answers · The mathematics underneath

Why does a Markov chain eventually forget which state it started in?

In shortA finite Markov chain forgets its starting point when it has one closed class and no cycle, because two runs from different starts share chance that the rule cannot separate again.

A finite Markov chain forgets its starting point when it has one closed class and no cycle. The reason is not that the start is overwritten by an average: two copies run from different starts share a portion of their chance, the rule keeps that shared portion identical for ever, and only the shrinking remainder can still differ.

dk=12∑j∣μj(k)−πj∣≤Cλkd_k = \tfrac{1}{2} \sum_{j} \left| \mu_j^{(k)} - \pi_j \right| \le C \lambda^{k}

Here dkd_k is half the sum of the absolute differences between the chance of each situation after kk hops and its resting share. It runs from nought, when the two distributions are identical, to one, when they have no overlap at all. The bound on the right has the shape that matters: a constant CC that absorbs the first hop or two, multiplied by a factor λ\lambda below one raised to kk. The constant changes when the decay begins; the factor sets how fast it goes, and the factor is read off the transition table, not off the starting distribution.

The shrinking gap

Take a chain whose distance from resting shrinks by four fifths each hop, which is the slow factor of the three-state machine chain. If the distance is one at some hop, then five hops later it is 0.85=0.327680.8^5 = 0.32768, ten hops later it is 0.810=0.1073740.8^{10} = 0.107374, and twenty hops later it is 0.820=0.0115290.8^{20} = 0.011529. The ratio from five to ten hops is 0.107374/0.32768=0.327680.107374/0.32768 = 0.32768, the same factor again. That is the whole content of forgetting: not that the start is moved along, but that the difference between the start and the rest is multiplied by a number below one, repeatedly. A gap of one becomes 0.1073740.107374 after ten hops, 0.0115290.011529 after twenty, and 0.0012380.001238 after thirty.

Why the start does not just shift

The natural guess is that the initial distribution survives as a moving copy, so the chain at time kk is the start shifted kk places. That is true of a deterministic rotation and false here. If the chain alternates certainly between A and B, the distribution after kk hops is (1,0)(1,0) for even kk and (0,1)(0,1) for odd kk, so no limit exists and the parity of the start is never lost. That is a cycle. If there are two closed classes with no movement between them, a chain started in one never puts any chance in the other, so the class of the start is retained for ever. That is a second closed class. One closed class rules out the second failure, and for a finite chain with no transient states that is irreducibility. No cycle rules out the first, which is aperiodicity.

P=(0110),μ(k)=(1,0) for even k,  (0,1) for odd k.P = \begin{pmatrix}0&1\\1&0\end{pmatrix}, \quad \mu^{(k)} = (1,0) \text{ for even } k, \; (0,1) \text{ for odd } k.

The rate is in the table

Once both conditions hold, the bound has λ\lambda equal to the slowest factor. The machine chain has two modes, four fifths and one tenth. After three hops the fast mode is 0.13=0.0010.1^3 = 0.001, while the slow mode is 0.83=0.5120.8^3 = 0.512; by then the fast mode is already a thousandth of its starting size. After ten hops the fast mode is 0.110=0.00000000010.1^{10} = 0.0000000001, and the slow mode is 0.810=0.1073740.8^{10} = 0.107374. That is why the observed gap falls by four fifths per hop after the first few hops: the fast mode has vanished. The mixing time is the hop count at which this slow factor has brought every start within a stated accuracy, so it is a property of the table and the accuracy, not of the starting distribution.

FIG 1The slow mode survives the fast one
0.000.631.251.882.500.06.312.518.825.0hops taken
slow mode, four fifthsfast mode, one tenthboth together
The fast mode is gone within a few hops, so the visible gap follows the slow factor. To know how long a chain takes to forget its start, only the slowest mode is needed; to make a chain fast, no mode may be allowed to be slow.

The conclusion is finite-state and depends on both conditions. With infinitely many states one closed class need not force convergence; a chain can drift away and return too rarely, so recurrence has to be checked separately. A cycle breaks it even when the resting distribution is unique, as the alternating chain shows. Two closed classes break it because the start chooses a class that no hop can leave. The mixing time also carries its accuracy: a chain within one per cent after twenty hops need not be close in a stronger sense, so the one per cent belongs to the number.

Worth keeping

  • One closed class and no cycle are jointly what make a finite chain converge to a single resting distribution from every start.
  • The rate of forgetting is fixed by the transition table, usually by its slowest mode, not by the starting distribution.
  • A periodic chain or a chain with two closed classes can keep a trace of its start for ever.

Where this goes next

This question is one step of Markov Chains, a course that works through its subject from the beginning. The page that teaches this part of it is Why the Chain Forgets Where It Started, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. What's the difference between a state the chain keeps returning to and one it eventually leaves forever?A state the chain keeps returning to is in a closed group it cannot leave; any other state is left forever after finitely many visits.
  2. How do you build a random walk whose long-run distribution is a distribution you choose?Propose a symmetric random move; accept moves to heavier target weight outright and moves to lighter weight with probability equal to the weight ratio, then run the chain.
  3. What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
  4. How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.
  5. How do you find the parabola that best fits a function near a point?Match the function's height, slope and bending at the chosen point; those three conditions single out exactly one parabola.
  6. Why does a test for a rare disease give so many false positives if the test is accurate?A positive result means the test fired, not that you are likely to be ill; when the disease is rare, healthy people vastly outnumber ill ones, so a small false-alarm rate on them swamps the few true cases.

Read alongside