11.5 Transition matrices

In Module 4.5, we tracked what stayed in each group and what moved to another group. In Module 11.3, a matrix combined several old inputs into new outputs. A transition matrix puts these ideas together: one row records all the destinations possible from one current state. Multiplication then applies the same movement rule to an entire population or probability distribution at once.

This is intermediate matrix and probability work. Review the two-state model in Module 4.5 and the matrix product first. MIT's Markov-chain notes go much further; the finite two-state calculations here are enough to begin.

A basic idea: stays plus arrivals in one calculation

Suppose each period, fraction $p$ of group $A$ moves to $B$, and fraction $q$ of $B$ moves to $A$. The rest stay. Put the old counts into a row $s_t=(A_t,B_t)$ and the movement fractions into

$$P=\begin{bmatrix}1-p&p\\q&1-q\end{bmatrix}.$$

The first row lists where someone in $A$ goes; the second lists where someone in $B$ goes. Now $s_{t+1}=s_tP$ says

$$A_{t+1}=(1-p)A_t+qB_t,\qquad B_{t+1}=pA_t+(1-q)B_t.$$

These are exactly the stays plus arrivals equations from Module 4.5, now packaged in one matrix product. Both new entries are computed from the same old row.

A quick tour of transition rules

For states $1,\ldots,n$, $P_{ij}$ is the fraction or probability of moving from state $i$ to state $j$ in one step. Every entry is nonnegative, and each row sums to $1$ when everyone has one destination among the listed states. With a row-vector state, $s_{t+1}=s_tP$ and $s_{t+k}=s_tP^k$. Entry $(P^2)_{ij}$ adds the probabilities of all two-step routes from $i$ to $j$ through an intermediate state.

If $s_t$ lists probabilities, its entries sum to $1$ and $s_tP$ is the next distribution. If it lists counts, the same formula gives expected counts when transitions are random, or exact counts when the stated fractions move exactly as described. A fixed transition rule says the next move depends on the current state; when this is used as a probabilistic model, it is a simple Markov chain.

The earlier matrix–vector lesson used column vectors $Ax$. If you prefer that convention, let $x_t=s_t^{\mathsf T}$ and write $x_{t+1}=P^{\mathsf T}x_t$. Transpose the matrix as well as the vector; otherwise the directions of movement change. Module 11.6 explains the corresponding row and column sums. Later, random walks on graphs use the same row-vector update to track a walker's location probabilities.

Application 1: two groups of people

Initially $80$ people are in $A$ and $20$ in $B$. Each period, $25\%$ of $A$ moves to $B$ and $10\%$ of $B$ moves to $A$. Find the next counts.

1. The row transition matrix is $P=\begin{bmatrix}0.75&0.25\\0.10&0.90\end{bmatrix}$.
2. $(80,20)P=(80(0.75)+20(0.10),\;80(0.25)+20(0.90))=(62,38)$.
3. The total is still $100$: everyone either stayed or moved between the two listed groups.

Application 2: changing weather

Suppose a sunny day is followed by sun with probability $0.8$ and rain with $0.2$; after rain, the next day is sunny with $0.4$ and rainy with $0.6$. Starting with a certainly sunny day, what is the weather distribution after two updates?

1. In the order (sun, rain), $P=\begin{bmatrix}0.8&0.2\\0.4&0.6\end{bmatrix}$ and $s_0=(1,0)$.
2. After one update, $s_1=s_0P=(0.8,0.2)$.
3. Use the new distribution for the second update: $s_2=s_1P=(0.8^2+0.2(0.4),\;0.8(0.2)+0.2(0.6))=(0.72,0.28)$.