Transition Diagrams

States and arrows

A transition diagram draws a Markov chain as a picture. Each state is a circle. An arrow from one state to another carries the chance of moving that way in one step, and a loop from a state back to itself carries the chance of staying.

For the city and the country: each year 0.2 of the city moves to the country and 0.3 of the country moves to the city, so the arrow from the city to the country carries 0.2 and the arrow back carries 0.3. The city keeps 0.8, written on its loop, and the country keeps 0.7.

The city C and the country K, each with a loop for the share that stays and an arrow for the share that moves to the other.

From the diagram to the matrix

Each state gets a column of T for where its people start and a row for where they end up, in the same order: the city first, then the country. An arrow from one state to another goes in the column of the state it leaves and the row of the state it reaches. So the 0.2 on the arrow from the city to the country sits in column 1, row 2.

Row 1 then collects every arrow arriving in the city: the loop 0.8 from the city itself and the arrow 0.3 from the country. Row 2 collects the arrows arriving in the country, 0.2 and 0.7. That gives T = (0.8 0.3; 0.2 0.7), the same matrix as the table of shares.

A pair of states with no arrow between them has a 0 in that place. A state drawn with no loop has a 0 on the diagonal: nobody stays.

The top row of T is everything arriving in the city: 0.8 on the city's loop and 0.3 on the arrow from the country.

What leaves a state adds to 1

Everyone who starts in the city either stays or moves, so the loop and the arrows leaving the city add to 1: 0.8 + 0.2 = 1. Those are the entries of column 1 of T. For the country, 0.7 + 0.3 = 1, which is column 2.

This is how to find a share the diagram leaves out. If two arrows leave a state P carrying 0.6 and 0.3, then P's loop must carry 1 − 0.6 − 0.3 = 0.1.

Everything leaving the city C, its loop 0.8 and its arrow 0.2, adds to 1. That pair is the first column of T.

Two steps along the arrows

A diagram also shows how to go two steps. To find the chance that someone in the city is in the city two years later, list every path of two arrows from the city back to the city. Multiply the chances along each path and add the paths.

There are two paths. Staying twice, city to city to city, has chance 0.8 × 0.8 = 0.64. Moving out and coming back, city to country to city, has chance 0.2 × 0.3 = 0.06. Together that is 0.64 + 0.06 = 0.7, which is the top left entry of $T^2$T². Multiplying T by itself adds up exactly these paths.

Regular chains

A Markov chain is regular when some power of T has every entry positive. Then, after that number of steps, every state can be reached from every state, whatever the start.

T itself may have zeros. Take two states A and B. A never stays: its only arrow goes to B, carrying 1. B stays with chance 0.5 and moves to A with chance 0.5. With A first, T = (0 0.5; 1 0.5), which has a 0 in the top left.

Square it. The top left entry of $T^2$T² is 0 × 0 + 0.5 × 1 = 0.5, the path A to B to A. The top right is 0 × 0.5 + 0.5 × 0.5 = 0.25, the bottom left is 1 × 0 + 0.5 × 1 = 0.5, and the bottom right is 1 × 0.5 + 0.5 × 0.5 = 0.75. So $T^2$T² is the matrix (0.5 0.25; 0.5 0.75). Every entry is positive, so the chain is regular.

A has no loop, so A cannot be in A one step later. In two steps it can: A to B to A has chance 1 × 0.5 = 0.5.

T has a 0 in its top left corner, and its square has none, so this chain is regular.

When a chain is not regular

Take three states A, B and D. A always moves to B, B always moves to D, and D has only a loop carrying 1. Nobody ever leaves D: it is a trap, also called an absorbing state.

In the order A, B, D the columns of T are (0, 1, 0) for A, (0, 0, 1) for B and (0, 0, 1) for D. Square it: two steps take A to D and B to D, and D stays at D, so every column of $T^2$T² is (0, 0, 1). Every later power is the same, with zeros in the rows of A and B. No power of T is all positive, so the chain is not regular.

A chain can fail in a second way. If two states swap every step, each arrow carrying 1 and neither state having a loop, then T = (0 1; 1 0), and $T^2$T² is the identity matrix (1 0; 0 1). The powers take turns between these two matrices, and both have zeros, so this chain is not regular either.

D has no arrow out, only a loop carrying 1, so everyone who reaches D stays there.

Two states that swap every step: after an odd number of steps a walker who started in A is always in B.

The usual mistakes

Putting an arrow in the row of the state it leaves. The arrow from the city to the country belongs in the city's column and the country's row.

Leaving out a loop that the diagram does not draw. The share that stays is 1 minus the arrows leaving, and it goes on the diagonal of T.

Calling a chain regular because each column of T adds to 1. That is true of every transition matrix; regular asks that some power of T has no zero entries.

Calling a chain not regular because T has a zero. A zero in T is allowed, as long as a zero-free power comes later.

Weather and a frog

In the applications below, a diagram of sunny and rainy days becomes a transition matrix, and the chance of rain two days on is found by multiplying by T twice and checked by adding the chances of the two paths. Then a frog hops between three lily pads, a missing arrow from one end pad to the other gives a 0 in T, and the only two-minute path to the far pad gives its chance.