Where You Are After Many Hops
Last timeWhere You Are, and One Hop
Two 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.
The table says what happens in one hop. Almost no question anybody actually has
is about one hop. What is the chance the machine is running a fortnight from
now, what fraction of readers reach the checkout page eventually, how long
before this process has forgotten where it started: all of these are questions
about many hops.
It turns out that the many hop question needs no new ideas at all. It needs the
one hop table and one piece of arithmetic, applied repeatedly.
Two hops, by listing the routes
Start with two. To get from a situation to another in exactly two hops, the
process has to be somewhere in between, and the list of candidates for that
somewhere is the list of situations, which is finite and known.
Fix one candidate. The chance of taking that particular route is the chance of
the first hop multiplied by the chance of the second, because both have to
happen and, by the memoryless assumption, the second hop's chance depends only
on where the process is at the middle moment and not on where it came from.
Now notice that the different candidates are mutually exclusive: at the middle
moment the process is in exactly one situation. So the chances of the routes
add. The two hop chance is a sum of products, one term for each situation.
| step | route | first hop | second hop | chance of the route |
|---|---|---|---|---|
| 1 | waiting, then running, then running | waiting to running is impossible, chance nought | running to running, nine in ten | nought |
| 2 | waiting, then under repair, then running | waiting to repair, three in ten | repair to running, one in two | three in ten times one in two, which is fifteen in a hundred |
| 3 | waiting, then waiting, then running | waiting to waiting, seven in ten | waiting to running is impossible, chance nought | nought |
| 4 | all routes together | three candidates for the middle situation, no others | the list is exhaustive because the process is somewhere | nought plus fifteen in a hundred plus nought, which is fifteen in a hundred |
The route sum is matrix multiplication
Write the sum down in symbols and look at what it is doing. It runs along the
row of the starting situation and down the column of the destination,
multiplying the pairs it meets and adding the products. That is the definition
of multiplying two matrices together, with the table playing both parts.
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