4.19 Transition matrices and Markov chainsIB Maths: Applications and Interpretation HL: Revision notes

A system that moves between a fixed set of states, where the next state depends only on the current one, is described by a transition matrix $T$. In this course $T_{ij}$ is the probability of moving from state $j$ to state $i$, so each column sums to 1. A transition diagram shows the same information: one node per state and an arrow for each move, labelled with its probability (a loop for staying put). Example: rain (R) or dry (D). After a rainy day, rain again with probability $0.8$; after a dry day, rain with probability $0.3$. $T=\begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix}$ Column 1 is 'from R', column 2 is 'from D'. This has the same layout as an adjacency matrix for the diagram, except that the entries are probabilities rather than counts of edges.

The initial state matrix $\mathbf{s}_0$ is a column giving the probability (or number) in each state at the start. After one transition $\mathbf{s}_1=T\mathbf{s}_0$, and in general $\mathbf{s}_n=T^n\mathbf{s}_0.$ The entry $(T^n)_{ij}$ is the probability of moving from state $j$ to state $i$ in exactly $n$ steps. Use your GDC for powers. Example: it is dry today, so $\mathbf{s}_0=\begin{pmatrix} 0 \\ 1 \end{pmatrix}$. Then $\mathbf{s}_1=\begin{pmatrix} 0.3 \\ 0.7 \end{pmatrix}$ and $\mathbf{s}_2=T\mathbf{s}_1=\begin{pmatrix} 0.45 \\ 0.55 \end{pmatrix}$: a probability $0.45$ of rain in two days.

A Markov chain is regular if some power of $T$ has all entries positive. Then $\mathbf{s}_n$ approaches the same steady state whatever $\mathbf{s}_0$ is, and $T^n$ settles to a matrix with identical columns. There are two methods.

• Repeated multiplication: calculate $T^n\mathbf{s}_0$ for a large $n$ on your GDC until the values stop changing.
• Solve $T\mathbf{s}=\mathbf{s}$ together with the entries summing to 1 (use this when an exact answer is demanded). Example with the rain matrix: $T\mathbf{s}=\mathbf{s}$ gives $0.8r+0.3d=r$, so $0.2r=0.3d$ and $r=1.5d$. With $r+d=1$: $d=0.4$ and $r=0.6$. So in the long term it rains on $60\%$ of days.

The equation $T\mathbf{s}=\mathbf{s}$ says that $\mathbf{s}$ is an eigenvector of $T$ with eigenvalue 1. A transition matrix always has the eigenvalue 1. To use this, solve $(T-I)\mathbf{v}=\mathbf{0}$, then scale $\mathbf{v}$ so its entries sum to 1. For the rain matrix, $\det(T-\lambda I)=(0.8-\lambda)(0.7-\lambda)-0.06=0$ gives $\lambda=1$ or $\lambda=0.5$. For $\lambda=1$: $-0.2r+0.3d=0$, so $\mathbf{v}=\begin{pmatrix} 3 \\ 2 \end{pmatrix}$, and scaling gives $\begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix}$. The other eigenvalue has size less than 1, which is why its contribution fades as $n$ grows and $\mathbf{s}_n$ tends to the steady state.

Markov chains model discrete dynamical systems: weather, customer loyalty, population movement, machine states. Read the question for the ordering of states and whether the state matrix is a count or a probability.

• Write $T$ with columns summing to 1 and check.
• Use $\mathbf{s}_n=T^n\mathbf{s}_0$ for a specific time.
• For the long term, use a high power or solve $T\mathbf{s}=\mathbf{s}$ with sum 1.
• Give answers in context, as probabilities or numbers of people, to 3 s.f.
• If $T$ contains an unknown $p$, use the steady-state equations to find it.