Basis Lab

Markov Chains

How Long Until It Gets There

Last timeWhy the Chain Forgets Where It Started

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

The last two lessons answered where a chain ends up and how long before it has

forgotten where it started. Neither answers the question most people arrive

with, which is how long until something in particular happens.

How many mornings before this machine needs a part. How many clicks before this

reader reaches the checkout. How many steps before this process hits the level

that triggers an alarm. These are arrival questions, and they have their own

method, which is short.

Take one hop, then ask the same question again

Suppose you want the average number of hops from here to some destination.

Take one hop. You have used one hop and you are now somewhere else, and from

there the question is the same question, because the chain does not remember how

it arrived.

So the average from here is one, plus the average from wherever the hop lands,

weighted by the chance of landing there.

FIG 1The average time to arrive, from one situation
One of these for every situation except the destination, and the destination contributes nought wherever it appears in the sums. That gives as many linear equations as unknowns, with no sum over paths and no limit anywhere. It is worth appreciating how much is being avoided here: the direct approach would add up the chance of every route of every length, and the conditioning argument replaces that infinite sum with a system you can solve by hand.

Doing it on the machine chain

Take the machine of the first lesson and ask how many mornings until it is

waiting for a part, starting from running.

The lesson stops here

5 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 Aloneopening only
  5. 05Why the Chain Forgets Where It Startedopening only
  6. 06How Long Until It Gets Thereyou are here
  7. 07Chains That Look the Same Run Backwardsopening only
  8. 08Building a Chain to Reach a Chosen Distributionopening only

Read alongside