The Bayes filter

A state you cannot see, from data you cannot trust

A robot drives along a corridor. Its true position, a single number along the corridor, is a hidden state: no sensor reports it directly. What you get instead are two weak signals. The first is a control, the command you sent — go forward about a metre — whose real effect is corrupted by wheel slip and a slightly uneven floor. The second is a measurement, a range reading to a wall or a landmark, which is corrupted by sensor noise and by the fact that several positions can produce similar readings. Neither signal is good enough alone, and you want them to combine.

It is tempting to keep a point estimate: start at the believed position, add the commanded motion, then nudge toward whatever the sensor says. That is what a great many robots do, and it fails in a specific and instructive way. Adding motions accumulates error, and the error accumulates faster than any single reading can correct for. Nudge too hard toward a noisy reading and you chase noise; nudge too softly and you drift. A point estimate throws away the one thing you need to set that balance: how uncertain you are.

The Bayes filter keeps uncertainty explicitly. Instead of one number it keeps a whole probability distribution over the state, written bel(x_t), the belief at time t. It is the probability of each possible position given every control and every measurement so far. A sharp spike means you know where you are; a broad smear means you do not. The width of that distribution is not a side note, it is the quantity that decides how much the next reading should be trusted.

The corridor in this part is a loop, a ring of known length. That choice is not just scenery. On a loop there is no boundary: position x = L is the same place as position x = 0, so probability that leaves one end of the number line re-enters at the other. If the state lives on a circle, the arithmetic has to respect that, and watching it happen is the clearest way to see why the filter is a convolution. By the end you will have watched the belief locate itself, and understood why the same two lines of reasoning run every filter in this volume.

Two lines of Bayes, applied forever

Name the three objects. The state is x_t, the thing we want. The control is u_t, the action taken between the last step and this one. The measurement is z_t, the reading that arrives now. All we ever want is the belief, the posterior over the current state given the whole history of controls and measurements.

Applied naively, that posterior is a nightmare: the history grows without limit, so each new step would require re-deriving the joint distribution over every past state. The recursion escapes the nightmare with two assumptions, each of which is a modelling decision you can check against the world. First, the Markov property: the current state is a sufficient summary of the past, so once you condition on x_t, older states add nothing. Second, the measurement depends only on the current state, not on how you got there. Under those two assumptions, the whole history collapses into the previous belief.

Write bel(x_t) for the prediction, the belief before the new measurement is used, and bel(x_t) for the belief after. The filter is then exactly two equations, repeated forever: propagate the previous belief through the motion model, then correct it with the measurement model.

The symbol η is a normalising constant, chosen so the corrected belief integrates to one. It is not arbitrary: it equals one over the total probability of the measurement, the evidence, and it is the number that would tell you how surprising this reading was under your model. The first equation is the law of total probability; the second is Bayes' rule. Nothing else is going on. Every named filter in this volume is a decision about how to represent the distribution and how to compute these two integrals.

That is the punchline of the whole subject, so it is worth saying slowly. Prediction adds uncertainty and moves probability with the motion. Correction removes uncertainty and pulls probability toward the measurement. Whatever representation you choose — a list of histograms, a mean and a covariance, a cloud of particles — the loop is the same, and the belief at time t is always a complete summary of the data up to time t. The animation below is this loop run eight times on the looped corridor, with the true position drawn as a dashed tick at each step.

Watch the order of operations. Each ridge is a posterior: the prediction already happened, then the reading was folded in. The motion shifts each ridge slightly forward and blurs it; the reading sharpens it again around the true position. When the two happen in the other order the result is nearly identical, because the multiply and the convolution commute, but the standard order is predict then update because the world moves before it is measured.

Motion is a convolution, and it costs certainty

The motion model is the distribution p(x_t | u_t, x_t−1): given that you were at x_t−1 and you applied control u_t, where could you be now? The control says where you tried to go; the model adds the spread of everything that could have gone wrong. The predict equation sums this over every place you might have started, weighted by how much you believed you were there. That weighted sum is a convolution of the belief with the motion kernel.

On a discretised corridor the integral becomes a sum over cells. If cell j is centred at x_j and cell i at x_i, the motion kernel is a probability over the displacement, and the new belief is the sum over old cells of old belief times kernel.

Two effects are visible in that one line. The kernel is centred on the displacement u_t, so the belief translates: a step forward moves the whole shape forward. The kernel has width σ_u, so the belief blurs: a spread of possible displacements smears the shape outward. Translation is the signal you wanted, blur is the uncertainty you paid. Add up independent sources of motion noise and their variances add, so the belief only ever loses sharpness in this step. Nothing in the predict step can make you more certain.

The demo below applies exactly one predict to a known starting belief. Drag the shift to translate, drag the motion noise to blur, and toggle the wrap to see what the loop does. With wrap off, mass that crosses the right edge falls off the end of the corridor and is discarded; with wrap on it reappears at the left. That single toggle is the difference between a line and a circle, and it is the reason the state space in the next section is written modulo the corridor length.

One subtlety hides inside the kernel: real motion is rarely a pure translation with symmetric Gaussian noise. A differential-drive robot turning while it drives rotates the belief as well as shifting it, and the kernel becomes a rotation of the state space. For richer models the convolution is still the right mental picture, but the kernel is no longer a shift-invariant blur and the tidy sum above generalises to a matrix of transition probabilities. That matrix is a Markov chain, which is why the Markov-chains part of this volume and the hidden-Markov-model part are the same idea in different clothing.

