Hidden Markov Models

Imagine you cannot see the weather outside, only whether your office-mate walks in with an umbrella. The umbrella is a noisy clue: people forget umbrellas on rainy days and carry them on sunny ones. From a week of umbrella-or-not observations, can you reconstruct the most likely sequence of sunny and rainy days?

That is exactly the setup of a hidden Markov model (HMM). There is a hidden chain of states that evolves step by step — today's weather depends only on yesterday's. You never observe the states directly; you only see emissions, each a noisy signal of the hidden state behind it.

The central question is decoding: given the clues, what is the single most likely path through the hidden states? Naively there are exponentially many paths to consider. The beautiful surprise is that a clever algorithm finds the best one fast.

Below is a tiny weather HMM. Two hidden states — Sunny and Rainy — and one clue per day: did your colleague carry an umbrella? Roll a random sequence of clues, then run the Viterbi decoder and watch it fill in the most likely hidden weather behind them.

<p class="hint">{{hint}}</p>
<div class="row" id="clues"></div>
<div class="row" id="states"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="roll" type="button">{{btn_roll}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; gap: 4px; flex-wrap: wrap; margin: .3rem 0; }
.cell { width: 46px; height: 46px; display: flex; align-items: center; justify-content: center;
        font: 700 20px system-ui, sans-serif; border-radius: 8px; user-select: none; }
.clue { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.state { border: 1px solid #cdd9e3; background: #f6f8fa; color: #aab2bd; font-size: 22px; }
.state.sun { background: #ffe9b0; border-color: #f0c850; color: #8a6a00; }
.state.rain { background: #c7d9ef; border-color: #8fb0dc; color: #1d3557; }
.status { font-size: .98rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what the decoder does. It does not judge each day in isolation — an umbrella on one day might still be best explained as a sunny day if the days around it scream "sunny." Viterbi weighs the whole path at once, balancing how likely each clue is against how likely the weather is to change from one day to the next. Brute force would test every one of the $2^{n}$ possible sun/rain sequences; Viterbi gets the same answer in time that grows only linearly with the number of days.

How hard is it to find the best hidden path?

• Brute force lists every possible state sequence. With S states and N steps there are Sᴺ of them — for two states and 50 days that is already over a quadrillion paths. Hopeless.
• The Viterbi algorithm sidesteps the explosion with dynamic programming. Going left to right, it keeps, for each state at each step, only the single best path that ends there together with its probability. The Markov property — the future depends only on the present state — guarantees this is enough.
• It runs in $O(N \cdot S^{2})$ time. For each of the N steps it considers every pair of states once. That is polynomial, even linear in the length of the sequence. This problem is fully solved: Andrew Viterbi published the algorithm in 1967, and nothing faster in the worst case is needed.
• Why it works. Any best path that passes through a given state at a given step must use a best path to reach that state — so the optimal sub-solutions compose into the optimal whole. That is the same principle behind shortest paths and edit distance.

So unlike the NP-complete puzzles elsewhere on KipuHub, HMM decoding is a happy story: a question that looks exponential collapses to a quick scan. It is a textbook example of how the right recursion turns an intractable search into an easy one — the optimistic mirror image of P vs NP.

"Recover a clean hidden sequence from noisy observations" describes an astonishing range of real problems, and the HMM is its workhorse:

• Speech recognition: the hidden states are the words or phonemes you meant; the observations are the noisy sound waves. Viterbi finds the most likely sentence.
• Bioinformatics: gene-finders and protein-family models treat DNA or amino acids as emissions of hidden biological states (gene vs. non-gene, helix vs. coil).
• Natural language: part-of-speech taggers decode the hidden grammatical role of each word, much like pattern matching over a sequence.
• Communications: Viterbi's algorithm decodes convolutional error-correcting codes — it is literally running in the chips that keep your phone call and Wi-Fi intact.

Under the hood every one of these is the same trick: a probabilistic model of how states evolve and emit clues, plus dynamic programming to read the story back. It is also a close cousin of Bayesian inference, reasoning from evidence back to the most probable cause.

Hidden Markov models capture a deep idea: the world hides its true state and leaks only noisy clues, yet a disciplined model can still reconstruct the most likely story behind them. The number of candidate stories is astronomical, but the Viterbi algorithm finds the best one in time that grows only linearly with the data.

That is the quiet triumph here. Where so many problems explode into intractability, decoding a hidden Markov model is solved — efficient, exact, and running invisibly every time your phone understands a word or your genome is read. Sometimes the hidden story is hard to live; it is not hard to compute. For the flip side, see P vs NP.