The discrete Bayes filter

October 16, 2026

The Kalman filter carries belief as a mean and a covariance. The particle filter carries it as two thousand weighted guesses. Both are approximations, and both are approximations of the same thing: the posterior over where the robot is, given everything it has done and seen. Neither post ever showed that posterior, because for the states those filters estimate it cannot be written down.

Make the state small enough and it can. A robot in a ring corridor of fifteen cells is somewhere in fifteen places, so belief is fifteen numbers summing to one, and Bayes’ rule applied to a table of fifteen numbers is a loop. Nothing below is approximated, sampled or linearised. Whatever the bars say is the answer.

The robot drives one cell per step and asks a door detector what it can see. Every door looks the same, so a reading of “door” never says which door. The information is in the pattern: which cells have doors, and therefore how many blank cells sit between them.

Belief is relative to its evidence

Pearl’s word for this is $\mathrm{BEL}$: the probability of a proposition given everything observed so far.

Fifteen numbers, non-negative, summing to one. The definition names $e$, which is the part that matters: belief is not a property of the robot but of the robot together with a pile of readings. Enlarge the pile and the belief about the same cell at the same step changes, without anything in the corridor having moved.

Switched on with no idea where it is, every cell holds $1/15$, which is $\log_2 15 = 3.91$ bits of entropy: the most a belief over fifteen cells can carry, and the exact amount of nothing.

Each step builds $\mathrm{BEL}$ out of two pieces, one from motion and one from the reading, multiplied together. Pearl calls them $\pi$ and $\lambda$.

Predict: build $\pi$

The robot is told to drive $u$ cells. It gets there, or it falls one short, or it goes one past. Those three outcomes with probabilities $(\tfrac{s}{2},\, 1-s,\, \tfrac{s}{2})$ are the motion model, and slip is $s$.

Belief after the move is belief before it, pushed through every way the robot could have arrived:

$\pi$ is Pearl’s causal support: everything the evidence above $x_k$ has to say about it. On a chain, above means earlier, so $\pi$ is $p(x_k \mid z_{1:k-1})$, belief carried forward through one step of motion and not yet told what the robot can see from where it landed.

A circular convolution, three multiplies per cell. Written as a matrix it is circulant, every row a rotation of the one above, so it is doubly stochastic: its columns sum to one as well as its rows. Hence $\pi$ can never have less entropy than the $\mathrm{BEL}$ it was built from. Drag detects a real door and imagines one to the same value and the filter runs on $\pi$ alone: belief flattens back toward $1/15$ and stays there.

Drag motion slip to zero and the kernel becomes $[0, 1, 0]$. $\pi$ is then the previous $\mathrm{BEL}$ slid one cell along the corridor, losing nothing, because the robot was told where to go and went there. It is the only setting at which motion is free.

Update: multiply $\pi$ by $\lambda$

A reading arrives, and it is evidence hanging below $x_k$ rather than above it. What such evidence contributes is $\lambda$, a likelihood rather than a distribution: it does not sum to one and is not trying to.

For a reading of “door” that is $p_\text{hit}$ at the eight cells that have one and $p_\text{false}$ at the seven that do not. Belief is the two supports multiplied cell by cell and scaled to sum to one:

Pearl’s combination rule, and also Bayes’ rule: the same statement, in the names that keep working once the graph stops being a chain.

Turn on show $\pi$ behind each bar and the two supports are drawn apart: the outline is $\pi$, the fill is $\mathrm{BEL}$, and the difference between them is everything $\lambda$ did.

How much a reading is worth is the gap between the two sensor numbers. At $0.85$ and $0.15$ a reading that tells two cells apart moves their odds by $\log_2(0.85/0.15) = 2.50$ bits. Equal, and $\lambda$ is flat, every cell is multiplied by the same thing, and $\alpha$ divides it straight back out: $\mathrm{BEL}$ comes through equal to $\pi$, which is the right answer to a sensor that cannot distinguish anything.

The default run passes 50% on the correct cell at step 8, half a lap in, and 90% at step 10. It never recognised a door. It worked out which gaps it had driven through.

Entropy does not fall every step

Read the entropy off while scrubbing through the default run and it goes

3.91  3.54  3.17  2.87  2.62  3.06  2.63  2.05  1.59  1.01  0.68  1.86 ...

Down, mostly, then up at step 5 and hard up at step 11. Those are steps where $\lambda$ disagreed with $\pi$: the filter had got confident, the reading said otherwise, and it became less confident.

The two supports carry different guarantees. Building $\pi$ can never lower the entropy, every time, because the transition matrix is doubly stochastic. Multiplying in $\lambda$ lowers it only on average, over the readings that might have arrived weighted by how likely each was. Information never hurts on average, though any single reading can.

What the normaliser says

$\alpha$ is the constant that makes $\mathrm{BEL}$ sum to one, and it is usually divided away without comment. Its reciprocal is a quantity the filter has no other way to produce. Written out,

the probability the filter would have assigned to the reading before it got it. The surprise readout is $-\log_2 \eta_k$, and over the default run it runs from 0.24 to 2.73 bits, averaging 0.77.

