Markov chains model systems that move between possible states over time, such as weather patterns, customer choices, game positions, or population movement. This cheat sheet helps students organize the notation, matrix rules, and long-run predictions used in applied math. It is especially useful when problems involve repeated transitions and probabilities that depend only on the current state.
Students need these tools to predict future behavior and understand stable patterns in changing systems.
The core idea is that a transition matrix stores the probabilities of moving from one state to another in one step. A state vector describes the current probability distribution, and multiplying by the transition matrix updates the system. Long-run behavior often leads to a steady-state vector that stays the same after another transition.
Absorbing chains include states that cannot be left, which makes them useful for modeling endings such as graduation, failure, purchase, or extinction.
Key Facts
- A Markov chain has the Markov property, which means the next state depends only on the current state, not on the path used to get there.
- A transition probability P_ij is the probability of moving from state i to state j in one step.
- In a row-stochastic transition matrix, every row adds to 1 because each row lists all possible next states from one current state.
- If v is a row state vector and P is the transition matrix, then the next state vector is v_next = vP.
- After n steps, the state vector is v_n = v_0 P^n when using row vectors.
- A steady-state vector pi satisfies piP = pi and the entries of pi add to 1.
- An absorbing state has transition probability 1 of staying in itself, so P_ii = 1 and all other probabilities in that row are 0.
- For an absorbing chain in standard form, the fundamental matrix is N = (I - Q)^-1, where Q describes transitions among non-absorbing states.
Vocabulary
- Markov chain
- A probability model for a system that moves between states where the next state depends only on the current state.
- State
- A possible condition, category, or location that the system can occupy at a given time.
- Transition matrix
- A matrix that lists the probabilities of moving from each current state to each possible next state.
- State vector
- A vector whose entries give the probabilities that the system is in each state at a certain time.
- Steady-state distribution
- A probability distribution that does not change after applying the transition matrix.
- Absorbing state
- A state that the system cannot leave once it enters.
Common Mistakes to Avoid
- Mixing up rows and columns is wrong because the multiplication order depends on whether state vectors are written as rows or columns. If using row vectors, use v_next = vP and make rows of P add to 1.
- Forgetting that probabilities in each row must add to 1 is wrong because one of the listed next states must occur. A row total other than 1 usually means a missing, duplicated, or incorrect probability.
- Using Pn instead of P^n is wrong because n-step transitions require repeated matrix multiplication, not multiplying each entry by n. The matrix P^n gives probabilities after n steps.
- Assuming every Markov chain has a unique steady state is wrong because some chains are periodic, disconnected, or have multiple closed classes. Check the structure of the chain before interpreting long-run behavior.
- Treating an absorbing state like an ordinary state is wrong because once the system enters it, it stays there forever. Its row must have a 1 on the diagonal and 0 everywhere else.
Practice Questions
- 1 A system has row state vector v = [0.70, 0.30] and transition matrix P = [[0.80, 0.20], [0.40, 0.60]]. Find the state vector after one step.
- 2 For P = [[0.90, 0.10], [0.25, 0.75]], find the steady-state vector pi = [x, y] where piP = pi and x + y = 1.
- 3 A Markov chain has states A, B, and C. From A it moves to A with probability 0.5, to B with 0.3, and to C with 0.2. From B it moves to A with 0.1, to B with 0.7, and to C with 0.2. From C it stays in C with probability 1. Write the transition matrix using row-stochastic form.
- 4 Explain why a model that uses only the current weather to predict tomorrow's weather may be considered a Markov chain, but a model that also needs the weather from the past five days may not be a simple Markov chain.