Deriving the Viterbi Recursion

From a Path Probability to a Recursion

For a long observed sequence, the number of possible hidden-state paths grows exponentially with the sequence length. The Viterbi method avoids listing every path: it retains, for each possible current state, only the best-scoring path that ends there. The justification is that all continuations from that state use the same transition and emission factors, so a worse prefix ending there can never become preferable later.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and consider a finite-state hidden Markov model with state space $S=\{1,\ldots,K\}$ and times $t=1,\ldots,T$. The hidden states are $X_t$; the observations are $Y_t$. The initial state distribution is the row vector $\mu$, the transition matrix is $P=(p_{ij})$, and $g_j(y)=\mathbb{P}(Y_t=y\mid X_t=j)$ is the emission probability for observation $y$ in state $j$. We assume the usual HMM factorization: conditional on the hidden states, observations are independent, and the next hidden state depends on the past only through the current state. For a fixed observed sequence $y_{1:T}=(y_1,\ldots,y_T)$, the joint probability of a hidden path $x_{1:T}$ and the observations is

\mathbb{P}(X_{1:T}=x_{1:T},Y_{1:T}=y_{1:T}) =\mu_{x_1}g_{x_1}(y_1)\prod_{t=2}^{T}p_{x_{t-1}x_t}g_{x_t}(y_t).

Every row of $P$ is a probability distribution, and for each state $j$, $g_j$ is a probability distribution over possible observations. If $\mathbb{P}(Y_{1:T}=y_{1:T})>0$, maximizing the joint probability over paths also maximizes the posterior probability of a path given the observations: the posterior divides each joint probability by the same positive number. If the observation sequence has probability zero, that conditional posterior is undefined; the recursion still computes joint scores, but it does not produce a conditional MAP path.

Definition: For $t=1,\ldots,T$ and $j\in S$, the Viterbi score $\delta_t(j)$ is the largest joint probability of the observations $y_{1:t}$ and any hidden prefix $x_{1:t}$ whose last state is $j$. For $t\ge2$, a predecessor pointer $\psi_t(j)$ is a state attaining the maximum that determines $\delta_t(j)$, when the maximum is positive. Ties may be resolved by any fixed rule. The terminal state is a state attaining $\max_{j\in S}\delta_T(j)$.

This score is a maximum over complete prefixes, not a sum over them. To see the recurrence, fix the ending state $j$ at time $t$. Any path ending there must have had some state $i$ at time $t-1$. Its prefix score is at most $\delta_{t-1}(i)$; the transition to $j$ contributes $p_{ij}$, and the current observation contributes $g_j(y_t)$. Maximizing over the possible previous states gives the update. The initial score has no preceding transition, so it is just the initial-state probability multiplied by the first emission probability.

Theorem (Viterbi recursion): For a fixed observation sequence, initialize $$ \delta_1(j)=\mu_jg_j(y_1),\qquad j\in S. $$ For $t=2,\ldots,T$, compute $$ \delta_t(j)=g_j(y_t)\max_{i\in S}\{\delta_{t-1}(i)p_{ij}\},\qquad \psi_t(j)\in\operatorname*{arg\,max}_{i\in S}\{\delta_{t-1}(i)p_{ij}\}. $$ A terminal state is any $x_T^*\in\operatorname*{arg\,max}_{j\in S}\delta_T(j)$. If the maximum terminal score is positive, these choices determine a path of maximum joint probability; if the observation sequence has positive probability, it is a MAP hidden path conditional on those observations.

Proof. We prove the score formula by induction on $t$. At $t=1$, the only prefix ending in $j$ is the one-state path $(j)$, whose joint probability with $y_1$ is $\mu_jg_j(y_1)$. Thus the initialization equals the largest such prefix probability. Now suppose the formula for $\delta_{t-1}(i)$ holds for every $i$. Any prefix ending in $j$ at time $t$ has some penultimate state $i$, and its joint probability is its prefix probability through time $t-1$, multiplied by $p_{ij}g_j(y_t)$. For fixed $i$, this factor is nonnegative and does not depend on the earlier states. Therefore the largest probability among prefixes with penultimate state $i$ is $\delta_{t-1}(i)p_{ij}g_j(y_t)$. Taking the maximum over all $i$ gives exactly the stated recurrence. This proves the score formula at time $t$, including when some factors are zero. At the final time, every complete path has one terminal state $j$, and $\delta_T(j)$ is the best path probability among paths ending at $j$. Maximizing over $j$ therefore maximizes over all complete paths. When that maximum is positive, each maximizing predecessor used by the recursion can be followed to a prefix attaining its score, so the resulting path attains the terminal maximum. Finally, for positive observation probability, the posterior path probability is its joint probability divided by the fixed positive marginal probability of the observations, so the same path maximizes both. $\square$

