Markov Chains Explained
Represent a stochastic process with a transition matrix and study state evolution via matrix powers. Explore conditions for a unique stationary distribution and mixing rates.
📚 Fundamentals
- Memoryless: next state depends only on current state.
- Transition matrix: rows sum to 1; non-negative entries.
- n-step transitions: given by powers Pⁿ.
Stationarity
A distribution π is stationary if πP = π. Under irreducible and aperiodic conditions, the chain converges to a unique π.
🧪 Examples
Weather model with states {Sunny, Cloudy, Rainy} and plausible transition probabilities; compute long-run frequencies.
❓ Frequently Asked Questions
1) What is ergodicity?
Conditions ensuring convergence to a unique stationary distribution.
Conditions ensuring convergence to a unique stationary distribution.
2) How to find π?
Solve (Pᵀ - I)π = 0 with normalization or power iteration.
Solve (Pᵀ - I)π = 0 with normalization or power iteration.
3) What is mixing time?
How fast distributions converge to stationarity.
How fast distributions converge to stationarity.
4) Periodicity?
If returns occur at multiples >1, convergence may oscillate.
If returns occur at multiples >1, convergence may oscillate.
5) Absorbing states?
States that, once entered, cannot be exited (row with 1 on diagonal).
States that, once entered, cannot be exited (row with 1 on diagonal).
6) Reversible chains?
Satisfy detailed balance: π(i)P(i,j)=π(j)P(j,i).
Satisfy detailed balance: π(i)P(i,j)=π(j)P(j,i).
7) Continuous-time chains?
Use generators instead of transition matrices.
Use generators instead of transition matrices.
8) Relation to MCMC?
MCMC constructs chains whose stationary distribution is the target posterior.
MCMC constructs chains whose stationary distribution is the target posterior.
9) Graph interpretation?
P is a weighted adjacency matrix of a directed graph.
P is a weighted adjacency matrix of a directed graph.
10) PageRank?
A Markov chain on the web graph with teleportation to ensure ergodicity.
A Markov chain on the web graph with teleportation to ensure ergodicity.