Markov chains work by modelling a stochastic process whose next-state probability depends on the present state rather than the entire recorded past, once the state has been defined appropriately. A Markov chain uses states, transition probabilities and a transition matrix to describe random movement through time; matrix powers give multi-step probabilities, stationary distributions describe statistical equilibrium, and irreducibility, recurrence, periodicity and mixing determine whether long-run behaviour forgets its starting point. Markov chains sit at the centre of stochastic processes, queueing, reliability, PageRank and Markov Chain Monte Carlo.
The Markov property is a conditional-independence statement, not a claim that history never matters. Given the present state, the model says the future is independent of the earlier past. If age, velocity, fatigue or regime still changes future probabilities, the state may simply be too small.
The central mathematical question is how local transition rules create global long-run behaviour. A one-step transition matrix is easy to write; understanding communicating classes, stationary distributions, hitting times, return times, reversibility, spectral mixing and absorbing behaviour is where the theory becomes useful.
Quick Read
STATE → TRANSITION RULE → MATRIX / KERNEL → MULTI-STEP PROBABILITY → COMMUNICATING CLASSES → RECURRENCE → STATIONARY DISTRIBUTION → MIXING → HITTING TIMES → VALIDATION
1. The Markov Property
Write X₀,X₁,… for system states. The model is Markov when the conditional distribution of the next state given the complete past depends only on the present state under the chosen representation.
2. State Design Is Part of the Model
Position may need velocity; machine condition may need age; customer status may need contract type. A process can look non-Markov because its state is too small.
3. Transition Matrices
For a finite time-homogeneous chain, pᵢⱼ=P(Xₙ₊₁=j|Xₙ=i). The transition matrix is row-stochastic. Matrix powers give multi-step probabilities through Chapman–Kolmogorov composition.
4. Stationary Distributions
A probability vector π satisfying πP=π is stationary. Starting in π preserves the marginal distribution even though the realised state can keep changing.
5. Irreducibility, Periodicity and Recurrence
Irreducibility asks whether states communicate. Periodicity asks whether returns are trapped on a cycle. Recurrence asks whether states return, while positive recurrence controls expected return time. These properties determine what kind of long-run equilibrium is available.
6. Mixing
Two chains can share the same stationary distribution and approach it at radically different speeds. Mixing time measures how quickly starting-state information becomes negligible.
7. Eigenvalues and Spectral Structure
One is an eigenvalue of a finite transition matrix. Other eigenvalues control transient decay; a second eigenvalue magnitude close to one often signals slow mixing.
8. Hitting and Return Times
Hitting times ask when a target state is first reached. Return times ask when the chain revisits its current state. These quantities drive search, queueing, reliability and network calculations.
9. Absorbing Chains
An absorbing state transitions to itself with probability one. The fundamental matrix for transient states summarises expected visits and expected time before absorption.
10. Detailed Balance and Reversibility
If πᵢpᵢⱼ=πⱼpⱼᵢ for all pairs, the chain is reversible with respect to π and π is stationary. Reversibility is sufficient, not necessary.
11. Random Walks and PageRank
A random walk on a graph moves to a neighbouring node according to transition probabilities. PageRank adds teleportation to avoid traps and periodic structures and obtains a stable ranking distribution.
12. Queueing and Reliability
Memoryless arrival or service structures can produce Markov queue models. Reliability models use operational, degraded, failed and repaired states. The state must preserve whatever history still changes future risk.
13. Hidden Markov Models
Hidden Markov models add latent states that generate noisy observations. Filtering estimates current hidden state; smoothing revises past-state probabilities using later observations.
14. Markov Decision Processes
An MDP adds actions and rewards to Markov state transitions. The problem changes from describing stochastic evolution to choosing controls that optimise long-run or discounted value.
15. Markov Chain Monte Carlo
MCMC constructs a chain whose stationary distribution is a target probability distribution. Correct stationarity is only the first requirement; finite computation also depends on mixing and effective sample size. See How Monte Carlo Simulation Works.
16. Coupling
Coupling runs two chains with coordinated randomness. If they meet and move together, the meeting time can bound how quickly initial-state information disappears.
17. State Aggregation and Lumpability
Combining microstates can destroy the Markov property. Lumpability conditions identify cases where an aggregated process retains valid Markov transitions.
18. Continuous-Time Markov Chains
Continuous-time chains use a generator matrix of transition rates. Matrix exponentials produce transition probabilities over elapsed time; birth–death chains provide an important structured example.
19. Continuous State Spaces
A transition kernel replaces the finite matrix by assigning a next-state probability distribution to each current state. Stationarity, recurrence and mixing extend to these spaces.
20. Estimated Transitions Carry Uncertainty
Observed transition counts estimate probabilities. Rare transitions can be highly uncertain. Bayesian or hierarchical models can propagate that uncertainty rather than treating fitted transition rows as exact.
21. Nonstationary Chains
Time-homogeneous models assume one transition rule across time. Seasonality, ageing, policy changes and regime shifts may require time-varying transitions or a richer state.
22. What Markov Chains Preserve
They preserve sequential transition structure, state-dependent uncertainty, path probabilities, hitting questions and long-run occupancy when the state representation is adequate.
23. What the Compression Discards
A first-order Markov model discards historical information not encoded in the present state. That compression is valid only when omitted history carries no additional predictive information.
24. Hostile Tests
State too small: machine failure depends on age but age is omitted. Stationarity without convergence: a two-state alternator oscillates forever. Slow mixing: a chain can remain trapped in one region for a practically enormous time.
25. Practical Workflow
Define states, justify the Markov state, specify or estimate transitions, inspect communicating classes, solve stationary structure, analyse hitting and return times, measure mixing, test sensitivity and validate against observed sequences.
26. Canonical Boundary
This article owns Markov-chain mechanics. Stochastic Processes owns the wider family; Conditional Probability owns information restriction; Monte Carlo owns simulation broadly; Bayesian Inference owns posterior reasoning.
Final Thought
A Markov chain is a compact promise about memory. Its usefulness depends on whether the present state really contains what the future needs to know.