Understanding Markov Chains and Transition Matrices

Markov chains are a cornerstone of probability theory and stochastic processes. They provide a mathematical framework for modelling systems that evolve over discrete time steps, where the future state depends solely on the current state. For undergraduate mathematicians, mastering these concepts is essential for success in modules covering probability, operational research, and statistical modelling.

In this article, we will explore the mechanics of transition matrices, how to calculate state distributions over time, and the significance of the stationary distribution. By the end, you will have a robust understanding of how to apply these tools to solve complex problems in your exams.

The Markov Property and State Spaces

A stochastic process ${X_n}{n \ge 0}$ is a Markov chain if it satisfies the Markov property: the probability of moving to the next state depends only on the present state, not on the history of how the system arrived there. Formally, $P(X{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j | X_n = i)$.

The state space $S$ is the set of all possible values the process can take. If $S$ is finite, we can represent the transition probabilities in a matrix.

Constructing Transition Matrices

A transition matrix $P$ is a square matrix where the entry $p_{ij}$ represents the probability of moving from state $i$ to state $j$ in one step.

Key Properties:

1. Each entry $p_{ij} \ge 0$.
2. The sum of each row must equal 1 (since the system must move to some state).

Example 1: Consider a weather model with two states: Sunny (S) and Rainy (R). If it is sunny, there is a 0.8 probability it stays sunny and 0.2 it rains. If it is rainy, there is a 0.4 probability it stays rainy and 0.6 it turns sunny. The transition matrix $P$ is:

$$P = \begin{pmatrix} 0.8 & 0.2 \ 0.6 & 0.4 \end{pmatrix}$$

N-Step Transitions

To find the probability of being in a specific state after $n$ steps, we use the initial state vector $v_0$ and the transition matrix $P$. The distribution after $n$ steps is given by $v_n = v_0 P^n$.

Example 2: Using the matrix from Example 1, if today is sunny ($v_0 = [1, 0]$), what is the probability it is sunny in two days?

First, calculate $P^2$: $$P^2 = \begin{pmatrix} 0.8 & 0.2 \ 0.6 & 0.4 \end{pmatrix} \begin{pmatrix} 0.8 & 0.2 \ 0.6 & 0.4 \end{pmatrix} = \begin{pmatrix} 0.64+0.12 & 0.16+0.08 \ 0.48+0.24 & 0.12+0.16 \end{pmatrix} = \begin{pmatrix} 0.76 & 0.24 \ 0.72 & 0.28 \end{pmatrix}$$

Then $v_2 = [1, 0] \begin{pmatrix} 0.76 & 0.24 \ 0.72 & 0.28 \end{pmatrix} = [0.76, 0.24]$. There is a 76% chance it will be sunny in two days.

The Stationary Distribution

A stationary distribution $\pi$ is a probability vector such that $\pi P = \pi$. Intuitively, if the system starts in this distribution, it remains there indefinitely. To find $\pi$, solve the system of linear equations $\pi P = \pi$ subject to the constraint $\sum \pi_i = 1$.

For our weather example: $[\pi_1, \pi_2] \begin{pmatrix} 0.8 & 0.2 \ 0.6 & 0.4 \end{pmatrix} = [\pi_1, \pi_2]$

This gives $0.8\pi_1 + 0.6\pi_2 = \pi_1$, which simplifies to $0.6\pi_2 = 0.2\pi_1$, or $\pi_1 = 3\pi_2$. Since $\pi_1 + \pi_2 = 1$, we have $3\pi_2 + \pi_2 = 1$, so $4\pi_2 = 1$. Thus, $\pi_2 = 0.25$ and $\pi_1 = 0.75$. The stationary distribution is $[0.75, 0.25]$.

Common Mistakes

1. Row vs Column Sums: Always ensure your rows sum to 1. If your columns sum to 1, you have likely transposed your matrix.
2. Initial Vector Order: Ensure your initial state vector $v_0$ matches the order of states in your matrix $P$.
3. Ignoring the Constraint: When solving for the stationary distribution, students often forget the constraint $\sum \pi_i = 1$, leading to an infinite number of solutions.

Frequently Asked Questions

What is the difference between a state and a state space? A state is a specific condition (e.g., 'Sunny'), while the state space is the set of all possible states (e.g., {'Sunny', 'Rainy'}).

Does every Markov chain have a stationary distribution? Not necessarily. A chain must be irreducible and positive recurrent to guarantee a unique stationary distribution.

Can transition matrices be non-square? No, a transition matrix must be square because the set of possible states at time $t$ must be the same as at time $t+1$.

Conclusion

Markov chains are powerful tools for predicting long-term behaviour in stochastic systems. By mastering transition matrices and the calculation of stationary distributions, you are well-equipped for your undergraduate assessments. To see these concepts brought to life with visualisations and step-by-step narrations, visit MathInstructor AI to generate a free animated lesson on this topic.