---
title: Probabilistic Reasoning over Time
module: Uncertainty
moduleNumber: 4
lessonNumber: 5
order: 405
summary: >
  A world that changes needs a state variable at every point in time. The Markov
  assumption cuts the dependence on history down to the previous slice, leaving a
  transition model and a sensor model that define a temporal Bayesian network.
  Four recursive tasks fall out — filtering, prediction, smoothing, and the most
  likely explanation — each a message passed along the sequence. We ground them in
  hidden Markov models and their matrix form, sketch the Kalman filter for
  continuous state, and reach dynamic Bayesian networks with particle filtering as
  the general approximate method.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 15 — Probabilistic Reasoning over Time; §15.1 Time and Uncertainty"
  - book: AIMA
    ref: "§15.2 Inference in Temporal Models; §15.3 Hidden Markov Models"
  - book: AIMA
    ref: "§15.4 Kalman Filters; §15.5 Dynamic Bayesian Networks; §15.6 Keeping Track of Many Objects"
---

A [Bayesian network](/artificial-intelligence/uncertainty/bayesian-networks)
reasons about a world that holds still. Diagnose a broken car and you assume the
fault stays put while you probe it: each random variable takes one fixed value,
and inference infers those values from evidence that is also fixed. Most of the
worlds an agent has to act in are not like that. A diabetic patient's blood sugar
drifts with food and insulin and the hour of the day; a robot's position slides
under its wheels; a tracked aircraft keeps moving between radar sweeps. To reason
about any of them the agent must treat the state not as one value but as a
sequence of values, one per instant, and connect the instants with a model of how
the world evolves.[^intro]

This lesson builds the machinery for exactly that. The world becomes a **temporal
Bayesian network** — the same local-dependency graph, unrolled through time — and
the questions we asked of a static network (what is the state, given the evidence?)
become recursive: each answer is computed from the previous answer plus one new
observation, so the agent never re-reads its whole history.

## States and observations over time

View the world as a series of snapshots, or **time slices**, each a set of random
variables. Some are hidden, some observed. Write $X_t$ for the set of **state
variables** at time $t$ — the things we cannot see directly — and $e_t$ for the
**evidence variables** we do observe at that slice. We assume the interval between
slices is fixed, so times are just integers, and by convention evidence begins at
$t = 1$. The notation $e_{1:t}$ denotes the evidence sequence
$e_1, e_2, \ldots, e_t$.[^states]

> **Definition (Temporal model).** A specification of a probability distribution
> over an unbounded sequence of state variables $X_0, X_1, X_2, \ldots$ and
> evidence variables $E_1, E_2, \ldots$, given by a prior $P(X_0)$, a transition
> model $P(X_t \mid X_{t-1})$, and a sensor model $P(e_t \mid X_t)$.

The running example is deliberately small. You are a security guard in a windowless
bunker; the only clue to the weather is whether the director walks in each morning
carrying an umbrella. The single state variable is $\textit{Rain}_t$ (is it raining
today?), hidden from you, and the single evidence variable is $\textit{Umbrella}_t$
(did the umbrella appear?), which you observe. The umbrella does not _cause_ the
rain; the rain causes the umbrella — the arrows in the model run from state to
sensor, and inference runs against them.

### The Markov assumption

The transition model should say how the current state depends on the past:
$P(X_t \mid X_{0:t-1})$. But the conditioning set $X_{0:t-1}$ grows without bound
as $t$ increases, so we cannot store a distribution that depends on all of it. The
**Markov assumption** cuts the dependence down to a finite, fixed number of
previous slices. The simplest and most common choice is a **first-order Markov
process**, in which the current state depends only on the immediately preceding
one:

$$
P(X_t \mid X_{0:t-1}) = P(X_t \mid X_{t-1}).
$$

The state variables thus carry _all_ the information needed to
predict the next slice: the future is conditionally independent of the past given
the present. A second-order process would keep $X_{t-2}$ as well; higher orders
gain accuracy at the cost of a larger conditional table.[^markov]

