Basis Lab

Markov Chains

The Distribution the Rule Leaves Alone

Last timeWhat Is Reachable, and What Traps You

One 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.

The second lesson showed that the distribution after many hops is the table

applied many times, and that for most chains the rows of the high powers become

identical. The third sorted out which chains those are.

This lesson asks what that common answer is, and finds it without computing any

powers at all. The trick is to stop asking what the chain tends towards and ask

instead what a single hop leaves unchanged. That question is algebra.

The condition

Take a spread of chances across the situations, adding to one, and apply the

rule once. Something comes out. A resting distribution is one where what comes

out is what went in.

FIG 1The condition for a distribution to be left alone
Read it as an instruction and it says apply the table to the distribution. Read it as an equation and it says the result is the distribution you started with. There is one of these for each situation, and the whole set has to hold at once. Note what is absent: no number of hops appears anywhere, and no starting point. This is a condition on a single hop, which is why it is solvable in closed form rather than something that has to be waited for.

The same thing as bookkeeping

Written one situation at a time, the condition says something plainer. Chance

leaves a situation at a rate equal to its share multiplied by the chance of

hopping away. Chance arrives from everywhere else. Resting means the two are

equal, everywhere, simultaneously.

The lesson stops here

6 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 contents

This 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

The rest of this course

  1. 01Where You Are, and One Hop
  2. 02Where You Are After Many Hopsopening only
  3. 03What Is Reachable, and What Traps Youopening only
  4. 04The Distribution the Rule Leaves Aloneyou are here
  5. 05Why the Chain Forgets Where It Startedopening only
  6. 06How Long Until It Gets Thereopening only
  7. 07Chains That Look the Same Run Backwardsopening only
  8. 08Building a Chain to Reach a Chosen Distributionopening only

Read alongside