Multiply the $\eta_k$ together and you have $p(z_{1:K})$, the likelihood of the entire run of readings. That is the only quantity here that can compare two models rather than two cells under one model, because it does not mention $x$ at all. Score the real map against the periodic one on the same readings and the real map wins.

It is also the only warning available from inside. $\mathrm{BEL}$ is normalised by construction and so always looks confident about something. A run of small $\eta_k$ is the filter reporting that the world keeps doing things it did not expect, which is what a wrong model looks like from inside.

A map is a code

The doors are at cells 3, 4, 5, 6, 8, 10, 11 and 14. That is not a corridor someone sketched. It is the output of a four-stage shift register with taps on $x^4 + x + 1$, a maximal-length sequence, and it was chosen for one property: slide it against itself by any amount other than a whole lap and it agrees in exactly seven of fifteen cells. Never more, never fewer, at any shift.

That matters because the filter’s job is to tell rotations of the map apart. Cell 3 and cell 10 are both doors and read identically; what separates them is everything else the robot will see from them. Agreement between a rotation and the map is exactly the fraction of future readings that will fail to distinguish the two, so a map whose rotations resemble it is a map that keeps its secret. Seven of fifteen is the lowest a binary sequence of odd length can hold across every shift at once, which makes every wrong hypothesis lose ground on about half of all readings, which is as fast as one bit of sensor can be made to work.

Sixty runs on each map, forty-five steps, identical noise, counting the runs that reach 50% on the correct cell:

Turn on doors every five cells for the last row. Shifting that map by five leaves it unchanged, so cells 1, 6 and 11 are not merely hard to tell apart: they are identical under everything the robot can ever observe. The three peaks stay at exactly equal weight for every step of every lap, and the equality is exact rather than approximate, because a belief that starts invariant under a five-cell shift stays invariant under both $\pi$ and $\lambda$.

The corridor does not contain the answer, so two to three bits of doubt, step after step, is the honest report. It never drops to the $\log_2 3 = 1.59$ bits three exact peaks would carry, because each peak is a cell or two wide and motion keeps it that way. This is what the particle filter meets in a building with a symmetric floor plan, and why that post counts modes instead of reporting a mean: the mean of three equal peaks is a cell the robot is known not to be in.

Zero is for ever

Turn on filter trusts the sensor completely. The world keeps the noise the sliders describe; only the filter’s model changes, to $p_\text{hit} = 1$ and $p_\text{false} = 0$. A detector that cannot be wrong.

Forty runs of forty-five steps, the same corridor and the same detector:

Under that model a reading of “no door” sets $\lambda$ to exactly zero at every door cell. Multiplication by zero is not reversible, so no later reading can argue the cell back however much it favours it, and the first wrong reading rules out the cell the robot is standing in. When enough cells have been ruled out that nothing is left, $\eta_k$ is zero and there is no $\mathrm{BEL}$ to report: the orange line across the grid marks such a step, where the filter restarts from flat and throws away every lap it had driven.

Any $p_\text{hit}$ below 1 keeps the door open. A contradicting reading then makes a cell unlikely by a factor of $p_\text{false} / p_\text{hit}$ rather than impossible, and six readings the other way bring it back. The margin between unlikely and impossible is the whole of the robustness, and it costs nothing to leave in.

The particle filter reaches the same dead end by sampling rather than by multiplying, which is what inject is there to escape: a resampled population can only hold poses descended from poses it already had.

What this costs, and what replaces it

Fifteen cells, one dimension, one bit of sensor. The table has fifteen entries, predict is three multiplies per entry and update is one, and the whole thing runs in less time than it takes to read the sensor.

Now take the robot off the rails. A pose on a floor is $(p_x, p_y, \theta)$, and a grid fine enough to be useful, say 5 cm and 5 degrees over a twelve by seven metre building, is $240 \times 140 \times 72$ cells, which is 2.4 million. Still tractable. A quadcopter carries twelve dimensions, and ten bins per dimension is $10^{12}$ entries, which is not. Exact inference over a table is bounded by the size of the table, and the table is exponential in the dimension of the state.

Which is why the other two filters exist. The Kalman filter assumes the posterior is Gaussian and carries a mean and covariance, $O(d^2)$ numbers instead of $O(c^d)$, exact when the assumption holds and badly wrong when the belief is two places at once. The particle filter carries samples, costing no assumption about shape but needing enough of them to have one near the truth. Both answer the same question: what do you give up, now that you cannot have the table?

One direction of two

$\pi$ and $\lambda$ are messages, and on a chain this page has passed only one of them. $\pi$ travels forward, the whole table of fifteen numbers handed from each step to the next. $\eta_k$ is not that message but the scale factor it is divided by, and sum-product messages are defined only up to scale.

$\lambda$ has not travelled at all. At step 8, $x_8$ has readings 9 through 45 hanging below it in the graph and none has been looked at, so $\lambda(x_8)$ is the single factor $p(z_8 \mid x_8)$ where it should be $p(z_{8:45} \mid x_8)$. Nothing about $\mathrm{BEL}$ needs to change to fix that: $e$ grows from $z_{1:k}$ to $z_{1:45}$, $\lambda$ collects the factors it was missing, and $\alpha \lambda \pi$ is recomputed against all of it.

