The Viterbi Algorithm

When you dictate a message to your phone, your words arrive at the microphone as a stream of noisy acoustic signals. The phone doesn't hear words — it hears frequencies. Yet in milliseconds it reconstructs the most likely sentence you said. How?

The answer is the Viterbi algorithm, published by Andrew Viterbi in 1967 for decoding error-correcting codes sent over noisy radio channels. The idea is deceptively simple: the world has hidden states (the words you spoke, the genes in a genome, the market regime a stock is in), and you only see noisy observations (acoustic features, DNA bases, closing prices). The two are linked by a probabilistic model called a Hidden Markov Model (HMM).

The brute-force approach — try every possible sequence of hidden states and pick the most likely one — takes time exponential in the length of the sequence. With 10 possible states and a sequence of 100 steps, that is $10^{100}$ candidates. Hopeless.

Viterbi's insight was that the problem has optimal substructure: the most likely path to any state at step t depends only on the most likely path to each state at step t − 1, not on the full history. That single observation turns the exponential blowup into an $O(T N^{2})$ dynamic programming sweep — where T is the sequence length and N is the number of hidden states. The result is the unique maximum-probability path, found exactly in polynomial time.

This is not an approximation. It is a provably optimal, efficient algorithm — one of the cleanest victories of dynamic programming in all of computer science.

Below is a two-state Hidden Markov Model: the hidden states are Sunny and Rainy. Each day the weather transitions between states with fixed probabilities, and an observer only sees whether the person carried an Umbrella or not.

Click Randomize to generate a new observation sequence, then Run Viterbi to watch the algorithm fill its trellis column by column and trace back the most likely hidden weather sequence.

<div class="hmm-desc">
  <strong>{{hmm_title}}</strong> {{hmm_desc}}
</div>
<div class="controls">
  <button id="btn-random" type="button">{{btn_randomize}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="obs-row" id="obs-row"></div>
<div id="trellis-wrap">
  <canvas id="trellis" width="560" height="200"></canvas>
</div>
<div class="result" id="result"></div>
<div class="prob-info" id="prob-info"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hmm-desc { font-size: .85rem; color: #555; margin-bottom: .6rem; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.obs-row { display: flex; gap: 6px; margin-bottom: .6rem; flex-wrap: wrap; align-items: center; }
.obs-label { font-size: .75rem; color: #777; margin-right: 4px; }
.obs-chip { padding: .25rem .55rem; border-radius: 6px; font-size: .85rem; font-weight: 600;
            border: 1.5px solid transparent; }
.obs-chip.umbrella { background: #dbeafe; border-color: #3b82f6; color: #1d4ed8; }
.obs-chip.no-umbrella { background: #fef9c3; border-color: #ca8a04; color: #78350f; }
#trellis-wrap { overflow-x: auto; }
#trellis { display: block; max-width: 100%; }
.result { margin-top: .6rem; font-size: .95rem; font-weight: 600; min-height: 1.3em; }
.result.ready { color: #0a7d33; }
.result.wait { color: #777; }
.prob-info { font-size: .8rem; color: #555; margin-top: .25rem; font-family: ui-monospace, monospace; min-height: 1.2em; }

// Code not found

Notice how the algorithm never backtracks or searches blindly. At each step it keeps only N partial-path scores — one per state — and extends them forward. The traceback at the end recovers the full optimal path in a single backward pass. This is the power of dynamic programming: throwing away all but the best incoming path at each node.

The Viterbi algorithm is a solved problem — it finds the maximum-a-posteriori (MAP) state sequence of an HMM in provably optimal time:

• Time: $O(T N^{2})$. For each of the T observation steps, and for each of the N destination states, the algorithm examines all N possible predecessor states and picks the best. That is T × N × N multiplications and comparisons.
• Space: $O(T N)$. A table of size T × N stores the best score reaching each state at each step, plus a backpointer table of the same size for traceback.
• Exact and optimal. The algorithm produces the single highest-probability state sequence — not a sample, not an approximation. This follows directly from the principle of optimality: if the overall best path passes through state s at time t, then its prefix up to t must itself be the best path to state s at time t.
• Lower-bound matching. Any algorithm that reads all T observations must spend at least Ω(T N) time. The $O(T N^{2})$ bound is tight for the general N-state case; it improves to $O(T N)$ with special structure (e.g., linear-chain or tree-structured transitions).

Contrast this with two related tasks that are harder:

• Computing the observation probability (summing over all paths, not maximizing) requires the Forward algorithm, also $O(T N^{2})$, but numerically it sums exponentially many small numbers — practitioners use the log-sum-exp trick or scaled arithmetic to stay numerically stable.
• Learning HMM parameters from unlabeled data requires the Baum-Welch / EM algorithm, which iterates forward-backward passes until convergence. Convergence to a global optimum is not guaranteed.

So Viterbi sits in a comfortable position: the decoding problem it solves is in P, and the algorithm achieves the best possible complexity for that problem.

The pattern "hidden states observed through noise" appears across science and engineering, and the Viterbi algorithm is the standard tool wherever it does:

• Speech recognition: phonemes are hidden states; acoustic frames are observations. Every major speech engine — from 1970s DARPA systems to today's phone assistants — built its core decoder on Viterbi. Modern neural approaches still use a Viterbi-like beam search at the output layer.
• DNA and gene annotation: in computational biology, CpG islands, exon/intron boundaries, and protein-coding regions are hidden states; the raw base sequence is observed. Tools like GENSCAN and Augustus use HMMs decoded by Viterbi to annotate genomes.
• Error-correcting codes: Viterbi's original application was decoding convolutional codes sent over noisy channels (used in deep-space probes, 3G/4G modems, and Wi-Fi). The algorithm finds the most likely transmitted codeword from the corrupted received signal.
• GPS and navigation: Kalman filtering is the continuous analogue; for discrete-state position tracking — map-matching a GPS trace to a road network — Viterbi decoding finds the most likely sequence of road segments.
• Finance and economics: regime-switching models treat "bull" and "bear" market states as hidden; Viterbi recovers the most likely state sequence from observed returns.
• Natural language processing: part-of-speech tagging (noun, verb, adjective…) over a sentence is a classic HMM decoding problem solved by Viterbi in $O(T N^{2})$ where N is the tagset size.

Whenever you see a problem that can be phrased as "given these noisy observations, what is the most likely sequence of hidden causes?", Viterbi is almost certainly the right tool — and it will give you the exact answer in linear time in the sequence length.

The Viterbi algorithm is one of those rare ideas that lands in exactly the right spot: it solves a genuinely hard-looking problem — finding the best hidden path through exponentially many candidates — in polynomial time, exactly, by recognizing that the problem has perfect optimal substructure.

Published in 1967 to decode signals from noisy radio channels, it went on to power speech recognition, decode the human genome, correct errors in your Wi-Fi connection, and match your GPS position to a road. The core insight never changed: keep only the best score arriving at each state, extend forward, trace back.

That is dynamic programming at its most satisfying — not an approximation, not a heuristic, but the provably optimal answer delivered in time that grows gracefully with the size of the problem.