> **Definition (Markov assumption).** The current state depends on only a fixed,
> finite number of previous states. In a first-order Markov process,
> $P(X_t \mid X_{0:t-1}) = P(X_t \mid X_{t-1})$, so the state at time $t-1$ renders
> $X_t$ independent of everything before it.

$$
% caption: A first-order Markov chain unrolled: each state $X_t$ depends only on
% its predecessor $X_{t-1}$, and each observation $E_t$ depends only on the
% state at the same slice. The dashed arrows continue the chain in both directions.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={draw, circle, minimum size=9mm, inner sep=0pt},
  ev/.style={draw, circle, minimum size=9mm, inner sep=0pt, thick}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\x in {1/0, 2/2.6, 3/5.2, 4/7.8, 5/10.4}
    \node[st, draw=acc, text=acc] (x\i) at (\x,1.4) {X};
  \foreach \i/\x in {1/0, 2/2.6, 3/5.2, 4/7.8, 5/10.4}
    \node[ev] (e\i) at (\x,-0.6) {E};
  \draw[->, acc, thick] (x1) -- (x2);
  \draw[->, acc, thick] (x2) -- (x3);
  \draw[->, acc, thick] (x3) -- (x4);
  \draw[->, acc, thick] (x4) -- (x5);
  \foreach \i in {1,2,3,4,5} \draw[->, thick] (x\i) -- (e\i);
  \draw[->, densely dashed, acc, thick] (-1.6,1.4) -- (x1);
  \draw[->, densely dashed, acc, thick] (x5) -- (12.0,1.4);
  \node[font=\scriptsize, text=acc, anchor=south] at (1.3,1.75) {transition};
  \node[font=\scriptsize, anchor=west] at (5.35,0.4) {sensor};
\end{tikzpicture}
$$

The state nodes read $X$ and the evidence nodes read $E$; the slice index
$t-2, \ldots, t+2$ belongs to each column and is carried in the caption rather than
crammed into the small node font.

### The transition and sensor models

Two conditional distributions finish the specification. The **transition model**
$P(X_t \mid X_{t-1})$ says how the state evolves. The **sensor model** (or
observation model) $P(e_t \mid X_t)$ says how the state produces the evidence; it
encodes a second, weaker Markov assumption, that a percept depends only on the
current state, $P(E_t \mid X_{0:t}, E_{0:t-1}) = P(E_t \mid X_t)$.

We also assume the process is **stationary** — the transition and sensor
distributions are the same at every $t$ — so a single table specifies each,
however long the sequence runs. (Stationary is not static: in a stationary
process the state still changes; it is the _law_ of change that stays fixed.) For
the umbrella world the two tables are tiny:

$$
P(\textit{Rain}_t \mid \textit{Rain}_{t-1}) : \;
\begin{cases}
0.7 & \text{if } \textit{Rain}_{t-1} = \text{true} \\
0.3 & \text{if } \textit{Rain}_{t-1} = \text{false}
\end{cases}
\qquad
P(\textit{Umbrella}_t \mid \textit{Rain}_t) : \;
\begin{cases}
0.9 & \text{if } \textit{Rain}_t = \text{true} \\
0.2 & \text{if } \textit{Rain}_t = \text{false.}
\end{cases}
$$

With a prior $P(X_0)$ added, the model defines the complete joint over every
variable, a temporal instance of the Bayes-net chain rule:

$$
P(X_{0:t}, E_{1:t}) = P(X_0) \prod_{i=1}^{t} P(X_i \mid X_{i-1})\, P(E_i \mid X_i).
$$

The three factors are the initial-state model, the transition model, and the sensor
model — the whole temporal network compressed into a prior and two stationary
tables.

## The four inference tasks

With the model reduced to a prior and two small tables, almost every temporal
question is one of four, and each
is a _recursive message_ — computed from the previous answer plus one new observation,
never from the whole history. That shape is what lets an agent
track an endless stream of evidence with fixed memory.

With the structure fixed, four questions can be asked of any temporal model,
independent of the particular transition and sensor tables.[^tasks]