A reading is a multiplication, and it buys certainty

The measurement model is the distribution p(z_t | x_t): how likely would this reading be if the state were here? For a range sensor it is a bell centred at the true distance with width set by the sensor noise, plus whatever outliers your model allows. Bayes' rule turns that likelihood into a posterior by multiplying it into the prediction, cell by cell, and rescaling.

The word to hold onto is pointwise. This is not another convolution; it does not move probability around at all. Each cell keeps its own argument and is simply multiplied by how well that cell explains the reading. Cells where the sensor says the state cannot be get a small factor and shrink; cells where the sensor says the state would fit nicely get a large factor and grow. Then η rescales the whole array so it sums to one, and the belief is again a probability distribution.

The effect on sharpness is the mirror image of the predict step. For a Gaussian belief and a Gaussian sensor, the posterior is Gaussian, and its precision — one over the variance — is the sum of the two precisions. Sharp likelihood times sharp belief gives an even sharper posterior; a broad, noisy likelihood barely changes the shape. That is the quantitative version of an intuition you already have: a vague sensor tells you little, and the belief should not move much for it. It also explains a failure mode. If the likelihood is broad because the sensor is noisy, the update cannot re-sharpen a belief that motion keeps blurring, and the filter settles into a wide steady state.

The demo below isolates the multiplication. The grey bars are a broad prior, the dashed curve is the sensor likelihood for one reading, and the blue bars are their pointwise product after normalisation. Move the reading and it slides the posterior toward itself; make the sensor noisier and the posterior relaxes back toward the prior. Nothing here is specific to corridors or robots. The update equation is Bayes' rule, so every Bayesian inference you have done is a one-step, one-cell update of this filter.

There is a reason this looks so much like the likelihood part of this volume. Index the cells and hold the reading fixed, and the array p(z | x_i) is exactly a likelihood as a function of the unknown state. The filter is doing maximum-likelihood-flavoured inference at every step, except that it keeps the whole distribution and lets the motion model supply the prior from the previous instant. Priors made from yesterday's data, updated by today's: that is the recursion, and it is why the same code handles a static parameter and a moving robot.

Discretise the state, then let the loop do the work

The simplest representation of a belief is a list of numbers. Cut the corridor into n cells, store a probability for each, and require the list to sum to one. This is a histogram filter, and it makes both equations concrete. Prediction becomes a discrete convolution: each cell sprays its probability across nearby cells according to the motion kernel, and the wrapped index arithmetic keeps the loop closed. Correction becomes a pointwise multiply by the likelihood evaluated at each cell centre, followed by a divide so the list sums to one again.

The cell size Δx = L/n is the one real design choice. Finer cells resolve a sharper belief and let the reading pull the shape around more precisely, but the array grows and the convolution costs more. Coarser cells are cheap but pile up position error within each cell, and a belief narrower than a cell is smeared out almost immediately. The slider below lets you change the resolution and watch that trade-off directly: too few cells and the filter cannot express how sure it is.

The corridor being a loop changes the predict step from a truncation to a wrap. In the sum above, indices are taken modulo n, so probability that would have left the right-hand end of the array reappears at the left-hand end instead of vanishing. That is exactly what a circular corridor requires: walking off the end of the corridor puts you back at the start. If you forget the wrap and use a straight line instead, the belief quietly loses probability at the edges and the filter becomes confidently wrong near the seam. The wrap arrow drawn across the top of the histogram, and the ring below it, are the same statement in two pictures.

The final ingredient is a way to say how much the filter knows, and entropy answers it. A uniform belief over n cells has entropy log₂ n bits, the maximum possible; a belief concentrated on one cell has entropy zero. Predict blurs, so it raises entropy; update multiplies, so it lowers it. Run the loop and the entropy trace falls as readings accumulate, until it levels off at the point where the information each reading brings is exactly cancelled by the uncertainty each motion adds. That plateau is the best the filter can do with this sensor and this motion, and it is the honest answer to "how well do we know where the robot is?"

Step it by hand and watch the story unfold. Press Predict a few times with the shift positive and the robot marches forward while the belief smears and slides; press Update and the reading snaps it back to a peak, occasionally to the wrong place on the loop when the sensor is noisy. Then raise the sensor noise slider and repeat: each reading now barely reshapes the belief, so the smear from the motion wins, the entropy plateau rises, and the dot and the triangle drift apart. Lower it again and the peak tightens. That single slider is the whole trade-off between trusting your model and trusting your senses, and the entropy trace is the ledger that records it.

One recursion, many filters

Every formula in one place

Where to go deeper

• Sebastian Thrun, Wolfram Burgard, Dieter Fox, Probabilistic Robotics, 2005, chapters 2–4 — the recursive Bayes filter, the histogram filter, and the looped-corridor example this part is built on.
• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, chapter 14 — the same recursion written for a computer-science audience, with the HMM as a special case.
• Dieter Fox, Wolfram Burgard, Frank Dellaert, Monte Carlo Localization: Efficient Position Estimation for Mobile Robots, 1999 — the particle-filter version of this filter, with the same predict and update steps.
• Simo Särkkä, Bayesian Filtering and Smoothing, 2013 — the continuous-state story and the Kalman, extended Kalman and sigma-point filters derived from the same two lines.
• David MacKay, Information Theory, Inference, and Learning Algorithms, chapters 23–24 — the HMM forward algorithm and the view of the filter as message passing on a chain.