A Markov chain you cannot see, betrayed only by the noisy symbols it emits. The world takes a hidden step; you get a shadow. From those shadows, dynamic programming recovers two exact answers: the FORWARD algorithm gives P(observations) summed over every hidden path without ever enumerating them, and VITERBI gives the single most-likely path. Data flows down the center: the observations go in, the trellis computes, the decoded story comes out. The blue team proves the DP equals brute force; the red team deletes the transitions and the witness catches it.
source Baum & Petrie, Statistical Inference for Probabilistic Functions of Finite State Markov Chains, Ann. Math. Statist. 37 (1966) 1554–1563 — projecteuclid.org; algorithm exposition after Rabiner, Proc. IEEE 77 (1989). Rendered, not quoted.
Two hidden states you never observe — SUN, RAIN — each emitting one of two visible symbols, walk or shop. Three fixed distributions:
Start π, transition A (row = from-state), emission B (row = state):
| π | SUN | RAIN |
|---|---|---|
| init | 0.6 | 0.4 |
| A → | SUN | RAIN |
|---|---|---|
| SUN | 0.7 | 0.3 |
| RAIN | 0.4 | 0.6 |
| B | walk | shop |
|---|---|---|
| SUN | 0.5 | 0.5 |
| RAIN | 0.1 | 0.9 |
FORWARD: αt(j) = [Σi αt-1(i)·Aij]·Bj(ot). VITERBI is the same with max replacing the sum, plus a back-pointer.
Take the Markov chain and pull a curtain across it: you no longer see the state, only a noisy emission of it. Inference over that curtain is dynamic programming across paths — the same trellis that powers speech recognition and gene finding.
It is the discrete cousin of the Kalman filter: both estimate a hidden state from noisy observations, one over a finite alphabet, one over the Gaussian line. Each sphere is the next one's premise.
The blue team's live check: for the current observation sequence, re-run FORWARD and VITERBI and confirm each equals a brute-force sum / argmax over all hidden paths, and that the posteriors γt sum to 1. If red deletes the transitions, this badge is where it shows.
You do not see the weather. You see a person's choices over three days — each day one visible symbol, walk or shop. That length-3 sequence is all the machine gets:
There are 23 = 8 hidden weather histories that could have produced any such sequence. The panel below folds all 8 into one pass — and the witness proves the fold is exact.
FORWARD trellis — each cell is αt(state), the total probability of every path that reaches that state having emitted the observations so far. The shaded cells are VITERBI's best path.
Change any day — both answers are recomputed from A, B and π on the spot, never looked up.
Two exact quantities, each cross-checked against enumeration of all 8 paths: P(observations) — the FORWARD sum — and the most-likely hidden path from VITERBI. Below them, the smoothed posteriors γt(state) = P(state at t | all observations), whose columns each sum to 1.
The blue team's witness (left) confirms these live; the red team (right) tries to make them wrong.
And the trellis is only tractable because the state space is tiny. FORWARD is O(T·N2); brute force is O(NT). Here N=2, T=3, so 8 paths — enumerable. Real problems (N in the thousands) make brute force impossible, which is the whole reason the DP exists — but it also means the witness can only spot-check small cases.
"The forward algorithm finds the most likely path." Cut. FORWARD sums over paths to get P(O); VITERBI maximizes to get the path. Different operators, different answers — both are in the machine.
"The Viterbi path is the sequence of individually most-likely states." Cut. That is the γ-argmax (posterior decoding); it can even be a path of probability zero. VITERBI maximizes the joint path.
"Baum–Welch finds the true parameters." Kept, corrected. EM only climbs to a local maximum of likelihood — the source paper proves convergence, not global optimality.
The red team's move: in the FORWARD recursion, ignore the transition matrix A — pretend consecutive hidden states are independent (drawn fresh from π). P(observations) then no longer equals the honest sum over paths.
Drop A and the forward pass double-counts the wrong way — the witness (window 7) recomputes the brute-force sum with the real A, the two disagree, and it turns red. Nothing is faked; the attack is real and it is caught.