| Task | Query | Reads evidence | Direction |
| --- | --- | --- | --- |
| **Filtering** | $P(X_t \mid e_{1:t})$ | up to now | forward |
| **Prediction** | $P(X_{t+k} \mid e_{1:t})$, $k > 0$ | up to now, project ahead | forward |
| **Smoothing** | $P(X_k \mid e_{1:t})$, $0 \le k < t$ | up to now, revise past | forward + backward |
| **Most likely explanation** | $\arg\max_{x_{1:t}} P(x_{1:t} \mid e_{1:t})$ | up to now | forward (Viterbi) |

**Filtering** is what a rational agent does to stay current: keep a **belief
state**, the posterior over the latest state given all evidence so far. **Prediction**
projects that belief into the future with no new evidence. **Smoothing** goes the
other way, revising an estimate of a _past_ state now that later evidence has
arrived — the extra evidence makes it a better estimate than was available at the
time. **Most likely explanation** asks not for the marginal at each slice but for
the single most probable state _sequence_ as a whole. The rest of this section
gives each its recursive formula.

### Filtering: the forward algorithm

The point of filtering is to avoid re-reading history. Given the belief state at
time $t$ we want to fold in the new evidence $e_{t+1}$ and produce the belief state
at $t+1$ directly — **recursive estimation**. Rearranging the query splits it into
a prediction and an update:

$$
P(X_{t+1} \mid e_{1:t+1})
= \alpha\, \underbrace{P(e_{t+1} \mid X_{t+1})}_{\text{update}}\,
  \underbrace{P(X_{t+1} \mid e_{1:t})}_{\text{one-step prediction}},
$$

where $\alpha$ is a normalizing constant. The update factor is read straight off
the sensor model. The prediction factor comes from conditioning on the current
state and summing it out, using the transition model:

$$
P(X_{t+1} \mid e_{1:t}) = \sum_{x_t} P(X_{t+1} \mid x_t)\, P(x_t \mid e_{1:t}).
$$

The second factor inside the sum is the previous belief state — the recursion has
closed on itself. We can think of the filtered estimate as a **forward message**
$f_{1:t} = P(X_t \mid e_{1:t})$ that is propagated along the sequence, projected by
each transition and reweighted by each observation:

$$
f_{1:t+1} = \alpha\, \textsc{Forward}(f_{1:t}, e_{t+1}), \qquad
f_{1:0} = P(X_0).
$$

Because each update touches only the previous message and the new evidence, its
time and space cost is constant, independent of $t$ — exactly the property a
memory-bounded agent needs to track an unbounded stream. Written as a procedure:

```algorithm
caption: $\textsc{Forward}$ — recursive belief-state update (filtering)
input: prior $P(X_0)$, transition model, sensor model, evidence $e_{1:t}$
$f \gets P(X_0)$ // the initial belief state
for $i = 1$ to $t$ do
  for each state $x$ do
    $f'(x) \gets \sum_{x'} P(X_i = x \mid X_{i-1} = x')\, f(x')$ // project forward
  for each state $x$ do
    $f'(x) \gets P(e_i \mid X_i = x)\, f'(x)$ // weight by the observation
  $f \gets \textsc{Normalize}(f')$
return $f$ // $f = P(X_t \mid e_{1:t})$
```

To see it run, filter the umbrella world with a prior $P(\textit{Rain}_0) =
\langle 0.5, 0.5 \rangle$, carrying every number through two days on which the
umbrella appears. Each day is a **predict** step (sum over the transition) then an
**update** step (multiply by the sensor model and renormalize).

**Day 1**, umbrella seen. Predict from $t = 0$ to $t = 1$. Rain today has
probability $P(r_1) = P(r_1 \mid r_0)\,P(r_0) + P(r_1 \mid \lnot r_0)\,P(\lnot r_0)
= 0.7(0.5) + 0.3(0.5) = 0.5$, and by symmetry $P(\lnot r_1) = 0.5$; the flat prior
predicts a flat state. Update by the umbrella-seen sensor vector $\langle 0.9, 0.2
\rangle$: the unnormalized belief is $\langle 0.5 \times 0.9,\ 0.5 \times 0.2
\rangle = \langle 0.45, 0.10 \rangle$, which sums to $0.55$, so

