Introduction

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.

Decode the Sequence

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">A hidden weather chain emits one clue per day: did your colleague carry an umbrella? You never see the weather — only the clues. Press New clues, then Run Viterbi to decode the single most likely sequence of hidden Sunny/Rainy days.</p>
<div class="row" id="clues"></div>
<div class="row" id="states"></div>
<div class="status" id="status">Roll a sequence of clues to begin.</div>
<div class="btns">
  <button id="roll" type="button">New clues</button>
  <button id="run" type="button">Run Viterbi</button>
  <button id="reset" type="button" class="ghost">Clear states</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// --- A 2-state Hidden Markov Model (weather) ---------------------------------
// Hidden states: Sun, Rain. Observation per day: umbrella (U) or no umbrella (N).
// We DECODE: given the clue sequence, find the single most likely hidden path.
// The Viterbi algorithm does this with dynamic programming in O(N * S^2),
// instead of brute-forcing all 2^N possible sun/rain sequences.
const STATES = ['Sun', 'Rain'];
const START = { Sun: 0.6, Rain: 0.4 };                 // day-1 prior
const TRANS = { Sun:  { Sun: 0.8, Rain: 0.2 },         // weather is sticky
                Rain: { Sun: 0.4, Rain: 0.6 } };
const EMIT  = { Sun:  { U: 0.1, N: 0.9 },              // umbrella rare on sun
                Rain: { U: 0.8, N: 0.2 } };            // umbrella likely on rain
const N_DAYS = 8;
const ICON = { Sun: '☀', Rain: '☂' };        // sun / umbrella glyphs

let clues = [];   // array of 'U' / 'N'
let path  = null; // decoded states, or null

// Sample a hidden path + clues honestly from the model (so clues are realistic).
function pick(dist){ let r = Math.random(); for (const k in dist){ r -= dist[k]; if (r <= 0) return k; } return Object.keys(dist).pop(); }
function roll(){
  clues = []; let s = pick(START);
  for (let t = 0; t < N_DAYS; t++){ clues.push(pick(EMIT[s])); s = pick(TRANS[s]); }
  path = null; render(); setStatus('Clues rolled. Press "Run Viterbi" to decode.');
}

// --- Viterbi: log-space dynamic programming ---------------------------------
function viterbi(obs){
  const L = (x) => Math.log(x);
  const V = [{}], back = [{}];
  for (const s of STATES) V[0][s] = L(START[s]) + L(EMIT[s][obs[0]]);
  for (let t = 1; t < obs.length; t++){
    V[t] = {}; back[t] = {};
    for (const cur of STATES){
      let best = -Infinity, arg = null;
      for (const prev of STATES){
        const score = V[t-1][prev] + L(TRANS[prev][cur]);   // best path INTO cur
        if (score > best){ best = score; arg = prev; }
      }
      V[t][cur] = best + L(EMIT[cur][obs[t]]);
      back[t][cur] = arg;
    }
  }
  // backtrack from the best final state
  let last = STATES[0];
  for (const s of STATES) if (V[obs.length-1][s] > V[obs.length-1][last]) last = s;
  const out = new Array(obs.length); out[obs.length-1] = last;
  for (let t = obs.length-1; t > 0; t--) out[t-1] = back[t][out[t]];
  return out;
}

function run(){
  if (!clues.length) return;
  path = viterbi(clues); render();
  console.log('clues :', clues.join(' '));
  console.log('decoded:', path.join(' '));
  setStatus(fmt('Decoded the most likely hidden weather — checked all %length% days at once, not 2^%length% = %v% guesses.', { length: clues.length, v: 1 << clues.length }));
}

// --- rendering --------------------------------------------------------------
function cell(cls, txt){ const d = document.createElement('div'); d.className = 'cell ' + cls; d.textContent = txt; return d; }
function render(){
  const cr = document.getElementById('clues'); cr.innerHTML = '';
  const sr = document.getElementById('states'); sr.innerHTML = '';
  clues.forEach((c, i) => {
    cr.appendChild(cell('clue', c === 'U' ? ICON.Rain : '·'));
    if (path) sr.appendChild(cell('state ' + (path[i] === 'Sun' ? 'sun' : 'rain'), path[i] === 'Sun' ? ICON.Sun : ICON.Rain));
    else sr.appendChild(cell('state', '?'));
  });
}
function setStatus(t){ document.getElementById('status').textContent = t; }

document.getElementById('roll').addEventListener('click', roll);
document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', () => { path = null; render(); setStatus('Cleared. Press "Run Viterbi" to decode the clues.'); });
roll();
Result
Console

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 2n2^{n} possible sun/rain sequences; Viterbi gets the same answer in time that grows only linearly with the number of days.

The Real Complexity

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⋅S2)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hidden-markov-models/Content licensed under CC BY-NC 4.0.