Model anything that moves at random between a known set of situations, work out where it spends its time in the long run, how long it takes to get there and how long it takes to arrive anywhere in particular, and then run the argument backwards to build a chain whose long run is a distribution you chose

Markov Chains

A system that hops between situations, each hop decided only by where it is now. This course derives where such a thing ends up, why it forgets where it began, and how to build one whose destination you picked in advance.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

01Where You Are, and One HopA chain is a list of situations and a table of hopping chances. The assumption that makes it work is that the present situation is the only thing the next hop is allowed to see.
02Where You Are After Many Hopsopening onlyTwo hops means adding up every route through a middle situation. That sum is exactly matrix multiplication, so the table for any number of hops is the one hop table raised to that power.
03What Is Reachable, and What Traps Youopening onlySome situations a chain keeps coming back to and some it abandons for good. Sorting them out is the step that has to happen before any long run question has an answer at all.
04The Distribution the Rule Leaves Aloneopening onlyOne spread of chances across the situations comes out of a hop exactly as it went in. Find it by balancing what flows into each situation against what flows out, and the long run is settled.
05Why the Chain Forgets Where It Startedopening onlyRule 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.
06How Long Until It Gets Thereopening onlyCondition on the first hop and the average number of hops to reach a situation becomes one small linear system. The average gap between visits then turns out to be one over the resting share.
07Chains That Look the Same Run Backwardsopening onlySome chains balance pair by pair rather than only situation by situation. When a chain does, its resting distribution can be read straight off the rule with no equations to solve at all.
08Building a Chain to Reach a Chosen Distributionopening onlyA distribution you can write down but cannot draw from. The construction here builds a chain that rests exactly there using only ratios, and promises correctness without promising any speed.