Where You Are, and One Hop
A 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.
A machine is either running, being repaired, or waiting for a part. Each
morning it is in one of those three situations, and which one it is in tomorrow
depends on which one it is in today. That is the whole of the setup, and almost
everything in this course is a question about it: how much of the year is it
running, how long between breakdowns, how long before the answer to the first
question stops depending on what happened this morning.
The setup is worth being precise about, because the precision is where the
modelling happens. Everything after this lesson is arithmetic.
The situations
The first decision is what counts as a situation. The list has to cover
everything that can happen, and the process has to be in exactly one of them at
any moment. Running, under repair and waiting for a part satisfies that for the
machine, provided those three really are the only possibilities and the machine
is never two of them at once.
The list can be small or enormous and the mathematics does not care. A board
game's situations are its squares. A queue's situations are the numbers of
people in it. A text model's situations are the possible recent histories of
words. What matters is not the size but a property the next section names.
What the chain may not remember
Here is the assumption, and it is the only one. Given the situation now, the
chances of the next situation do not depend on anything else. Not on how the
process arrived here, not on how long it has been here, not on the time of
year, not on anything.
There is a practical test. Think of two different histories that both end in
the same situation, and ask whether somebody who knew which history had
occurred would bet differently on tomorrow. If the answer is yes, the
assumption is false as the situations are currently defined.
The machine fails that test in one respect, and it is worth naming because it
is typical. If a repair that has already taken five days is less likely to
finish tomorrow than a repair that started this morning, then under repair is
not a single situation: how long it has been going matters, and the chain does
not know. The repair is to split it, into repair day one, repair day two and so
on, which is more situations but an honest table.
| to running | to under repair | to waiting | |
|---|---|---|---|
| from running | 0.9 | 0.1 | 0.0 |
| from under repair | 0.5 | 0.1 | 0.4 |
| from waiting | 0.0 | 0.3 | 0.7 |
Rows that add to one
The table is the model. Each row is a complete statement of what can happen
from one situation, so each row adds to one: from wherever the process is, it
goes somewhere, and staying counts as going somewhere.
A row that adds to less than one means one of two things, and it is worth
telling them apart. Either the model is wrong and a possibility has been
forgotten, or the process can genuinely leave, as a customer can abandon a
queue. The second case is handled by adding a situation called gone, with a row
that sends it to itself with certainty. It is better to have a situation for
leaving than a table that does not add up.
Now watch the table move a whole distribution of chances around rather than a
single walker. If there is a one in three chance of being in each situation
this morning, applying the table once gives the chances for tomorrow morning,
and the three chances still add to one for the same reason each row does.
the three chances, added upunder 0.001% of it gone by the end, at every setting of every slider
- stepped by
- pa → (0.9 - g)*pa + 0.5*pb + 0.0*pc pb → (0.1 + g)*pa + 0.1*pb + 0.3*pc pc → 0.0*pa + 0.4*pb + 0.7*pc
- each rule reads
- the state as it was when the step began
- started at
- pa = 1.0, pb = 0.0, pc = 0.0
- held steady
- the three chances, added up = pa + pb + pc
- drift
- under 0.001% over the run, against 0.20% allowed
Enlarging the situation when the assumption fails
The repair for a failed memoryless test is nearly always the same move: put the
missing information into the situation. If tomorrow depends on today and
yesterday, make a situation out of each ordered pair of consecutive days. If it
depends on how long the process has been where it is, make a situation for each
length of stay. If it depends on the day of the week, pair each situation with
the day.
This always works, and it is worth knowing why it is not a free move. Suppose
there are ten situations and the next hop depends on the last three. The pairs
are a hundred, the triples are a thousand, and the table of a thousand
situations has a million entries. Each thing remembered multiplies the list
rather than lengthening it. That is the trade this whole subject lives inside:
the memoryless assumption can always be bought, and the price is paid in the
size of the table.
| step | morning | situation | what the table says happens next |
|---|---|---|---|
| 1 | Monday | running | nine in ten it is still running, one in ten it breaks |
| 2 | Tuesday | running | the same two chances again: nothing about Monday changes them |
| 3 | Wednesday | under repair | half fixed, two in five waiting for a part, one in ten still in pieces |
| 4 | Thursday | waiting for a part | seven in ten still waiting, three in ten the part arrives |
| 5 | Friday | waiting for a part | exactly the same two chances as Thursday, which is the assumption at its most visible and most questionable |
| 6 | Saturday | under repair | back to the repair row, with no memory that this is the second visit |
What to take from this
A chain is a list and a table. The list is a decision and the table is a
measurement, and almost all of the ways this subject goes wrong in practice are
decisions about the list rather than errors in the table.
The question to ask of any proposed list is the one from the second section:
two histories ending in the same place, would anybody bet differently. If not,
the chain is honest and the rest of the course applies to it. If so, enlarge the
situation until the answer is no, and then check whether the table that results
is one anybody can estimate.
Recap
- A Markov chain is two things: a list of the situations the process can be in, and for each one, the chances of being in each situation next. Those chances are written as a square table whose rows each add up to one, because the process has to be somewhere.
- The assumption is that the next hop depends on the present situation and on nothing else about the past. That is a restriction on the situations, not on the process: almost anything can be made to satisfy it by putting enough into the description of where you are.
- Choosing what counts as a situation is therefore the whole modelling decision. Too little in it and the assumption is false and the answers are wrong. Too much and the table is unusably large. Everything else in the course is arithmetic on a table somebody else chose.
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