The last step is the one place this page already has it right. $x_{45}$ has nothing below it but its own reading, so $\lambda(x_{45})$ is complete and the final bar chart is $\mathrm{BEL}$ against the whole run. Every bar chart before it is not.

Polytrees is where $\lambda$ starts travelling, on a graph that branches rather than a chain, and where setting a variable turns out to do two opposite things depending on where it sits.

The code

Two functions over a std::vector<double>. The parts worth keeping in a port are the modular arithmetic in predict, which has to handle a negative i - u - d, and the zero-evidence branch in update.

// The motion model, as probabilities over how far the robot actually
// went when told to go u cells: one short, exactly u, or one past.
// Symmetric on purpose; an asymmetric kernel is a calibration fault, and
// a filter is the wrong place to absorb one.
struct Kernel { double shortfall, exact, overshoot; };

Kernel motionKernel(double slip) {
    return {slip / 2.0, 1.0 - slip, slip / 2.0};
}

// Pearl's pi: the causal support, p(x_k | z_1..k-1). A circular
// convolution of BEL with the motion kernel, shifted by u. The transition
// matrix this writes out is circulant, hence doubly stochastic, hence
// this step can never lower the entropy.
//
// The % in C++ takes the sign of the dividend, so a bare (i - u - d) % n
// goes negative and indexes off the front of the vector. Hence the
// + n) % n.
std::vector<double> predict(const std::vector<double>& belief, int u, double slip) {
    const int n = static_cast<int>(belief.size());
    const Kernel k = motionKernel(slip);
    const double w[3] = {k.shortfall, k.exact, k.overshoot};

    std::vector<double> out(n, 0.0);
    for (int i = 0; i < n; i++) {
        double sum = 0.0;
        for (int d = -1; d <= 1; d++) {
            const int from = ((i - u - d) % n + n) % n;
            sum += w[d + 1] * belief[from];
        }
        out[i] = sum;
    }
    return out;
}

// Pearl's lambda: the diagnostic support, p(z | cell) for every cell.
// A likelihood, not a distribution, so it does not sum to one. hit is the
// chance of reading a door while standing at one, falseAlarm the chance
// of reading one while not.
std::vector<double> likelihood(const std::vector<int>& doors, int z,
                              double hit, double falseAlarm) {
    std::vector<double> out(doors.size());
    for (std::size_t i = 0; i < doors.size(); i++) {
        const double p = doors[i] ? hit : falseAlarm;
        out[i] = z ? p : 1.0 - p;
    }
    return out;
}

struct Belief {
    std::vector<double> bel;
    double evidence;
    bool collapsed;
};

// Pearl's combination rule, BEL = alpha * lambda * pi, which here is also
// Bayes' rule. evidence is alpha^-1, returned rather than divided away.
//
// Zero evidence means the model called this reading impossible from every
// cell holding any belief at all, so there is no BEL to report. Only
// reachable at hit 1 or falseAlarm 0.
Belief update(const std::vector<double>& pi, const std::vector<double>& lambda) {
    const std::size_t n = pi.size();
    double evidence = 0.0;
    for (std::size_t i = 0; i < n; i++) evidence += pi[i] * lambda[i];

    if (!(evidence > 0.0)) {
        return {std::vector<double>(n, 1.0 / static_cast<double>(n)), 0.0, true};
    }

    std::vector<double> out(n);
    for (std::size_t i = 0; i < n; i++) out[i] = pi[i] * lambda[i] / evidence;
    return {out, evidence, false};
}

Belief step(const std::vector<double>& belief, int u, int z,
            const std::vector<int>& doors,
            double slip, double hit, double falseAlarm) {
    return update(predict(belief, u, slip), likelihood(doors, z, hit, falseAlarm));
}

// Shannon entropy in bits: 0 when the belief is certain, log2(n) when it
// is flat.
double entropy(const std::vector<double>& belief) {
    double h = 0.0;
    for (const double p : belief) {
        if (p > 0.0) h -= p * std::log2(p);
    }
    return h;
}

Explore further

• Drag the step slider slowly from 0 with $\pi$ shown. Every step the outline spreads and the fill sharpens inside it, in opposite directions, all the way down the run.
• Watch the surprise readout while scrubbing. Its large values land on the steps where entropy goes up: the same event seen from the sensor’s side rather than the belief’s.
• Click a row of the grid to jump to that step. The dark trace runs diagonally because the robot is driving; a filter that has lost it shows as a dark column the orange marker is not in.
• Turn on doors every five cells, then off again. The same filter on the same corridor either never resolves it or resolves it in eight steps, entirely on which map it was given.
• Turn on filter trusts the sensor completely and compare the bars against the same step with it off. The honest filter puts no cell at exactly zero at any point in any run; the credulous one has nine or ten of fifteen there.
• Set detects a real door to 0.55 and click new readings a few times. One bit of sensor barely better than a coin still localises in 32 of 40 runs, around step 17 rather than step 8.