Advanced undergraduateProbability & StatisticsPlanned
Markov chains
Discrete-time Markov chains: transition matrices, classification of states, stationary distributions, convergence to equilibrium, hitting times and random walks.
math.prob.markov-chains
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Required prerequisites, all the way down: 42
You will learn to
- Model processes with transition matrices and compute n-step transition probabilities.
- Classify states as recurrent or transient and find stationary distributions.
- Prove convergence to equilibrium for irreducible aperiodic finite chains.
Definition
- A Markov chain is a sequence of random variables in which the conditional distribution of the next state, given the past, depends only on the current state.
- A probability distribution π (as a row vector) is stationary for transition matrix P if πP = π.
- A chain is irreducible if every state can be reached from every other state.
Theorem
- An irreducible Markov chain on a finite state space has a unique stationary distribution.
- If it is also aperiodic, the distribution at time n converges to the stationary distribution from any starting distribution.
- Pólya: simple random walk is recurrent on ℤ and ℤ² and transient on ℤ³.
Common misconceptions
- Reading 'memoryless' as 'forgets everything'; it means the future depends on the past only through the present.
Leads to
Optional discoveries
- Mathematical biology Stochastic models of populations and of genetic drift, such as the Wright–Fisher model, are Markov chains.
Further reading
- J. R. Norris, Markov Chains (1997)