$$
P(\textit{Rain}_1 \mid u_1) = \frac{1}{0.55}\langle 0.45, 0.10 \rangle
= \langle 0.818, 0.182 \rangle.
$$

**Day 2**, umbrella seen again. Predict from the day-1 belief:
$P(r_2) = 0.7(0.818) + 0.3(0.182) = 0.5726 + 0.0546 = 0.627$ and $P(\lnot r_2) =
0.3(0.818) + 0.7(0.182) = 0.373$, so the prediction is $\langle 0.627, 0.373
\rangle$ — the transition alone has pulled the belief a little back toward $0.5$
because the chain forgets. Update: $\langle 0.627 \times 0.9,\ 0.373 \times 0.2
\rangle = \langle 0.5645, 0.0746 \rangle$, summing to $0.6391$, giving

$$
P(\textit{Rain}_2 \mid u_1, u_2) = \frac{1}{0.6391}\langle 0.5645, 0.0746 \rangle
= \langle 0.883, 0.117 \rangle.
$$

Belief in rain climbs from $0.818$ to $0.883$ across the two days: rain persists,
and each umbrella confirms it faster than the transition erodes the estimate. The
balance between the two steps is the whole content of filtering — the predict
step spreads probability out along the chain's tendency to forget, and the update
step pulls it back toward whatever the latest observation supports.

$$
% caption: The forward algorithm on the umbrella world, two days, both with an
% umbrella. Each row is one day: the flat prior is predicted forward (the diffusion
% toward 0.5), multiplied by the sensor vector $\langle 0.9, 0.2 \rangle$, and
% renormalized. The filtered belief in rain rises 0.500 to 0.818 to 0.883.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum width=21mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % column headers
  \node[font=\scriptsize, text=black] at (0,1.7)   {prior / day-1 belief};
  \node[font=\scriptsize, text=black] at (3.7,1.7)  {predict};
  \node[font=\scriptsize, text=black] at (7.4,1.7)  {update x (.9, .2)};
  \node[font=\scriptsize, text=black] at (10.9,1.7) {normalize};
  % day 1 row
  \node[bx] (p0) at (0,0.8)   {(.500, .500)};
  \node[bx] (pr1) at (3.7,0.8) {(.500, .500)};
  \node[bx] (up1) at (7.4,0.8) {(.450, .100)};
  \node[bx, draw=acc, text=acc] (n1) at (10.9,0.8) {(.818, .182)};
  \draw[->, thick] (p0) -- (pr1);
  \draw[->, thick] (pr1) -- (up1);
  \draw[->, acc, thick] (up1) -- (n1);
  \node[font=\scriptsize, anchor=east] at (-1.4,0.8) {day 1:};
  % day 2 row
  \node[bx] (p1) at (0,-0.9)   {(.818, .182)};
  \node[bx] (pr2) at (3.7,-0.9) {(.627, .373)};
  \node[bx] (up2) at (7.4,-0.9) {(.565, .075)};
  \node[bx, draw=acc, text=acc] (n2) at (10.9,-0.9) {(.883, .117)};
  \draw[->, thick] (p1) -- (pr2);
  \draw[->, thick] (pr2) -- (up2);
  \draw[->, acc, thick] (up2) -- (n2);
  \node[font=\scriptsize, anchor=east] at (-1.4,-0.9) {day 2:};
  % carry-down: drop into the gap between rows, run left, up into day-2 prior
  \draw[->, black, densely dashed] (n1.south) |- (12.7,-0.05) -- (-1.0,-0.05) |- (p1.west);
  \node[font=\scriptsize, text=black, anchor=south] at (5.8,0.1) {day-1 result becomes day-2 prior};
\end{tikzpicture}
$$

### Prediction

Prediction is filtering with the update step removed: no new evidence, only the
transition model iterated forward. From the state at $t+k$ we get the state at
$t+k+1$ by summing over the transition,