Scores, Pointers, and Termination

The pointer stores which previous state achieved the maximum for the current state. If several previous states tie, choosing any one of them preserves an optimal path; storing all tied predecessors instead records all optimal paths. If the maximum is zero, the score still has a well-defined value, but no positive-probability prefix ends through that maximizing choice. A pointer for such a zero score is not evidence of a possible path. In implementations, one can mark it as unavailable unless a separate convention is useful for bookkeeping.

After the last observation, choose a state with the largest score. The maximum score is the joint probability of the observations together with a most probable hidden path. To recover that path, the terminal state at time $T$ is followed backward using the stored pointers at times $T,T-1,\ldots,2$. The recursion itself establishes that these pointers lead to a path attaining the maximum; detailed path reconstruction is a separate computational step.

Worked Example: A Three-Observation Sequence

Take $S=\{1,2\}$, initial distribution $\mu=(\tfrac12,\tfrac12)$, and transition matrix $P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac13&\tfrac23\end{bmatrix}$. Its row sums are $\tfrac34+\tfrac14=1$ and $\tfrac13+\tfrac23=1$. For each state, the emission probabilities of symbols $A,B$ are $(\tfrac34,\tfrac14)$ in state 1 and $(\tfrac14,\tfrac34)$ in state 2; each emission row sums to $1$. Use observations $A,B,B$.

At time 1, the two scores are $\delta_1(1)=\tfrac12\cdot\tfrac34=\tfrac38$ and $\delta_1(2)=\tfrac12\cdot\tfrac14=\tfrac18$. At time 2, the observation is $B$. For state 1, the two predecessor products are $\tfrac38\cdot\tfrac34=\tfrac9{32}$ and $\tfrac18\cdot\tfrac13=\tfrac1{24}$; the first is larger because $\tfrac9{32}=\tfrac{27}{96}>\tfrac4{96}=\tfrac1{24}$. Thus $\delta_2(1)=\tfrac14\cdot\tfrac9{32}=\tfrac9{128}$, with pointer $\psi_2(1)=1$. For state 2, the products are $\tfrac38\cdot\tfrac14=\tfrac3{32}$ and $\tfrac18\cdot\tfrac23=\tfrac1{12}$. Since $\tfrac3{32}=\tfrac9{96}>\tfrac8{96}=\tfrac1{12}$, $\delta_2(2)=\tfrac34\cdot\tfrac3{32}=\tfrac9{128}$, with pointer $\psi_2(2)=1$.

At time 3, for state 1 the predecessor products are $\tfrac9{128}\cdot\tfrac34=\tfrac{27}{512}$ and $\tfrac9{128}\cdot\tfrac13=\tfrac3{128}=\tfrac{12}{512}$. Hence $\delta_3(1)=\tfrac14\cdot\tfrac{27}{512}=\tfrac{27}{2048}$, and its pointer is 1. For state 2 the products are $\tfrac9{128}\cdot\tfrac14=\tfrac9{512}$ and $\tfrac9{128}\cdot\tfrac23=\tfrac3{64}=\tfrac{24}{512}$. Hence $\delta_3(2)=\tfrac34\cdot\tfrac3{64}=\tfrac9{256}$, and its pointer is 2. Since $\tfrac9{256}=\tfrac{72}{2048}>\tfrac{27}{2048}$, the terminal state is 2. Following the pointers gives the path $(1,2,2)$.

Check: The joint probability for this path is $\tfrac12\cdot\tfrac34\cdot\tfrac14\cdot\tfrac34\cdot\tfrac23\cdot\tfrac34$. Multiplying in order gives $\tfrac38$, then $\tfrac3{32}$, then $\tfrac9{128}$, then $\tfrac3{64}$, and finally $\tfrac9{256}$, exactly the terminal score.

Worked Example: Tied Paths and a Fixed Rule

