Markov Chains and Hidden Markov Models
time is just another dimension to factorise over. a bayesian network whose variables are indexed by time steps, with the same local structure copied at every step, is a dynamic bayesian network — and its two simplest members, the markov chain and the hidden markov model, carry a startling share of applied probability: language models before transformers, speech recognition, robot localisation, pagerank, and the mcmc machinery behind approximate inference. 𐃏
markov chains
a markov chain is a sequence of variables \(X_1, X_2, \dots\) over a common state space, forming the world’s simplest bayesian network — a path:
\begin{equation} P(X_1, \dots, X_n) = P(X_1) \prod_{t=2}^{n} P(X_t \mid X_{t-1}). \end{equation}
two assumptions do all the compressing. the markov assumption (first-order): the future is independent of the past given the present — each \(X_t\) has a single parent \(X_{t-1}\). the stationarity assumption: the transition model \(P(X_t \mid X_{t-1})\) is the same table at every step, the dynamics. so the whole process is two objects — an initial distribution \(P(X_1)\) and a \(|X| \times |X|\) transition matrix — instead of \(O(|X|^n)\) joint entries.
where is the chain going? the mini-forward algorithm
the state distribution rolls forward by one matrix-vector product per step — variable elimination specialised to a path:
\begin{equation} P(x_t) = \sum_{x_{t-1}} P(x_t \mid x_{t-1})\, P(x_{t-1}), \qquad O(n\,|X|^2) \text{ for } n \text{ steps}. \end{equation}
stationary distributions
for many chains the state distribution forgets its start: it converges to a stationary distribution \(\pi\), the fixed point
\begin{equation} \pi(x) = \sum_{x’} P(x \mid x’)\, \pi(x’), \qquad \sum_x \pi(x) = 1. \end{equation}
for the weather chain: \(\pi(\mathrm{sun}) = 0.9\,\pi(\mathrm{sun}) + 0.3\,\pi(\mathrm{rain})\) with normalisation gives \(\pi = (0.75, 0.25)\) — three sunny days in four, no matter how it started.
when does this work? two structural conditions:
- irreducible — every state reachable from every other (the transition diagram is strongly connected). guarantees a unique stationary distribution.
- aperiodic — the chain is not trapped in deterministic cycles (returns to a state are possible at irregular times; a single self-loop anywhere in an irreducible chain suffices).
an irreducible, aperiodic (together: ergodic) chain converges to its unique \(\pi\) from any initial distribution — though possibly slowly; mixing time is the practical worry. 𐃏
hidden markov models
usually the state itself is not observable — only noisy emissions of it. an hmm attaches an observed child \(E_t\) to each hidden \(X_t\):
the factorisation, straight off the graph:
\begin{equation} P(X_{1:n}, E_{1:n}) = P(X_1)\, P(E_1 \mid X_1) \prod_{t=2}^{n} P(X_t \mid X_{t-1})\, P(E_t \mid X_t), \end{equation}
and the d-separations that make inference cheap: \(X_t \perp X_{1:t-2}, E_{1:t-2} \mid X_{t-1}\) and \(E_t \perp \text{everything earlier} \mid X_t\). the canonical toy: a phd student in a windowless lab infers the weather (hidden) from whether the supervisor carries an umbrella (emission); the serious versions are speech recognition (phonemes from acoustics), part-of-speech tagging, and robot localisation (position from sensor readings).
filtering: the forward algorithm
filtering maintains the belief state \(B(X_t) = P(X_t \mid e_{1:t})\) online, alternating two steps:
passage of time — push the belief through the dynamics (exactly the mini-forward update):
\begin{equation} P(X_{t+1} \mid e_{1:t}) = \sum_{x_t} P(X_{t+1} \mid x_t)\, B(x_t); \end{equation}
observation — multiply in the evidence likelihood and renormalise:
\begin{equation} B(X_{t+1}) \;\propto\; P(e_{t+1} \mid X_{t+1})\, P(X_{t+1} \mid e_{1:t}). \end{equation}
this is the forward algorithm: \(O(n\,|X|^2)\) time, \(O(|X|)\) memory — variable elimination along the temporal order, with the normalisation constants multiplying up to the probability of evidence \(P(e_{1:n})\).
decoding: the viterbi algorithm
the most probable trajectory — the mpe of the chain — is not the sequence of individually most probable states. picture the state trellis: states stacked vertically, time running horizontally, edges weighted by transition \(\times\) emission probabilities. a path through the trellis is a trajectory, its weight the product along it; the forward algorithm sums path weights into each node, viterbi maximises:
\begin{align} s_t[x_t] &= P(e_t \mid x_t) \sum_{x_{t-1}} P(x_t \mid x_{t-1})\; s_{t-1}[x_{t-1}] && \text{(forward)} \\ m_t[x_t] &= P(e_t \mid x_t) \max_{x_{t-1}} P(x_t \mid x_{t-1})\; m_{t-1}[x_{t-1}] && \text{(viterbi)} \end{align}
each node also records which predecessor achieved the max; backtracking from the best final state reads the trajectory off in reverse. two numerical realities: products of many probabilities vanish below floating-point range, so implementations either renormalise every step or — cleaner — work with log probabilities, replacing multiplications with additions; and ties in the max must be broken consistently or backtracking wanders. both algorithms are \(O(n\,|X|^2)\), linear in sequence length. 𐃏
particle filtering
when the state space is huge or continuous (\(|X|^2\) unaffordable — a robot’s pose in a warehouse), replace the belief table with a population of \(N\) samples (“particles”) and push the samples through the same two-step loop:
- elapse time — move each particle by sampling its successor from the transition model;
- observe — do not sample the evidence: weight each particle by \(P(e_t \mid x)\);
- resample — draw \(N\) fresh particles proportional to weight, returning to an unweighted population (equivalent to renormalising, and concentrating particles where the evidence points).
this is sequential importance resampling — likelihood weighting made to work over time by pruning hopeless samples before their weights collapse. accuracy grows with \(N\); the failure mode is particle deprivation, all particles missing the true state.
dynamic bayesian networks and the kalman filter
nothing above needed the hidden state to be a single variable. a dynamic bayesian network copies an arbitrary “slice” network at each time step, with edges within a slice and from slice \(t-1\) to \(t\) — an hmm whose state factorises. exact filtering must in general drag around the joint over the full slice (the factorisation does not survive conditioning on evidence), so dbn inference typically falls back to the jointree algorithm per window, or to particle methods.
the continuous cousin: make the hmm’s transition and emission models linear gaussian — \(X_{t+1} = A X_t + \varepsilon\), \(E_t = H X_t + \delta\) — and the belief state stays exactly gaussian forever; propagating its mean and covariance is the kalman filter. same graph as the hmm, closed-form updates, the workhorse of tracking and control.
results
- markov chain parameters — initial distribution + shared transition matrix: \(O(|X|^2)\) numbers for arbitrarily long sequences.
- stationary distribution — an irreducible chain has a unique \(\pi\) solving \(\pi = \pi P\); adding aperiodicity, \(P(X_t) \to \pi\) from every start.
- forward algorithm — filtering in \(O(n |X|^2)\) time, \(O(|X|)\) space; normalisers accumulate \(P(e_{1:n})\).
- viterbi algorithm — mpe trajectory in \(O(n |X|^2)\) by max-product on the trellis + backtracking; run in log-space.
- forward = ve, viterbi = max-out ve — both are variable elimination along the temporal order on the hmm’s chain network.
- particle filter — sample-based filtering: propagate, weight by evidence, resample; cost \(O(nN)\), exact as \(N \to \infty\).
- kalman filter — exact filtering for linear gaussian dynamics; gaussian belief state propagated in closed form.
see also
- bayesian networks — hmms are just chain-structured ones
- exact inference — the general algorithms these specialise
- approximate inference — mcmc, built on ergodic markov chains
- recurrent neural networks — the neural sequence model on the same unrolled graph