Lesson 259
Markov Chains
States, Transitions & the Stationary Distribution
1:00How Markov chains model systems that hop between states using only the present — covering the transition matrix, stationary distribution, ergodicity, absorbing states, and applications from PageRank to MCMC.
By the end, you can
- State the Markov property and explain why a chain is called "memoryless" — the next state depends only on the current state, not on the path taken to reach it.
- Read a state graph and write the corresponding transition matrix P, verifying that each row sums to 1 (every state's outgoing probabilities form a complete distribution).
- Compute multi-step transition probabilities by multiplying the distribution vector by P^n.
- Solve for the stationary distribution pi by hand (for a small chain) using pi*P = pi.
- Define irreducibility and aperiodicity, and explain why both are required for ergodicity.
- Identify absorbing states and explain what the fundamental matrix gives you.
- Describe how PageRank uses the stationary distribution of a web-graph Markov chain.
- Explain what MCMC does differently from standard Markov chain analysis.
- Distinguish "memoryless" from "patternless" and give an example of structure that emerges.
Up next in Advanced Algorithms, Math & PL Theory
