Markov Chains, HMMs & Filters
Reasoning about processes that unfold in time.
A phone fuses jittery satellite fixes with its accelerometer, a speech recognizer turns noisy audio into words, a robot works out where it is from a door sensor. Each tracks a hidden state through time with the same recursion: push the belief through a model of how the world moves, then reweight it by what the sensors report. This lesson derives that recursion for discrete states (hidden Markov models), for linear-Gaussian states (the Kalman filter) and for everything else (particle filters).
What you’ll learn
- Compute multi-step transition probabilities and stationary distributions of Markov chains, and state when a chain converges to its stationary distribution.
- Derive the forward (filtering) recursion and the forward–backward smoothing algorithm for hidden Markov models, with their cost.
- Derive the Viterbi algorithm for the most likely state sequence, and explain how its answer differs from smoothing.
- Derive the Kalman filter's predict and update steps in one dimension, state them in general, and explain why particle filters resample.
Markov chains and their long run
A Markov chain is a sequence of random states with the Markov property: the future depends on the past only through the present, . For a finite, time-homogeneous chain, collect the transition probabilities in a row-stochastic matrix . A distribution over states is a row vector, and one step multiplies it by :
The weather of the umbrella world is such a chain: rain follows rain with probability 0.7, and a dry day is followed by rain with probability 0.3.
It rains today. In the umbrella world's weather chain, what is the probability that it rains the day after tomorrow?
Show the answer
58 %
Sum over tomorrow's weather: . That is the (rain, rain) entry of . A day later it is , then : the chain forgets today's weather.
A stationary distribution satisfies : a left eigenvector of with eigenvalue 1. A finite chain that is irreducible (every state can reach every other) and aperiodic (returns to a state are not restricted to multiples of some period greater than 1) has exactly one, and from every starting distribution. The time averages along one long run also converge to , which is what lets MCMC replace integrals by averages.
Let and , and write for the probability of rain on day :
The fixed point is the stationary probability of rain:
Subtracting the fixed-point equation, the distance to it shrinks by the factor every day. That number is the second eigenvalue of (the first is 1):
For the umbrella world , so and the gap shrinks by a day: starting from rain, In general the gap between and 1, the spectral gap, sets the speed of forgetting.
Two facts about stationarity come up again and again:
- Detailed balance. If for all , then is stationary: sum over to get . Metropolis–Hastings and Gibbs samplers are built this way (Bayesian Reasoning).
- PageRank. A random surfer follows a random link with probability and jumps to a uniformly random page otherwise. The ranking is the stationary distribution of this chain; the random jumps make it irreducible and aperiodic, so repeatedly multiplying by the transition matrix converges.
Periodicity is the trap: a chain that alternates deterministically between two states has stationary distribution , but flips back and forth forever.
Hidden Markov models and filtering
In a hidden Markov model the chain is hidden, and at each step it emits an observation through a sensor model . The joint distribution is a Bayesian network shaped like a comb, with one evidence leaf per time step:
Four questions come up: filtering , the belief now; prediction ; smoothing for a past step ; and the most likely explanation .
Split off the newest observation and apply Bayes' rule. Given , the new observation is independent of the older ones:
Predict by conditioning on the current state, which by the Markov property screens off the older evidence:
Together, with as a column vector and the diagonal matrix of , one step costs for states, and memory does not grow with :
Umbrella world, umbrellas on days 1 and 2, with and . Day 1 predicts and updates to ; day 2 predicts and updates:
The normalizers are worth keeping: at step is , so their product is the likelihood of the whole observation sequence, , the quantity used to compare models and to learn parameters. Products of many small numbers underflow, so implementations normalize at every step and add up the logarithms of the normalizers.
Smoothing: forward–backward
Filtering uses only the past. Whether it rained yesterday is better judged once you know that the director carried an umbrella today as well, because rain tends to persist. Smoothing computes for by combining a forward message with a backward message , the probability of the future evidence given the state at .
Split the evidence at . Given , the future evidence is independent of the past evidence (d-separation in the chain); multiplies vectors elementwise:
The backward message satisfies a recursion that runs from down to , starting from :
Umbrella world, day 1 given both days: . Day 2's umbrella raises the belief in rain on day 1 from 0.818 to 0.883:
Run the forward pass and store every , then sweep backward, multiplying as you go: all smoothed estimates for time and memory, instead of for separate computations.
The most likely sequence: Viterbi
For speech recognition, the right output is the single most likely sequence of words, not the most likely word at each instant considered separately. The most likely explanation maximizes the joint probability of the whole hidden path, and the Viterbi algorithm finds it by replacing the sum in the forward recursion with a maximum.
Let be the probability of the best path that ends in , jointly with the evidence. The best path ending in must extend the best path ending in some (optimal substructure):
Record which achieved each maximum (a backpointer). At the end, start from the best final state and follow the backpointers to recover the path:
The cost is the same as filtering, , plus backpointers. Implementations add log-probabilities instead of multiplying probabilities, which avoids underflow and turns the recursion into a shortest-path computation on a trellis.
| Day | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Umbrella | yes | yes | no | yes | yes |
| Filtered P(rain) | 0.818 | 0.883 | 0.191 | 0.731 | 0.867 |
| Smoothed P(rain) | 0.867 | 0.820 | 0.307 | 0.820 | 0.867 |
| Viterbi | 0.818 | 0.515 | 0.036 | 0.033 | 0.021 |
| Viterbi | 0.182 | 0.049 | 0.124 | 0.017 | 0.002 |
| Most likely path | rain | rain | dry | rain | rain |
Which statement about the Viterbi path and the smoothed estimates is true in general?
- The Viterbi path always consists of the individually most likely (smoothed) states
- Viterbi is a fast approximation to forward–backward smoothing
- The two can disagree, and the sequence of individually most likely states can even have probability zero
- They agree whenever the hidden chain is irreducible and aperiodic
Show the answer
C. The two can disagree, and the sequence of individually most likely states can even have probability zero
Smoothing maximizes each step's marginal separately; Viterbi maximizes the probability of the whole sequence. If the paths (A, B), (C, A) and (C, C) have probabilities 0.4, 0.3 and 0.3, the individually most likely states are C and then B, a sequence of probability zero, while Viterbi returns (A, B).
So far the model was given. Baum–Welch learns , the sensor model and the prior from observation sequences alone. It is the EM algorithm: forward–backward computes the expected number of times each transition and each emission occurred, and the parameters are re-estimated as normalized expected counts. Each iteration never decreases the likelihood , but it can stop at a local optimum, so restarts matter.
Continuous states: the Kalman filter
Position and velocity are continuous. In a linear-Gaussian state-space model, the state evolves linearly with Gaussian noise and the sensor measures a linear function of it with Gaussian noise:
A Gaussian belief stays Gaussian under both steps, so the Kalman filter only has to track a mean and a covariance.
Take a random walk with , measured as with . Predict: independent variances add.
Update: the posterior is proportional to . Completing the square in , precisions add and the mean is a precision-weighted average:
Rewrite with the Kalman gain , the fraction of the surprise (the innovation) that the estimate absorbs:
Example: , , and a measurement . The prediction has variance 2, so :
A Kalman filter's predicted variance is and the sensor noise variance is . A measurement arrives 5 units above the predicted mean. What happens?
- The mean moves up 4 units and the variance drops to 0.8
- The mean moves up 5 units and the variance drops to 1
- The mean moves up 2.5 units and the variance drops to 2.5
- The mean moves up 1 unit and the variance drops to 3.2
Show the answer
A. The mean moves up 4 units and the variance drops to 0.8
, so the mean moves units and the variance becomes , below both the prediction's 4 and the sensor's 1. A precise sensor () pulls the estimate most of the way to the measurement; a noisy one () gives , and the measurement is ignored.
Nonlinear models are handled by linearizing and around the current estimate (the extended Kalman filter) or by pushing a few deterministically chosen sigma points through the nonlinearity (the unscented Kalman filter). Both keep a single Gaussian, so neither can represent a belief with two separate peaks, such as a robot that might be in either of two identical corridors.
Particle filters, dynamic Bayes nets, and where to go deeper
When the belief is multimodal or the model is far from linear-Gaussian, represent the belief by samples, called particles. A particle filter runs the same predict–update loop on them, and adds a third step, resampling:
function PARTICLE-FILTER(particles x[1..N], action a, observation z):
for i = 1 to N:
x[i] ← a sample from P(X_t | X_{t−1} = x[i], a) # predict: move each particle
w[i] ← P(z | X_t = x[i]) # update: weight by the sensor
normalize w so that it sums to 1
x ← N draws, with replacement, from x[1..N] with probabilities w # resample
return x # the new belief, as N samplesSequential importance resampling with the motion model as proposal, the "bootstrap" filter of Gordon, Salmond & Smith (1993). The empirical distribution of the particles approximates the filtering distribution, with error of order at each fixed time.
All of these models are dynamic Bayesian networks (DBNs): a Bayesian network slice repeated over time. An HMM is a DBN with one discrete state variable per slice, and the Kalman filter's model is a DBN with linear-Gaussian conditionals. Factoring the state into variables keeps the transition model small ( small CPTs instead of a matrix), but exact filtering still needs all joint values of the belief: after a few steps, every state variable becomes correlated with every other, even when their dynamics interact only locally. Approximate filters, such as projecting the belief onto a factored form after each step (Boyen & Koller, 1998) and particle filters, are the practical answer.
Key takeaways
- A Markov chain evolves as . Irreducible, aperiodic finite chains converge to a unique stationary distribution , at a rate set by the second eigenvalue (for two states, ).
- Filtering in an HMM is predict-then-update: , at per step; the normalizers multiply to the likelihood .
- Smoothing multiplies forward and backward messages, ; forward–backward gives every smoothed estimate in time.
- Viterbi replaces the sum by a max and follows backpointers to the single most likely sequence, which can differ from the sequence of individually most likely states. Baum–Welch learns the model by EM from forward–backward's expected counts.
- The Kalman filter predicts by adding process noise and updates by adding precisions, with gain ; it is exact for linear-Gaussian models. Particle filters handle anything else with weighted samples, and resample to fight weight degeneracy.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A two-state chain moves from to with probability 0.1 and from to with probability 0.3. What fraction of the time does it spend in in the long run?
- 0.25
- 0.5
- 0.75
- 0.9
Show the answer
C. 0.75
, where is the rate of leaving and the rate of entering it. Check balance: the flow is , and is .
An HMM has hidden states and you observe a sequence of length . About how many multiply–add operations does the forward algorithm need to compute ?
- About
- About
- About
- About
Show the answer
B. About
Each step multiplies a 100-vector by a matrix, operations, and there are steps: . Summing over all hidden sequences directly would be hopeless.
A speech recognizer must output one transcript for a recorded utterance, using an HMM over phones. Which computation should it run?
- Filtering, at every step
- Smoothing, then the most likely phone at each step
- The Viterbi algorithm
- Prediction,
Show the answer
C. The Viterbi algorithm
A transcript is one sequence, so the right objective is the most likely sequence, . Stringing together per-step maxima can produce a sequence that the model considers unlikely or even impossible.
Two independent sensors measure the same quantity: one reads 10 with noise variance 4, the other reads 14 with noise variance 4. With a flat prior, what is the Gaussian posterior?
- Mean 12, variance 2
- Mean 12, variance 4
- Mean 12, variance 8
- Mean 14, variance 2
Show the answer
A. Mean 12, variance 2
Precisions add, , so the variance is 2, and the mean is the precision-weighted average, here the plain average 12. This is exactly the Kalman update, with one sensor playing the role of the prediction.
What problem does the resampling step of a particle filter address?
- It removes the bias of the motion model
- It makes the particles independent of each other
- It reduces the cost of each step from to
- Weight degeneracy: without it, a few particles soon carry almost all the weight
Show the answer
D. Weight degeneracy: without it, a few particles soon carry almost all the weight
Weights are running products of likelihoods, so their spread grows over time. Resampling replaces the weighted set by an unweighted one concentrated where the posterior mass is, at the price of some duplicated particles.
Go deeper
- Markov Chains & Mixing · Stationary distributions, ergodicity and mixing times.
- HMM Algorithms · Forward–backward, Viterbi and Baum–Welch.
- Kalman & Particle Filters · Tracking hidden state with noisy sensors.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 14.
- L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proceedings of the IEEE 77(2), 257–286 (1989).
- R. E. Kalman, "A new approach to linear filtering and prediction problems," Journal of Basic Engineering 82(1), 35–45 (1960).
- S. Thrun, W. Burgard & D. Fox, Probabilistic Robotics (MIT Press, 2005).