Probabilistic Reasoning over Time

A Bayesian network 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.¹

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}, \dots, e_{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 $Rain_{t}$ (is it raining today?), hidden from you, and the single evidence variable is $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} ∣ 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} ∣ X_{0 : t - 1}) = P (X_{t} ∣ 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.³

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.

The state nodes read $X$ and the evidence nodes read $E$ ; the slice index $t - 2, \dots, 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} ∣ X_{t - 1})$ says how the state evolves. The sensor model (or observation model) $P (e_{t} ∣ 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} ∣ X_{0 : t}, E_{0 : t - 1}) = P (E_{t} ∣ 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 (Rain_{t} ∣ Rain_{t - 1}) : {0.7 0.3 if Rain_{t - 1} = true if Rain_{t - 1} = false P (Umbrella_{t} ∣ Rain_{t}) : {0.9 0.2 if Rain_{t} = true if Rain_{t} = false.

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}) i = 1 \prod t P (X_{i} ∣ X_{i - 1}) P (E_{i} ∣ 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.⁴

Task	Query	Reads evidence	Direction
Filtering	$P (X_{t} ∣ e_{1 : t})$	up to now	forward
Prediction	$P (X_{t + k} ∣ e_{1 : t})$ , $k > 0$	up to now, project ahead	forward
Smoothing	$P (X_{k} ∣ e_{1 : t})$ , $0 \leq k < t$	up to now, revise past	forward + backward
Most likely explanation	$ar g max_{x_{1 : t}} P (x_{1 : t} ∣ 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} ∣ e_{1 : t + 1}) = α update P (e_{t + 1} ∣ X_{t + 1}) one-step prediction P (X_{t + 1} ∣ e_{1 : t}),

where $α$ 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} ∣ e_{1 : t}) = x_{t} \sum P (X_{t + 1} ∣ x_{t}) P (x_{t} ∣ 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} ∣ e_{1 : t})$ that is propagated along the sequence, projected by each transition and reweighted by each observation:

f_{1 : t + 1} = α Forward (f_{1 : t}, e_{t + 1}), 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:

\textsc{Forward}

— recursive belief-state update (filtering)

1
input: prior $P(X_0)$ , transition model, sensor model, evidence $e_{1:t}$
2
$f \gets P(X_0)$
the initial belief state
3
for $i = 1$ to $t$ do
4
for each state $x$ do
5
$f'(x) \gets \sum_{x'} P(X_i = x \mid X_{i-1} = x')\, f(x')$
project forward
6
for each state $x$ do
7
$f'(x) \gets P(e_i \mid X_i = x)\, f'(x)$
weight by the observation
8
$f \gets \textsc{Normalize}(f')$
9
return $f$
$f = P(X_t \mid e_{1:t})$

To see it run, filter the umbrella world with a prior $P (Rain_{0}) = ⟨ 0.5, 0.5 ⟩$ , 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} ∣ r_{0}) P (r_{0}) + P (r_{1} ∣ \neg r_{0}) P (\neg r_{0}) = 0.7 (0.5) + 0.3 (0.5) = 0.5$ , and by symmetry $P (\neg r_{1}) = 0.5$ ; the flat prior predicts a flat state. Update by the umbrella-seen sensor vector $⟨ 0.9, 0.2 ⟩$ : the unnormalized belief is $⟨ 0.5 \times 0.9, 0.5 \times 0.2 ⟩ = ⟨ 0.45, 0.10 ⟩$ , which sums to $0.55$ , so

P (Rain_{1} ∣ u_{1}) = \frac{1}{0.55} ⟨ 0.45, 0.10 ⟩ = ⟨ 0.818, 0.182 ⟩ .

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 (\neg r_{2}) = 0.3 (0.818) + 0.7 (0.182) = 0.373$ , so the prediction is $⟨ 0.627, 0.373 ⟩$ — the transition alone has pulled the belief a little back toward $0.5$ because the chain forgets. Update: $⟨ 0.627 \times 0.9, 0.373 \times 0.2 ⟩ = ⟨ 0.5645, 0.0746 ⟩$ , summing to $0.6391$ , giving

P (Rain_{2} ∣ u_{1}, u_{2}) = \frac{1}{0.6391} ⟨ 0.5645, 0.0746 ⟩ = ⟨ 0.883, 0.117 ⟩ .

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.

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

⟨ 0.9, 0.2 ⟩

, and renormalized. The filtered belief in rain rises 0.500 to 0.818 to 0.883.

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} ∣ e_{1 : t}) = x_{t + k} \sum P (X_{t + k + 1} ∣ x_{t + k}) P (x_{t + k} ∣ 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} ∣ 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} ∣ e_{1 : t}) = α P (X_{k} ∣ e_{1 : k}) P (e_{k + 1 : t} ∣ X_{k}) = α 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} ∣ X_{k})$ , computed by a recursion that runs backward from $t$ :

P (e_{k + 1 : t} ∣ X_{k}) = x_{k + 1} \sum P (e_{k + 1} ∣ x_{k + 1}) P (e_{k + 2 : t} ∣ x_{k + 1}) P (x_{k + 1} ∣ X_{k}),

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

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} ∣ e_{1 : t})

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:

\textsc{Forward-Backward}

— smoothed estimates for every slice

1
input: evidence $e_{1:t}$ , prior $P(X_0)$
2
$fv[0] \gets P(X_0)$
3
for $i = 1$ to $t$ do
4
$fv[i] \gets \textsc{Forward}(fv[i-1], e_i)$
store the forward messages
5
$b \gets \mathbf{1}$
backward message, all ones
6
for $i = t$ downto $1$ do
7
$sv[i] \gets \textsc{Normalize}(fv[i] \times b)$
combine stored forward with backward
8
$b \gets \textsc{Backward}(b, e_i)$
9
return $sv$

Applied to the umbrella world at $k = 1$ , given umbrellas on days 1 and 2, the smoothed estimate is $\approx ⟨ 0.883, 0.117 ⟩$ — higher than the filtered $⟨ 0.818, 0.182 ⟩$ . 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 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}$ :

x_{1} \dots x_{t} max P (x_{1}, \dots, x_{t}, X_{t + 1} ∣ e_{1 : t + 1}) = α P (e_{t + 1} ∣ X_{t + 1}) x_{t} max (P (X_{t + 1} ∣ x_{t}) x_{1} \dots x_{t - 1} max P (x_{1}, \dots, x_{t} ∣ e_{1 : t})) .

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.

The Viterbi trellis for the umbrella sequence. Each column holds the two states

Rain = 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.

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 $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.⁵

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

T = (0.7 0.3 0.3 0.7), O_{u = true} = (0.9 0 0 0.2), O_{u = false} = (0.1 0 0 0.8) .

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

f_{1 : t + 1} = α O_{t + 1} T^{⊤} f_{1 : t},

and the backward recursion is $b_{k + 1 : t} = T 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 (S t)$ 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.⁶

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 $μ_{t}$ and covariance $Σ_{t}$ to a new Gaussian $(μ_{t + 1}, Σ_{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.

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} ∣ z_{1})

, a sharper Gaussian whose mean sits between the prediction and

z_{1}

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, 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.

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. ↩
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. ↩
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. ↩
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). ↩
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. ↩
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. ↩