IB Maths AI 4.14 Notes

Markov chains & transition matrices

Transition matrices are used to model systems that move between a fixed set of states in steps. At each step, there is a probability of moving from one state to another. These systems are called Markov chains.

A Markov chain is a process in which the next state depends only on the current state. It does not depend on the earlier history of the system.

Examples include customer brand switching, weather changes, movement between towns, and population movement between categories.

A state is one of the possible positions or conditions of the system. For example, a person may be in state $A$, $B$, or $C$. A transition diagram shows the possible moves between these states, with arrows labelled by probabilities.

Image reference: transition diagram with three states and probabilities on arrows.

The probabilities leaving a state must add to $1$, since the system must move somewhere.

A transition matrix records the probabilities of moving between states. Using the column-state convention, the entry $T_{ij}$ gives the probability of moving from state $j$ to state $i$. This means each column of the matrix adds to $1$.

If there are three states, the transition matrix may look like:

$T=\begin{pmatrix}T_{ii}&&T_{ij}&&T_{ik}\\T_{ji}&&T_{jj}&&T_{jk}\\T_{ki}&&T_{kj}&&T_{kk}\end{pmatrix}$

Here, the first column gives the probabilities of moving from state $1$, the second column gives the probabilities of moving from state $2$, and the third column gives the probabilities of moving from state $3$.