Math AI HL: Markov Chains and Transition Matrices

Understanding how systems evolve over time is a central challenge in applied mathematics. Markov chains provide a powerful, probability-based framework for modeling such changes, from predicting tomorrow's weather to forecasting market trends. This concept, a cornerstone of the IB Math AI HL syllabus, equips you with the tools to analyze real-world stochastic processes using matrix algebra, turning uncertainty into quantifiable predictions.

Defining States and Transition Matrices

The foundation of any Markov model is the concept of states. A state represents a distinct, mutually exclusive condition in which a system can exist. For example, a weather system could be in the state "Sunny" or "Rainy." A consumer's brand loyalty might be in the state "Buys Brand A" or "Buys Brand B." We describe the system's current condition using a state vector, which is a column matrix showing the probability distribution across all possible states at a given time. If today has an 80% chance of being sunny and a 20% chance of being rainy, the initial state vector, $S_0$, would be: $$S_0=\left[\begin{array}{c}0.8\\ 0.2\end{array}\right]$$ where the top entry corresponds to "Sunny" and the bottom to "Rainy."

The engine of change is the transition matrix, denoted $T$. This square matrix contains the conditional probabilities of moving from one state to another in a single step. Each entry $t_{ij}$ represents the probability of transitioning to state $i$ from state $j$. It is crucial to set up this matrix correctly: columns must represent the current state, and rows represent the next state. For our weather example, if a sunny day has a 70% chance of being followed by another sunny day, and a rainy day has a 40% chance of being followed by a sunny day, the transition matrix is: $$T=\left[\begin{array}{cc}0.7& 0.4\\ 0.3& 0.6\end{array}\right]$$

Predicting Future States with Matrix Multiplication

Once you have an initial state vector $S_0$ and a transition matrix $T$, predicting the state distribution after $n$ steps is a direct application of matrix multiplication. The state vector after one step, $S_1$, is found by calculating $S_1=T\times S_0$. For our weather example: $$S_1=T\times S_0=\left[\begin{array}{cc}0.7& 0.4\\ 0.3& 0.6\end{array}\right]\left[\begin{array}{c}0.8\\ 0.2\end{array}\right]=\left[\begin{array}{c}(0.7\times 0.8)+(0.4\times 0.2)\\ (0.3\times 0.8)+(0.6\times 0.2)\end{array}\right]=\left[\begin{array}{c}0.64\\ 0.36\end{array}\right]$$ This result tells us that tomorrow, the probability of a sunny day is 64% and rainy is 36%.

To project further into the future, you simply multiply by the transition matrix repeatedly. The state after $n$ steps is given by $S_n=T^n\times S_0$, where $T^n$ is the transition matrix raised to the $n$th power. This elegant formula allows for long-term forecasting. For instance, calculating $S_3=T^3\times S_0$ would give the forecast for three days from now. This process assumes the Markov property: the probability of transitioning to a future state depends only on the current state, not on the sequence of events that preceded it.

Finding the Steady-State Probability Vector

For many Markov chains, as $n$ becomes very large, the state vector $S_n$ converges to a fixed distribution called the steady-state or long-run probability vector, often denoted $S$. This vector remains unchanged when multiplied by the transition matrix, satisfying the equation $T\times S=S$. The steady-state vector represents the equilibrium of the system, showing the proportion of time the system spends in each state over the long term.

To find $S$, you solve the matrix equation $T\times S=S$ along with the condition that the entries of $S$ sum to 1. This is equivalent to solving a system of linear equations. Using our weather matrix $T=\left[\begin{array}{cc}0.7& 0.4\\ 0.3& 0.6\end{array}\right]$, and letting $S=\left[\begin{array}{c}x\\ y\end{array}\right]$, we have:

1. $T\times S=S$ gives: $0.7x+0.4y=x$ and $0.3x+0.6y=y$.
2. The first equation simplifies to $-0.3x+0.4y=0$.
3. The normalization condition is $x+y=1$.

Solving this system (e.g., from $-0.3x+0.4y=0$, we get $y=0.75x$; substituting into $x+y=1$ gives $x+0.75x=1$, so $x=0.571$ and $y=0.429$). Therefore, the steady-state vector is approximately: $$S\approx \left[\begin{array}{c}0.571\\ 0.429\end{array}\right]$$ This means that, over a long period, approximately 57.1% of days will be sunny and 42.9% will be rainy, regardless of the starting weather. Not all chains have a unique steady state (some may oscillate or have absorbing states), but for standard, regular Markov chains, this long-run equilibrium is a key feature.

Applications in Modeling Real-World Processes

Markov chains are not abstract mathematical toys; they are directly applicable to a wide range of disciplines. In modeling weather patterns, states represent meteorological conditions, and transition probabilities are derived from historical data, allowing for short and long-term climate forecasts. In business and economics, they are used to analyze market share. Companies can model consumers switching between brands (states) based on monthly transition probabilities. The steady-state vector, in this context, predicts the eventual market share each brand will capture if current trends continue, which is vital for strategic planning.

Another powerful application is modeling population movement between regions, such as migration between cities or rural areas. Here, states are geographical regions, and transition probabilities represent the likelihood of a person moving from one region to another in a given time period (e.g., annually). The initial state vector gives the current population distribution. By calculating future state vectors, urban planners can forecast population changes. The steady-state analysis reveals the long-term distribution of the population, informing infrastructure and resource allocation decisions for decades to come.

Common Pitfalls

1. Incorrectly Setting Up the Transition Matrix: The most frequent error is confusing rows and columns. Remember: the column represents the "from" state, and the row represents the "to" state. A quick check is that each column of the transition matrix must sum to 1. If your columns don't sum to 1, your conditional probabilities are incorrect.
2. Misinterpreting the Steady-State Vector: The steady-state vector $S$ does not mean the system gets "stuck" in one state. It means the probability distribution stabilizes. The system continues to transition between states, but the proportion of time spent in each state becomes constant. It is also not dependent on the initial state $S_0$ for a regular chain, which is a counterintuitive but important result.
3. Forgetting the Markov Property: Applying Markov chains requires the Markov assumption to be reasonably valid. If the probability of a future event depends on more than just the current state (e.g., if brand loyalty depends on a customer's entire purchase history, not just their last purchase), then a basic Markov model may give misleading results. Always consider if the system has a "memory" longer than one step.
4. Algebraic Errors in Finding the Steady State: When solving $T\times S=S$, remember this is a homogeneous system ($T\times S-S=0$). One of the equations from $T\times S=S$ will be redundant (linearly dependent). You must replace it with the normalization equation $sum(\text{entries of }S)=1$ to get a unique, solvable system. Attempting to solve with only the equations from $T\times S=S$ will lead to an infinite number of solutions.

Summary

• A Markov chain models a system that moves between defined states according to fixed probabilities, relying only on its current state (the Markov property).
• The system's current condition is described by a state vector $S_n$, and its dynamics are encoded in a transition matrix $T$, where columns (from) sum to 1.
• Future states are predicted by repeated matrix multiplication: $S_n=T^n\times S_0$. This allows for multi-step forecasting of probabilistic systems.
• The steady-state probability vector $S$, found by solving $T\times S=S$ with the normalization condition, represents the long-run equilibrium distribution and is independent of the starting state for regular chains.
• These tools have wide-ranging applications, including forecasting weather patterns, analyzing market share competition, and modeling population migration, making them essential for quantitative analysis in numerous fields.