Why the Chain Forgets Where It Started
Last timeThe Distribution the Rule Leaves Alone
Rule out two failures and a chain forgets its starting point from every start. The forgetting happens at a rate the rule itself fixes, and that rate is what a mixing time measures.
The previous lesson found a distribution that a hop leaves alone. It did not
show that a chain ever gets there, and the alternating chain is a reminder that
being left alone is no guarantee of being arrived at.
This lesson supplies the missing argument. Two conditions, both already built in
the third lesson, are enough: one closed class and no cycle. With those, every
starting point leads to the same place.
Two copies, converging
The clean way to see it is to stop watching one chain and watch two, started
differently, running under the same rule.
both copies of the chance, added upunder 0.001% of it gone by the end, at every setting of every slider
- stepped by
- pa → 0.9*pa + (0.5 + k)*pb + 0.0*pc pb → 0.1*pa + 0.1*pb + 0.3*pc pc → 0.0*pa + (0.4 - k)*pb + 0.7*pc qa → 0.9*qa + (0.5 + k)*qb + 0.0*qc qb → 0.1*qa + 0.1*qb + 0.3*qc qc → 0.0*qa + (0.4 - k)*qb + 0.7*qc
- each rule reads
- the state as it was when the step began
- started at
- pa = 1.0, pb = 0.0, pc = 0.0, qa = 0.0, qb = 0.0, qc = 1.0
- held steady
- both copies of the chance, added up = pa + pb + pc + qa + qb + qc
- drift
- under 0.001% over the run, against 0.20% allowed
The reason the gap shrinks is worth stating carefully, because it is the whole
proof and it is not an argument about averages.
After enough hops, every situation can be reached from every other with some
chance above nought. That is what one closed class and no cycle give you. So
both copies, whatever they started as, place at least some fixed share of their
chance in the same places in the same proportions.
That shared share is identical in the two copies. The rule treats it identically
in both, so it stays identical forever: it can never come apart again. Only the
remainder can still differ, and the same argument applies to the remainder next
time round.
So the difference between the copies is multiplied by some factor below one,
every round, forever. A number multiplied repeatedly by a factor below one goes
to nought, and the two copies therefore agree in the limit. Since one of the
copies could have been started at the resting distribution, where it stays
forever, every other start converges to it.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents