A Markov chain is a model for a system that moves between possible states, such as weather changing from sunny to rainy or a website user moving between pages. It is useful because many real situations involve repeated steps with uncertainty. Instead of predicting one exact future path, a Markov chain describes the probabilities of many possible paths.
This makes it a powerful tool in statistics, physics, computer science, economics, and biology.
The key idea is the memoryless property: the next state depends only on the current state, not on the full history of how the system got there. Transition probabilities tell how likely each move is, and these probabilities are often organized in a transition matrix. By multiplying probability vectors by the transition matrix, you can predict the distribution of states after many steps.
In many chains, the probabilities approach a steady state, where the long-run distribution stops changing.
Key Facts
- Memoryless property: P(X_{n+1} = j | X_n = i, past states) = P(X_{n+1} = j | X_n = i).
- A transition probability p_ij is the probability of moving from state i to state j in one step.
- Each row of a transition matrix sums to 1: p_i1 + p_i2 + ... + p_ik = 1.
- If v_n is a row vector of state probabilities, then v_{n+1} = v_n P.
- After two steps, the transition matrix is P^2, and after n steps it is P^n.
- A steady state distribution pi satisfies pi = pi P and the probabilities in pi sum to 1.
Vocabulary
- State
- A state is one possible condition or category that the system can be in 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 table of transition probabilities for all possible moves between states.
- Memoryless property
- The memoryless property means the next state depends only on the current state and not on earlier states.
- Steady state
- A steady state is a long-run probability distribution that stays the same after applying the transition matrix.
Common Mistakes to Avoid
- Forgetting that each row of the transition matrix must sum to 1. This is wrong because the entries in a row represent all possible next states from one current state.
- Using the full history to compute the next step in a basic Markov chain. This is wrong because the Markov property says only the current state matters.
- Mixing up row vectors and column vectors when multiplying by the transition matrix. This is wrong because v_{n+1} = v_n P uses a row vector, while column-vector notation usually uses v_{n+1} = P v_n.
- Assuming every Markov chain has one simple steady state. This is wrong because some chains are periodic, reducible, or have absorbing states that change the long-run behavior.
Practice Questions
- 1 A two-state Markov chain has transition matrix P = [[0.7, 0.3], [0.4, 0.6]]. If the current distribution is v_0 = [1, 0], find v_1.
- 2 For P = [[0.8, 0.2], [0.1, 0.9]], solve for the steady state distribution pi = [x, y] where pi = pi P and x + y = 1.
- 3 A student says a Markov chain cannot model weather because yesterday's weather also matters. Explain when a Markov chain could still be a useful weather model and what assumption it makes.