$$
P(X_{t+k+1} \mid e_{1:t}) = \sum_{x_{t+k}} P(X_{t+k+1} \mid x_{t+k})\, P(x_{t+k} \mid e_{1:t}).
$$

Iterating this recursion, the predicted distribution drifts toward the **stationary
distribution** of the Markov chain — the fixed point of the transition model — after
which it stops changing. The number of steps to reach it is the **mixing time**.
Prediction far beyond a small fraction of the mixing time is worthless: the future
washes out to the chain's long-run average, and the more uncertain the transition
model, the sooner that happens.

### Smoothing: the forward–backward algorithm

Smoothing computes $P(X_k \mid e_{1:t})$ for a past slice $k < t$, using _all_ the
evidence, including what arrived after $k$. Split the evidence at $k$ into the past
$e_{1:k}$ and the future $e_{k+1:t}$:

$$
P(X_k \mid e_{1:t})
= \alpha\, P(X_k \mid e_{1:k})\, P(e_{k+1:t} \mid X_k)
= \alpha\, f_{1:k} \times b_{k+1:t},
$$

where $\times$ is pointwise multiplication. The first factor is the forward message
already available from filtering. The second is a new **backward message**
$b_{k+1:t} = P(e_{k+1:t} \mid X_k)$, computed by a recursion that runs _backward_
from $t$:

$$
P(e_{k+1:t} \mid X_k)
= \sum_{x_{k+1}} P(e_{k+1} \mid x_{k+1})\, P(e_{k+2:t} \mid x_{k+1})\, P(x_{k+1} \mid X_k),
$$

that is, $b_{k+1:t} = \textsc{Backward}(b_{k+2:t}, e_{k+1})$, initialized with
$b_{t+1:t} = \mathbf{1}$ (an empty evidence sequence has probability 1). Each
backward step, like each forward step, is constant-time.

