Basis Lab

Markov Chains

What Is Reachable, and What Traps You

Last timeWhere You Are After Many Hops

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

The previous lesson said that the long run behaviour of a chain is a question

about high powers of its table. It did not say that the question always has an

answer, and it does not.

Before any of that can be settled, the situations have to be sorted. Some of

them the chain keeps coming back to forever. Some it passes through and

abandons. Some trap it completely. Which is which is decided by nothing more

than which arrows exist, and the sorting is the whole content of this lesson.

Reaching

One situation reaches another if there is any route from the first to the second

whose every hop has a chance above zero. The length of the route does not

matter and neither does how small the chance is.

That last point is worth insisting on. A route of six hops each with chance one

in a thousand has a chance of one in a million million million, and it counts

exactly as much as a single hop of chance nine in ten. The question being asked

is whether the thing is possible, and the answers to the long run questions turn

out to depend only on the possibilities and not on their sizes.

FIG 1A reader moving through a website, with two traps
Five situations, four distinct classes. The front page is a class on its own that is never returned to. The article and the pricing page form one class, which the reader circulates in for a while and then leaves. Bought and gone are each closed classes of one situation, and between them they collect all of the chance in the end. The useful question about this chain is not where it settles, since that depends on the start, but what fraction of readers ends up in each of the two traps.

Two situations that reach each other are said to communicate, and that relation

sorts the situations into classes: within a class everything reaches everything,

and between classes the reaching runs one way or not at all.

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 Youyou are here
  4. 04The Distribution the Rule Leaves Aloneopening only
  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