Let $S=\{1,2\}$, $\mu=(\tfrac12,\tfrac12)$, and $P=\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac12&\tfrac12\end{bmatrix}$. Each transition row sums to $\tfrac12+\tfrac12=1$. Suppose the observation alphabet is $\{a,b\}$, and both states emit $a$ and $b$ with probabilities $\tfrac12,\tfrac12$; each emission row sums to $1$. For observations $a,a$, initialize $\delta_1(1)=\delta_1(2)=\tfrac12\cdot\tfrac12=\tfrac14$.

For either ending state at time 2, the predecessor products are $\tfrac14\cdot\tfrac12=\tfrac18$ and $\tfrac14\cdot\tfrac12=\tfrac18$. Multiplying their maximum by the current emission probability gives $\delta_2(1)=\delta_2(2)=\tfrac12\cdot\tfrac18=\tfrac1{16}$. Adopt the fixed rule “choose the smallest state index in a tie.” Then both pointers at time 2 are 1, and the terminal state is 1. Following the selected pointer gives path $(1,1)$.

Check: Every two-state path has joint probability $\tfrac12\cdot\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac1{16}$: initial probability, first emission, transition, and second emission. Thus all four paths tie, and the chosen path has the terminal score. The pointer rule selects one optimizer; it does not imply that the optimizer is unique.

Worked Example: A Forbidden Transition

Let $S=\{1,2\}$, $\mu=(1,0)$, and $P=\begin{bmatrix}1&0\\\tfrac12&\tfrac12\end{bmatrix}$. The rows sum to $1+0=1$ and $\tfrac12+\tfrac12=1$. Let the observation alphabet be $\{x,y\}$, with state 1 emitting $x,y$ with probabilities $\tfrac12,\tfrac12$, and state 2 emitting them with probabilities $0,1$. Both emission rows sum to 1. Use observations $x,y$.

At time 1, $\delta_1(1)=1\cdot\tfrac12=\tfrac12$ and $\delta_1(2)=0\cdot0=0$. At time 2, ending in state 1 gives the predecessor products $\tfrac12\cdot1=\tfrac12$ and $0\cdot\tfrac12=0$. Since state 1 emits $y$ with probability $\tfrac12$, $\delta_2(1)=\tfrac12\cdot\tfrac12=\tfrac14$, with pointer 1. Ending in state 2 gives products $\tfrac12\cdot0=0$ and $0\cdot\tfrac12=0$; the maximum is zero, so $\delta_2(2)=1\cdot0=0$. There is no positive-probability path ending in state 2. The terminal state is 1, and the path is $(1,1)$.

Check: This path has joint probability $1\cdot\tfrac12\cdot1\cdot\tfrac12=\tfrac14$, equal to the terminal score. The transition from state 1 to state 2 has probability zero, so a path using it cannot have positive joint probability.

Why the Maximum Matters

A common error is to replace the maximum over predecessor states by a sum. In the first example, for state 1 at time 2, summing the predecessor products gives $\tfrac14(\tfrac9{32}+\tfrac1{24})=\tfrac14(\tfrac{27}{96}+\tfrac4{96})=\tfrac{31}{384}$. The Viterbi score is instead $\tfrac14\max(\tfrac9{32},\tfrac1{24})=\tfrac14\cdot\tfrac9{32}=\tfrac{27}{384}=\tfrac9{128}$. The sum retains probability from all prefixes ending in state 1; the maximum retains only the best such prefix. Summing is the logic of forward likelihood calculation, not joint most-probable-path decoding.

Another useful check is to verify that every calculated score is nonnegative and no larger than the probability of the observation prefix. A score is the joint probability of one particular prefix and those observations, whereas the prefix likelihood sums over all hidden prefixes. This bound is a check, not a substitute for the recursion. Exact fractions also make ties and zero-probability transitions visible rather than hiding them behind rounded values.

Check Your Understanding

For each question, distinguish a maximum over paths from a sum over paths, and state any assumptions needed for a conditional MAP interpretation.

Write the Viterbi initialization and one-step update for a three-state HMM using $g_j(y_t)$.
Why can a prefix that is not optimal among paths ending in state $j$ be discarded when computing future scores from $j$?
If two predecessor products tie, what may be stored in $\psi_t(j)$, and what does that imply about uniqueness of the decoded path?
What does a zero Viterbi score for a state at a time tell you? Does it always mean the observation sequence itself has probability zero?
In the tied-path example, calculate the joint probability of any one path and explain why the terminal scores match it.
Why does maximizing the joint path-observation probability give a conditional MAP path only when the observation sequence has positive probability?

What You'll Learn