$$
% caption: Smoothing at slice $k$ multiplies the forward message $f_{1:k}$
% (filtering from 1 up to $k$) by the backward message $b_{k+1:t}$ (evidence
% from $k+1$ down to $t$); the product, normalized, is $P(X_k \mid e_{1:t})$.
\begin{tikzpicture}[>=stealth, font=\small,
  sl/.style={draw, circle, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \foreach \i/\x in {0/0, 1/2.0, k/5.4, t/9.4}
    \node[sl] (x\i) at (\x,0) {X};
  \node[font=\scriptsize, anchor=south] at (x0.north) {0};
  \node[font=\scriptsize, anchor=south] at (x1.north) {1};
  \node[font=\scriptsize, anchor=south, text=acc] at (xk.north) {k};
  \node[font=\scriptsize, anchor=south] at (xt.north) {t};
  \node[font=\scriptsize] at (3.6,0) {. . .};
  \node[font=\scriptsize] at (7.4,0) {. . .};
  \draw[->, acc, thick] (x0) -- (x1);
  \draw[->, acc, thick] (x1) -- (3.1,0);
  \draw[->, acc, thick] (4.0,0) -- (xk);
  \draw[->, red, thick] (xt) -- (7.9,0);
  \draw[->, red, thick] (6.9,0) -- (xk);
  \node[font=\scriptsize, text=acc, anchor=north] at (2.6,-0.55) {forward f};
  \node[font=\scriptsize, text=red, anchor=north] at (7.9,-0.55) {backward b};
\end{tikzpicture}
$$

Smoothing a single slice $k$ is $O(t)$. Smoothing the _whole_ sequence naively
would repeat this for every $k$, costing $O(t^2)$; the **forward–backward
algorithm** does it in $O(t)$ by dynamic programming — run filtering forward once
and record every $f_{1:k}$, then sweep the backward recursion from $t$ down to 1,
combining each stored $f_{1:k}$ with the running $b$.

```algorithm
caption: $\textsc{Forward-Backward}$ — smoothed estimates for every slice
input: evidence $e_{1:t}$, prior $P(X_0)$
$fv[0] \gets P(X_0)$
for $i = 1$ to $t$ do
  $fv[i] \gets \textsc{Forward}(fv[i-1], e_i)$ // store the forward messages
$b \gets \mathbf{1}$ // backward message, all ones
for $i = t$ downto $1$ do
  $sv[i] \gets \textsc{Normalize}(fv[i] \times b)$ // combine stored forward with backward
  $b \gets \textsc{Backward}(b, e_i)$
return $sv$
```

Applied to the umbrella world at $k=1$, given umbrellas on days 1 and 2, the
smoothed estimate is $\approx \langle 0.883, 0.117 \rangle$ — _higher_ than the
filtered $\langle 0.818, 0.182 \rangle$. The day-2 umbrella makes rain on day 2
more likely, and because rain persists, that raises the estimate of rain on day 1.
Learning the transition and sensor models from data (an
[expectation–maximization](/artificial-intelligence/learning/probabilistic-learning)
procedure) requires smoothing rather than filtering for exactly this reason:
inferring what happened needs the evidence from after it happened.

### Most likely explanation: the Viterbi algorithm

Given the umbrella sequence, we might want the single most probable weather
_sequence_ that explains it — not the most likely weather on each day separately,
which can differ. Picture every state sequence as a **path** through a graph whose
nodes are the possible states at each slice; the likelihood of a path is the
product of the transition probabilities along it and the observation probabilities
at each node. We want the most likely path.

The Markov property gives a recursion. The most likely path to a state $x_{t+1}$
consists of the most likely path to _some_ state at $t$ followed by a transition
into $x_{t+1}$:

$$
\max_{x_1 \ldots x_t} P(x_1, \ldots, x_t, X_{t+1} \mid e_{1:t+1})
= \alpha\, P(e_{t+1} \mid X_{t+1})\, \max_{x_t}\!\left( P(X_{t+1} \mid x_t)\,
  \max_{x_1 \ldots x_{t-1}} P(x_1, \ldots, x_t \mid e_{1:t}) \right).
$$

This is _identical_ to the filtering equation, with two changes: the forward
message $f_{1:t}$ is replaced by a message $m_{1:t}$ holding the probability of the
best path _reaching_ each state, and the summation over $x_t$ becomes a
**maximization** over $x_t$. The algorithm — the **Viterbi algorithm** — therefore
runs forward like filtering, computing $m_{1:t}$ at each slice; at each state it
also records which predecessor was best, and following those back-pointers from the
best final state recovers the optimal sequence.

$$
% caption: The Viterbi trellis for the umbrella sequence. Each column holds the
% two states $\textit{Rain}=\text{true/false}$; a bold arrow into a state marks
% its best predecessor, and tracing the bold arrows back from the best final
% state gives the most likely path.
\begin{tikzpicture}[>=stealth, font=\small,
  cell/.style={draw, minimum width=10mm, minimum height=6.5mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c/\x in {1/0, 2/2.4, 3/4.8, 4/7.2} {
    \node[cell] (t\c) at (\x,1.0) {true};
    \node[cell] (f\c) at (\x,-0.4) {false};
  }
  \foreach \c/\lab in {1/{Rain 1},2/{Rain 2},3/{Rain 3},4/{Rain 4}}
    \node[font=\scriptsize, anchor=south] at (t\c.north) {\lab};
  % best-path arrows (bold acc) and alternatives (thin)
  \draw[->, acc, very thick] (t1) -- (t2);
  \draw[->, black] (f1) -- (t2);
  \draw[->, acc, very thick] (t2) -- (t3);
  \draw[->, black] (f2) -- (t3);
  \draw[->, black] (t2) -- (f3);
  \draw[->, acc, very thick] (f3) -- (f4);
  \draw[->, black] (t3) -- (f4);
  \draw[->, black] (f3) -- (t4);
  \node[font=\scriptsize, anchor=north] at (3.6,-1.05) {observations: umbrella present, present, absent};
\end{tikzpicture}
$$

Like filtering, Viterbi is linear in $t$; unlike filtering, it needs $O(t)$ space
for the back-pointers. The same algorithm is the backbone of sequence labeling in
natural-language processing — part-of-speech tagging and speech recognition run
Viterbi over a hidden Markov model to recover the most likely tag or word sequence
behind a string of sounds or tokens.

## Hidden Markov models

A **hidden Markov model** (HMM) is the special case in which the state is a
_single discrete_ variable. The umbrella world is already an HMM: one state
variable $\textit{Rain}_t$ whose values are the possible states of the world. A
model with several discrete state variables still fits, by merging them into one
"megavariable" whose values are the tuples. The restriction to a single discrete
variable yields a clean **matrix** implementation of all four inference tasks.[^hmm]

> **Definition (Hidden Markov model).** A temporal model whose state is one
> discrete variable $X_t \in \{1, \ldots, S\}$. The transition model is an
> $S \times S$ matrix $\mathbf{T}$ with $\mathbf{T}_{ij} = P(X_t = j \mid
> X_{t-1} = i)$, and the sensor model at slice $t$ is a diagonal matrix
> $\mathbf{O}_t$ whose $i$-th entry is $P(e_t \mid X_t = i)$.

For the umbrella world the transition matrix and two sensor matrices (for an
umbrella seen, $u = \text{true}$, and not seen, $u = \text{false}$) are

$$
\mathbf{T} = \begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix},
\qquad
\mathbf{O}_{u=\text{true}} = \begin{pmatrix} 0.9 & 0 \\ 0 & 0.2 \end{pmatrix},
\qquad
\mathbf{O}_{u=\text{false}} = \begin{pmatrix} 0.1 & 0 \\ 0 & 0.8 \end{pmatrix}.
$$

With the messages as column vectors, filtering and smoothing become matrix–vector
products. The forward recursion is

$$
f_{1:t+1} = \alpha\, \mathbf{O}_{t+1}\, \mathbf{T}^{\!\top} f_{1:t},
$$

and the backward recursion is $b_{k+1:t} = \mathbf{T}\, \mathbf{O}_{k+1}\,
b_{k+2:t}$. Each step multiplies an $S$-element vector by an $S \times S$ matrix,
so the forward–backward algorithm runs in $O(S^2 t)$ time and $O(St)$ space. The
matrix form also exposes a constant-space variant of smoothing and a constant-time
fixed-lag smoother — the algebra of the messages carries the improvements the raw
recursions could not.

An HMM localizes a robot the same way it forecasts rain. Put the robot's grid
square in the state variable $X_t$, let the transition model spread probability to
neighboring squares, and let a noisy four-bit obstacle sensor drive the sensor
model. Filtering with Equation for $f$ produces a posterior over locations that
sharpens with each reading; even with a per-bit sensor error of $20\%$ — meaning
the full reading is wrong more than half the time — a couple of dozen observations
pin the robot down to within a square, because filtering integrates evidence over
time against the transition constraints.

## Kalman filters: continuous state

Discrete states cover a robot on a grid, but a bird flitting through foliage, a
blip wandering across a radar screen, or a planet traced from noisy angular
sightings all live in a _continuous_ state space — position and velocity, real
numbers. **Kalman filtering** is the continuous analogue of the forward algorithm,
and it stays tractable by keeping the whole thing Gaussian.[^kalman]

The trick is **linear Gaussian** models. The next state is a linear function of
the current state plus Gaussian noise, and each measurement is a linear function of
the state plus Gaussian noise. Under those assumptions the belief state, if it
starts Gaussian, _stays_ Gaussian for all time: the forward operator maps a
Gaussian with mean $\mu_t$ and covariance $\Sigma_t$ to a new Gaussian
$(\mu_{t+1}, \Sigma_{t+1})$. Filtering reduces to updating a mean and a covariance —
no representation blowup. (This is special: filtering a general continuous or
hybrid model produces a belief state whose description grows without bound.)

Each update is a **predict** step followed by an **update** step, the same
two-part structure as discrete filtering. Predict pushes the Gaussian through the
transition, shifting the mean by the motion and _inflating_ the covariance by the
transition noise. Update folds in the new measurement, pulling the mean toward the
observation and _shrinking_ the covariance.

$$
% caption: One Kalman update cycle for a 1-D random walk. The prior $P(x_0)$ is
% predicted forward to $P(x_1)$ — same mean, wider from transition noise — then
% conditioned on the observation $z_1$ to give the posterior $P(x_1 \mid z_1)$,
% a sharper Gaussian whose mean sits between the prediction and $z_1$.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (-4.4,0) -- (4.6,0) node[right, font=\scriptsize] {x};
  % prior: mean 0, moderate width (solid black)
  \draw[black, thick, domain=-4.2:4.2, samples=90, smooth] plot (\x, {2.4*exp(-(\x)*(\x)/1.4)});
  % prediction: mean 0, wider (dashed acc)
  \draw[acc, thick, densely dashed, domain=-4.2:4.2, samples=90, smooth] plot (\x, {1.7*exp(-(\x)*(\x)/2.8)});
  % posterior: mean shifted right toward z, taller/narrower (red)
  \draw[red, thick, domain=-4.2:4.2, samples=90, smooth] plot (\x, {3.0*exp(-(\x-1.5)*(\x-1.5)/0.9)});
  % observation marker
  \draw[black!70, thick] (2.5,0.08) -- (2.5,-0.08);
  \node[font=\scriptsize, anchor=north] at (2.5,-0.1) {z};
  \node[font=\scriptsize, anchor=south, text=black] at (-1.9,1.7) {prior};
  \node[font=\scriptsize, anchor=south, text=acc] at (2.7,1.1) {prediction};
  \node[font=\scriptsize, anchor=south, text=red] at (1.5,3.05) {posterior};
\end{tikzpicture}
$$

The new mean is a **weighted average** of the prediction and the observation, and
the weight — the **Kalman gain** — says how much to trust the measurement. If the
sensor is noisy the gain is small and the prediction dominates; if the process is
unpredictable the gain is large and the observation dominates. The variance update
does not depend on the observation at all, so the sequence of covariances (and
gains) can be computed offline in advance; only the mean update runs during
tracking, which is why the filter is cheap enough for real-time radar.

Kalman filtering's assumptions are strong. When the transition is _nonlinear_ the
**extended Kalman filter** linearizes it around the current mean — good enough for
smooth systems. When the true belief is genuinely non-Gaussian — a bird deciding
to dodge left _or_ right of a tree, two distinct outcomes a single Gaussian bump
cannot represent — no Kalman variant suffices, and we need a more expressive model
and, with it, a more general approximate filter.

This continues in [Reasoning over Time: Tracking and Data Association](/artificial-intelligence/uncertainty/tracking-and-data-association),
which introduces dynamic Bayesian networks and particle filtering, then tackles the
hardest case — tracking many objects when you do not know which observation came from
which.

[^intro]: **Russell & Norvig**, _AIMA_ (3rd ed.), Ch. 15 — Probabilistic Reasoning over Time: partially observable environments require a belief state maintained through a transition model and a sensor model, with probability quantifying the degree of belief in each possible world state.
[^states]: **Russell & Norvig**, _AIMA_, §15.1.1 — States and Observations: the world as time slices of hidden state variables $X_t$ and observed evidence $E_t$, with the umbrella/rain example and the $a{:}b$ interval notation.
[^markov]: **Russell & Norvig**, _AIMA_, §15.1.2 — Transition and Sensor Models: the Markov assumption and first-order Markov process (Eq. 15.1), the sensor Markov assumption (Eq. 15.2), and stationarity of the process.
[^tasks]: **Russell & Norvig**, _AIMA_, §15.2 — Inference in Temporal Models: the definitions of filtering, prediction, smoothing, and most likely explanation, and the generic recursive algorithms (Eqs. 15.4–15.11).
[^hmm]: **Russell & Norvig**, _AIMA_, §15.3 — Hidden Markov Models: the single-discrete-variable case and the matrix form of the forward and backward recursions (Eqs. 15.12–15.13), with the robot-localization example.
[^kalman]: **Russell & Norvig**, _AIMA_, §15.4 — Kalman Filters: linear Gaussian transition and sensor models, the predict/update cycle (Eqs. 15.20, 15.22), the Kalman gain, and the extended Kalman filter for nonlinear systems.