Viterbi Algorithm: Full Worked Example

Setup: COVID HMM from 2022 Q9

Training data (timesteps 1–7): hidden states L, M, H, H, H, M, M; observations +, ++, ++, +++, ++, ++, +.

Estimated parameters — Transition matrix $A$ (MLE, no smoothing):

$q_{t-1}$ / $q_t$	L	M	H
L	0	1	0
M	0	2/3	1/3
H	0	1/3	2/3

Emission matrix $B$ (MLE, no smoothing):

$q_t$ / $o_t$	+	++	+++
L	1	0	0
M	0	1	0
H	0	2/3	1/3

Task

Timesteps 8–10, observations: +++, ++, ++. Unknown state sequence. Start from t=7 in state M. Find the most likely hidden-state path.

Initialisation at $t = 7$

We are in state M at t=7. Set:

$\delta_L(7) = 0 \qquad \delta_M(7) = 1 \qquad \delta_H(7) = 0$

$t = 8$: Observation = +++

State	Computation	$\delta$	$\psi$
L	$b_L(\text{+++}) = 0 \Rightarrow \delta_L(8) = 0$	0	—
M	$b_M(\text{+++}) = 0 \Rightarrow \delta_M(8) = 0$	0	—
H	$\max[\delta_M(7) \cdot a_{M \to H} \cdot b_H(\text{+++}),\; \delta_H(7) \cdot a_{H \to H} \cdot b_H(\text{+++})]$	$\frac{1}{9}$	M

$\delta_H(8) = 1 \cdot \frac{1}{3} \cdot \frac{1}{3} = \frac{1}{9}$

Best at $t = 8$: H with $\delta = \frac{1}{9}$, came from M.

$t = 9$: Observation = ++

State	Computation	$\delta$	$\psi$
L	No viable path leads to L	0	—
H	$\delta_H(8) \cdot a_{H \to H} \cdot b_H(\text{++})$	$\frac{4}{81}$	H
M	$\delta_H(8) \cdot a_{H \to M} \cdot b_M(\text{++})$	$\frac{3}{81}$	H

$\delta_H(9) = \frac{1}{9} \cdot \frac{2}{3} \cdot \frac{2}{3} = \frac{4}{81}$ $\delta_M(9) = \frac{1}{9} \cdot \frac{1}{3} \cdot 1 = \frac{1}{27} = \frac{3}{81}$

Best at $t = 9$: H with $\delta = \frac{4}{81}$, came from H.

$t = 10$: Observation = ++

State	Computation	$\delta$	$\psi$
H	$\delta_H(9) \cdot a_{H \to H} \cdot b_H(\text{++})$	$\frac{16}{729}$	H
M	$\delta_H(9) \cdot a_{H \to M} \cdot b_M(\text{++})$	$\frac{12}{729}$	H
L	No viable path leads to L	0	—

$\delta_H(10) = \frac{4}{81} \cdot \frac{2}{3} \cdot \frac{2}{3} = \frac{16}{729}$ $\delta_M(10) = \frac{4}{81} \cdot \frac{1}{3} \cdot 1 = \frac{4}{243} = \frac{12}{729}$

Best at $t = 10$: H with $\delta = \frac{16}{729}$, came from H.

Backtracking

Start from $q_{10}^* = H$ and follow backpointers:

$q_{10}^* = H \quad \Rightarrow \quad \psi_H(10) = H \quad \Rightarrow \quad q_9^* = H$ $\psi_H(9) = H \quad \Rightarrow \quad q_8^* = H$ $\psi_H(8) = M \quad \Rightarrow \quad q_7^* = M$

Optimal state sequence (t=7–10): $[M, H, H, H]$. For t=8,9,10: H, H, H.

Trellis Table (Exam Layout)

State	$t=7$ (M)	$t=8$ (+++)	$t=9$ (++)	$t=10$ (++)
L	0	0	0	0
M	1	0	3/81 ←H	12/729 ←H
H	0	1/9 ←M	4/81 ←H	16/729 ←H

Bold = max per column. Arrows show backpointers. Trace backwards from t=10: H → H → H → M.

Key Observations

• Zero emissions ($b_L(\text{+++}) = 0$, $b_M(\text{+++}) = 0$) permanently kill those paths at t=8. Without smoothing, dead paths never recover.
• The transition $a_{M \to H} = 1/3$ at t=8 gets the path to H, which then becomes the only viable route forward.
• $b_H(\text{++}) = 2/3$ gives H an edge over M at t=9 and t=10 despite $b_M(\text{++}) = 1$, because H’s accumulated delta is higher at t=8.
• The optimal path probability is $\frac{16}{729}$, which is very small — typical for Viterbi with many multiplications. In practice, use log-space to avoid underflow.

Summary

Timestep	Observation	Best State	$\delta_j(t)$	Source
8	+++	H	$1/9$	M
9	++	H	$4/81$	H
10	++	H	$16/729$	H

Past paper questions: y2022p3q9