A Markov chain is a mathematical model for a system that moves from one state to another with fixed probabilities. It is useful when the next state depends only on the current state, not on the full history of how the system got there. This idea appears in weather prediction, board games, genetics, search engines, and customer behavior.
Transition matrices give a compact way to store and calculate these probabilities.
Each entry in a transition matrix tells the probability of moving from one state to another in one step. Multiplying a probability vector by the transition matrix predicts the distribution after the next step, and using powers of the matrix predicts many steps into the future. In many Markov chains, repeated transitions lead to a steady-state distribution that stops changing.
This steady state describes the long-run fraction of time the system spends in each state.
Key Facts
- A Markov chain has the Markov property: the next state depends only on the current state.
- A transition probability satisfies 0 ≤ Pij ≤ 1 for every pair of states i and j.
- For a row-stochastic transition matrix, each row sums to 1: Σj Pij = 1.
- If p0 is the starting probability row vector, then after n steps pn = p0 P^n.
- A steady-state distribution π satisfies πP = π and Σi πi = 1.
- For a regular Markov chain, P^n approaches a matrix whose rows are the steady-state distribution.
Vocabulary
- State
- A state is one possible condition or category the system can occupy at a given step.
- Transition probability
- A transition probability is the chance that the system moves from one state to another in one step.
- Transition matrix
- A transition matrix is a square matrix that stores all one-step transition probabilities between states.
- Probability vector
- A probability vector lists the probabilities of being in each state, and its entries add to 1.
- Steady state
- A steady state is a probability distribution that remains unchanged after applying the transition matrix.
Common Mistakes to Avoid
- Forgetting that probabilities in each row must add to 1 is wrong because a row represents all possible next states from one current state.
- Multiplying matrices in the wrong order is wrong because row-vector models use pn = p0 P^n, while column-vector models use pn = P^n p0.
- Treating P^n as nP is wrong because matrix powers mean repeated matrix multiplication, not multiplying every entry by n.
- Assuming every Markov chain has a unique steady state is wrong because some chains are periodic, disconnected, or have absorbing classes that change long-run behavior.
Practice Questions
- 1 A weather model has states Sunny and Rainy with transition matrix P = [[0.8, 0.2], [0.4, 0.6]]. If today is Sunny, what is the probability distribution after one day?
- 2 For P = [[0.7, 0.3], [0.2, 0.8]], find the steady-state distribution π = [x, y] by solving πP = π and x + y = 1.
- 3 A chain has three states A, B, and C. From A it always stays in A, while B and C can move between each other but never reach A. Explain why the long-run result depends on the starting state.