A guard patrols a corridor with four posts and tends to keep walking the way he is going. Where he goes next depends on where he is and on which way he was walking, so his position alone is not a Markov chain: two guards at the same post can have different futures. The cure is not a new theory but a better choice of state. Put the missing memory into the state, and the process becomes an ordinary Markov chain again, with everything from the previous chapters available: transition matrix, πP = π, long-run shares.
By the end you can
- Recognise when the obvious states of a process are not Markov.
- Enlarge the state with just the memory the rule needs, and list only the states that can occur.
- Build the transition matrix of the enlarged chain, including forced moves at the ends.
- Solve it, and add states back up to answer questions about the original quantity.
- Handle a rule that looks two steps back.
Number the posts 1 to 4 from left to right. The rule: if the last step was to the right, the next one is also to the right with probability r = 0.5; if it was to the left, the next is also to the left with probability l = 0.75. At post 1 or post 4 he has no choice and turns back. Call his position after n steps Xₙ. A Markov chain needs P(Xₙ₊₁ = j | the whole past) to depend only on Xₙ. Look at a guard standing at post 2:
The rule looks at two things: the post and the direction of the last step. So the state must hold both: Yₙ = (Xₙ, Dₙ), where Dₙ is → or ← for the step that brought him to Xₙ. Now the next state depends only on the current one, because everything the rule reads is in it. Not every pair can occur. He can only arrive at post 1 walking left and at post 4 walking right, so instead of 4 × 2 = 8 states there are 6:
| State | Meaning | Next state (probability) |
|---|---|---|
| 1← | at post 1, arrived walking left | 2→ (1): forced to turn |
| 2→ | at post 2, arrived walking right | 3→ (r = 0.5), 1← (1 − r = 0.5) |
| 2← | at post 2, arrived walking left | 1← (l = 0.75), 3→ (1 − l = 0.25) |
| 3→ | at post 3, arrived walking right | 4→ (r = 0.5), 2← (1 − r = 0.5) |
| 3← | at post 3, arrived walking left | 2← (l = 0.75), 4→ (1 − l = 0.25) |
| 4→ | at post 4, arrived walking right | 3← (1): forced to turn |
Read the names carefully: the arrow in the next state is the direction of the step just taken. From 2→, going on to the right lands on post 3 still walking right, 3→; turning lands on post 1 walking left, 1←. Each row adds up to 1, as every row of a transition matrix must. The forced turns at the ends are rows with a single 1.
The stationary distribution satisfies πP = π: for each state, the probability flowing in equals the probability sitting there. Write one equation per state, adding the arrows that arrive at it. Call π(1←) = A, π(2→) = B, π(2←) = C, π(3→) = D, π(3←) = E, π(4→) = F.
The question was about posts, not about states. The guard is at post 2 whenever he is in 2→ or in 2←, so the share of time at a post is the sum of the probabilities of its states:
A walker that does not prefer a side
If r = l, then q = 1 and all six states are equally likely, 1/6 each, however stubborn the walker is. The end posts have only one state each, so they get 1/6 of the time, and the middle posts 2/6. Stubbornness changes how the walk looks (long runs instead of jitter) but not where the time goes. Check it in the figure: set r = l and move them together.
The bars are the exact long-run share of time at each post: π of the enlarged chain, with the states of each post added up. The dots are what the walker has actually done so far; let it run (the fast button takes 200 steps at a time) and they settle on the bars. The chips under the corridor are the states that can occur: the post, then the direction of the last step, and in two-step mode the direction of the step before. At the ends only one direction can arrive, which is why there are fewer states than posts × directions. Set r = l, or s = q, and look at what stays the same.
Some rules look further back. In a simple weather model, whether it rains tomorrow depends on today and on yesterday: rain tomorrow with probability 0.8 after two rainy days, 0.6 if it rained today but not yesterday, 0.3 if it rained yesterday but not today, and 0.1 after two dry days. The day's weather alone is not Markov. The state must hold both days: (yesterday, today), four states. Moving one day forward, today becomes yesterday and tomorrow becomes today.
| State | Meaning | Next state (probability) |
|---|---|---|
| RR | rain yesterday, rain today | RR (0.8), RD (0.2) |
| DR | dry yesterday, rain today | RR (0.6), RD (0.4) |
| RD | rain yesterday, dry today | DR (0.3), DD (0.7) |
| DD | dry yesterday, dry today | DR (0.1), DD (0.9) |
A walker whose rule depends on its last two steps works the same way: the state is (post, direction of the last step, direction of the step before). Only combinations that can really happen count. Arriving at post 1 always means the last step was to the left; at post 2 of a corridor with only 3 posts the two last steps always point opposite ways. The second mode of the figure builds these states for any corridor and lists them under the bars.
- Write the rule for the next step in words, including what happens at the edges.
- List everything the rule looks at: the position, the last direction, the last two days…
- Make the state exactly that list. Less, and the chain is not Markov; more, and it is Markov but needlessly big.
- Keep only the states that can occur: start from one state and follow the arrows until no new state appears.
- Write each row of P and check that it adds up to 1.
- Solve πP = π, then add states up to answer the question about the original quantity.
A round of 10 questions
Answer as many as you can. Mistakes come back at the end for a review round.
Every exercise is made on the spot, so a new round is never the same. The computer picks the answer first and builds the question around it, working with exact fractions, so the answer key is always right. Answers are read exactly: 0.75, 3/4 and 6/8 count as the same number (where lowest terms are asked for, 6/8 just gets a reminder). A wrong answer shows the worked solution line by line, in the order the lesson does it; the new number in each line is coloured.
| Wrong | Right | Why |
|---|---|---|
| a chain on the positions alone | position + direction | the next step depends on the direction, so it must be in the state |
| 8 states for 4 posts | 6 states | 1→ and 4← can never occur; unreachable states make πP = π have many solutions or none |
| forgetting the forced turn | a row with a single 1 | at the ends the rule's probabilities do not apply |
| reporting π of the states | add the states of each post | the question is about posts; 2→ and 2← are both post 2 |
| next state named by the old direction | name it by the step just taken | otherwise rows point to the wrong columns |
Key ideas
- A process is Markov in a set of states only if the next step depends on the current state alone.
- When the rule looks at more than the position (the last direction, yesterday), put that memory into the state.
- Keep only the states that can occur; at the ends the rule is replaced by forced moves.
- The enlarged chain is an ordinary Markov chain: build P, check the rows, solve πP = π.
- To answer for the original quantity, add the probabilities of the states that share it.
- Two-step memory: the state is the last two observations; one step forward shifts them along.