Hidden Markov Models: Seeing Through Noise

The Problem: You Can't See the Weather, Only the Umbrella

Your cousin lives in Ooty, up in the Nilgiri hills, where the weather flips between bright sun and sudden rain in the space of an hour. You are in Chennai and cannot see the sky above her house. Every evening she sends you exactly one bit of information: whether she carried an umbrella that day. She never says "it rained" or "it was sunny" — you only get the umbrella report.

Can you figure out, from a week of umbrella reports alone, what the actual weather in Ooty probably was on each of those days? This sounds like a guessing game, but it is a completely solvable problem once you set it up correctly, and the machinery you build to solve it — the Hidden Markov Model, or HMM — is the same machinery that lets a phone transcribe your voice from noisy audio, lets a keyboard guess the grammatical role of a word it has never seen before, and lets a spacecraft's navigation computer infer its true position from noisy sensor readings. The pattern in all these problems is identical: a sequence of true states you cannot observe directly, and a sequence of noisy clues you can. This chapter builds that machinery from first principles, all the way down to arithmetic you can check by hand.

Refresher: The Markov Property and Transition Matrices

Before adding "hidden," you need to be precise about "Markov." Say the weather each day is one of two states: Sunny (S) or Rainy (R). A sequence of daily weather values X₁, X₂, X₃, ... is called a Markov chain if the weather tomorrow depends on the weather today, but given today, it does not depend on any day before that:

P(X_t = x | X_t-1, X_t-2, ..., X₁) = P(X_t = x | X_t-1)

This is called the Markov property: the present screens off the past. It does not mean the weather is memoryless in an absolute sense — today's weather still strongly influences tomorrow's — it means all of the useful memory is captured in the single most recent state. You do not need last Tuesday's weather to predict tomorrow if you already know today's.

The rule "given today, what is the chance of each possible tomorrow" is captured in a transition matrix A, where A(i, j) = P(tomorrow = j | today = i). If it is Sunny today, suppose there is a 0.7 chance tomorrow is also Sunny and a 0.3 chance it turns Rainy (hill weather is fairly persistent within a day or two). If it is Rainy today, suppose there is a 0.4 chance it clears to Sunny and a 0.6 chance it stays Rainy. Every row of A must sum to 1, because "tomorrow" must land on some state. This part of the story — states you can directly observe evolving under a transition matrix — is an ordinary Markov chain, the kind you may already have met as a stochastic process with a transition-probability matrix. The interesting twist starts now.

Adding Noise: What Makes a Markov Chain "Hidden"

In the ordinary Markov chain above, you were told the weather directly. In the umbrella problem, you are never told the weather — you only see whether an umbrella was carried, and that clue is noisy: an umbrella can appear on a Sunny day (she is cautious) and can be missing on a Rainy day (she got caught out). The true weather sequence is a Markov chain evolving underneath, invisible to you. What you actually observe is a second sequence, generated stochastically from the hidden one. That is precisely what "hidden" means in Hidden Markov Model: there is a Markov chain, but you do not get to watch it — you only get to watch a noisy shadow it casts.

Historically, the Markov property itself was introduced by the Russian mathematician Andrey Markov, who in 1913 used it to analyse the sequence of vowels and consonants in Pushkin's poem Eugene Onegin — one of the earliest applications of probability to a non-numeric sequence. The "hidden" layer on top was added decades later by Leonard Baum and collaborators in the late 1960s, originally to model signal sequences, and it is their algorithms — the ones you are about to derive by hand — that made the model practically usable.

The Three Ingredients of an HMM

A Hidden Markov Model is completely specified by three pieces, together written as λ = (π, A, B):

• Initial distribution π: the probability of each hidden state on day 1, before any evidence arrives. Say π(Sunny) = 0.6, π(Rainy) = 0.4 (Ooty in this season leans dry).
• Transition matrix A: the hidden-state-to-hidden-state rule from the previous section. A(S,S)=0.7, A(S,R)=0.3, A(R,S)=0.4, A(R,R)=0.6.
• Emission matrix B: the new ingredient. B(i, o) = P(observe o | true hidden state is i). This is the "noise model" — how the hidden state leaks into what you actually see. Say B(S, Umbrella)=0.1, B(S, No-Umbrella)=0.9 (on a Sunny day she rarely bothers), and B(R, Umbrella)=0.8, B(R, No-Umbrella)=0.2 (on a Rainy day she usually remembers, but not always).

Crucially, B also carries a Markov-like independence assumption: given the hidden state on a particular day, the observation on that day does not depend on any other day's hidden state or observation. All of the day-to-day dependence lives in A; all of the state-to-clue noise lives in B. This is what keeps the model tractable — without this assumption, the number of dependencies you would need to track would explode with the length of the sequence.

Now suppose your cousin's reports for three consecutive days are: Umbrella, Umbrella, No Umbrella. Two questions become worth asking. First: given this model, how likely was this exact three-day report sequence, overall? Second, and more interesting: what was the single most probable underlying weather story that produced it? These are the two classic problems solved by HMMs, and each has an efficient algorithm.

Question 1 — Evaluation: How Likely Was This Sequence At All?

You might think to compute P(observations) by listing every possible 3-day weather sequence (there are 2³ = 8 of them: SSS, SSR, SRS, ..., RRR), computing the joint probability of each specific weather-and-umbrella story using the multiplication rule P(A ∩ B) = P(A)·P(B|A), and adding all 8 up. That works, but it is wasteful: many of those 8 calculations repeat the same sub-products. The forward algorithm avoids the repetition using dynamic programming, exactly the same idea you may already know from counting paths or computing Fibonacci numbers efficiently: solve small overlapping subproblems once, cache the answer, and build up.

Define the forward variable α_t(j) = P(observations up to day t, AND hidden state on day t is j). This single quantity already bakes in a sum over every way the hidden chain could have reached state j by day t. It obeys a clean recursion:

α₁(j) = π(j) · B(j, o₁)

α_t(j) = [ Σ_i α_t-1(i) · A(i, j) ] · B(j, o_t)   for t > 1

Read the recursion in words: to have been in state j at time t and to have produced the seen observations, you must have been in some state i the day before (with probability α_t-1(i), which already contains all the history), transitioned from i to j (probability A(i,j)), and then emitted the observed clue o_t from state j (probability B(j, o_t)). You sum over all possible yesterday-states i because any of them could have led here. Finally, P(observations) = Σ_j α_T(j), summing over the possible final hidden states.

Let's trace it by hand for the sequence Umbrella (U), Umbrella (U), No-Umbrella (N):

Day 1 (o₁=U): α₁(S) = 0.6 × 0.1 = 0.06. α₁(R) = 0.4 × 0.8 = 0.32.

Day 2 (o₂=U): α₂(S) = (0.06×0.7 + 0.32×0.4) × 0.1 = (0.042+0.128)×0.1 = 0.017. α₂(R) = (0.06×0.3 + 0.32×0.6) × 0.8 = (0.018+0.192)×0.8 = 0.168.

Day 3 (o₃=N): α₃(S) = (0.017×0.7 + 0.168×0.4) × 0.9 = (0.0119+0.0672)×0.9 = 0.07119. α₃(R) = (0.017×0.3 + 0.168×0.6) × 0.2 = (0.0051+0.1008)×0.2 = 0.02118.

Result: P(U,U,N) = α₃(S) + α₃(R) = 0.07119 + 0.02118 = 0.09237. There was roughly a 9.2% chance, under this model, of seeing exactly this three-day umbrella pattern. Every number above came from four multiplications and one addition per state per day — no brute-force listing of 8 sequences was needed, though you can check (as a genuine exercise, not a hand-wave) that summing the 8 individual sequence probabilities gives the identical 0.09237, because the forward algorithm is just a reorganised, non-repeating way of computing that same sum.

Question 2 — Decoding: What Really Happened Behind the Scenes?

Evaluation told you how likely the whole sequence was, summed over every hidden path. Decoding asks a sharper question: which single hidden path was most responsible? This needs the Viterbi algorithm, structurally identical to the forward algorithm except sum becomes max, and you additionally keep a "breadcrumb" recording which previous state won at each step, so you can walk the winning path back afterward.

Define δ_t(j) = the probability of the single best hidden-state path ending in state j at time t, jointly with the observations seen so far:

δ₁(j) = π(j) · B(j, o₁)

δ_t(j) = [ max_i ( δ_t-1(i) · A(i, j) ) ] · B(j, o_t),   with backpointer ψ_t(j) = argmax_i ( δ_t-1(i) · A(i, j) )

Tracing the same three-day sequence:

Day 1: δ₁(S)=0.06, δ₁(R)=0.32 (identical to α on day 1, since there is nothing yet to maximise over).

Day 2: δ₂(S) = max(0.06×0.7, 0.32×0.4) × 0.1 = max(0.042, 0.128)×0.1 = 0.0128, winner: Rainy→Sunny, so ψ₂(S)=R. δ₂(R) = max(0.06×0.3, 0.32×0.6)×0.8 = max(0.018,0.192)×0.8 = 0.1536, winner: Rainy→Rainy, so ψ₂(R)=R.

Day 3: δ₃(S) = max(0.0128×0.7, 0.1536×0.4)×0.9 = max(0.00896, 0.06144)×0.9 = 0.055296, winner: Rainy→Sunny, so ψ₃(S)=R. δ₃(R) = max(0.0128×0.3, 0.1536×0.6)×0.2 = max(0.00384,0.09216)×0.2 = 0.018432, winner: Rainy→Rainy, so ψ₃(R)=R.

Backtrack: the largest final value is δ₃(S)=0.055296, so Day 3 = Sunny. Its backpointer ψ₃(S)=Rainy, so Day 2 = Rainy. Day 2's backpointer ψ₂(R)=Rainy, so Day 1 = Rainy. The single most probable weather story is Rainy, Rainy, Sunny, with joint probability 0.055296.

This matches intuition nicely: two umbrella days in a row is best explained by two rainy days, and the sudden dry day probably really was sunny — but notice the algorithm derived that conclusion from the transition and emission numbers alone, with no appeal to intuition. The following code implements exactly the two hand traces above, verifying them:

states = ['Sunny', 'Rainy']
pi = {'Sunny': 0.6, 'Rainy': 0.4}
A = {'Sunny': {'Sunny': 0.7, 'Rainy': 0.3},
     'Rainy': {'Sunny': 0.4, 'Rainy': 0.6}}
B = {'Sunny': {'U': 0.1, 'N': 0.9},
     'Rainy': {'U': 0.8, 'N': 0.2}}
obs = ['U', 'U', 'N']

def forward(obs):
    alpha = [{s: pi[s] * B[s][obs[0]] for s in states}]
    for t in range(1, len(obs)):
        row = {}
        for s in states:
            row[s] = sum(alpha[t-1][p] * A[p][s] for p in states) * B[s][obs[t]]
        alpha.append(row)
    return alpha

def viterbi(obs):
    delta = [{s: pi[s] * B[s][obs[0]] for s in states}]
    psi = [{}]
    for t in range(1, len(obs)):
        drow, prow = {}, {}
        for s in states:
            best_prev = max(states, key=lambda p: delta[t-1][p] * A[p][s])
            drow[s] = delta[t-1][best_prev] * A[best_prev][s] * B[s][obs[t]]
            prow[s] = best_prev
        delta.append(drow); psi.append(prow)
    last = max(delta[-1], key=delta[-1].get)
    path = [last]
    for t in range(len(obs) - 1, 0, -1):
        path.append(psi[t][path[-1]])
    path.reverse()
    return path, delta

alpha = forward(obs)
print(round(sum(alpha[-1].values()), 5))   # -> 0.09237
path, delta = viterbi(obs)
print(path)                                # -> ['Rainy', 'Rainy', 'Sunny']

Running this trace mentally: forward(obs) reproduces α₁, α₂, α₃ exactly as computed above, and sum(alpha[-1].values()) adds 0.07119 + 0.02118 = 0.09237. In viterbi(obs), the max(states, key=...) call at t=1 for s='Sunny' compares delta[0]['Sunny']*A['Sunny']['Sunny']=0.042 against delta[0]['Rainy']*A['Rainy']['Sunny']=0.128, picks 'Rainy', giving drow['Sunny'] = 0.128 × 0.1 = 0.0128 — matching δ₂(S) above, and so on through to the final backtracked path ['Rainy','Rainy','Sunny'].

Why Not Just Check Every Possibility?

With only 2 hidden states and 3 days, brute force (list all 2³=8 sequences, score each) is barely more work than the algorithm. The payoff of forward/Viterbi shows up at scale. With N hidden states and a sequence of length T, brute force must examine N^T paths — a speech recognizer with even a modest N=50 acoustic states over T=100 time frames would face 50¹⁰⁰ paths, a number with no physical meaning (more than the atoms in the observable universe, many times over). The forward and Viterbi algorithms instead do O(N²T) work: at each of T time steps, for each of N states, you compare N incoming transitions. For N=50, T=100 that is 50×50×100 = 250,000 basic operations — a number any laptop finishes instantly. This is the same dynamic-programming trade-off (exponential brute force collapsed to polynomial time by caching overlapping subproblems) that shows up in classic DP algorithms like computing binomial coefficients or the longest common subsequence — only here the "subproblem value" being cached is a probability, not a count.

The Misconception: "Best State Each Day" Is Not the Same as "Best Story Overall"

A very natural but wrong instinct is: "why not just pick whichever state is individually most likely at each time step, one day at a time, and string those together?" This section proves, with a small self-contained example, that this shortcut can give an answer with drastically lower joint probability than the true Viterbi path — because it throws away exactly the transition information that couples the days together.

Take an abstract two-state system with states P and Q, and two possible observed signals, Strong and Weak (deliberately unlabeled with any real-world meaning, to isolate the logic). Let π(P)=π(Q)=0.5. Let the states be "sticky": A(P,P)=0.9, A(P,Q)=0.1, A(Q,P)=0.1, A(Q,Q)=0.9. Let the emissions be: P(Strong|P)=0.4, P(Weak|P)=0.6, P(Strong|Q)=0.6, P(Weak|Q)=0.4. Suppose you observe, over two steps, Strong then Weak.

The naive, day-by-day approach looks only at which state best explains each single observation in isolation: for Strong, P(Strong|Q)=0.6 beats P(Strong|P)=0.4, so it picks Q. For Weak, P(Weak|P)=0.6 beats P(Weak|Q)=0.4, so it picks P. Naive story: Q, then P. Its actual joint probability is π(Q)·P(Strong|Q)·A(Q,P)·P(Weak|P) = 0.5×0.6×0.1×0.6 = 0.018.

Now run true Viterbi. δ₁(P)=0.5×0.4=0.20, δ₁(Q)=0.5×0.6=0.30. δ₂(P) = max(0.20×0.9, 0.30×0.1)×0.6 = max(0.18,0.03)×0.6 = 0.108 (path P,P). δ₂(Q) = max(0.20×0.1, 0.30×0.9)×0.4 = max(0.02,0.27)×0.4 = 0.108 (path Q,Q). Both tied at 0.108 — and both are roughly six times more probable than the naive story's 0.018. The reason: the emission evidence only mildly prefers switching states (0.6 vs 0.4), but the transition matrix strongly penalises switching at all (only a 0.1 chance of leaving a state versus 0.9 of staying). Ignoring the transition term, as the naive per-day rule does, throws away exactly the piece of the model that dominates the answer here. Viterbi never makes this mistake because its recursion multiplies the transition term in at every single step, before comparing.

A useful boundary case sharpens this further: if the transition matrix were uninformative — A(i,j) the same constant for every i and every j — then that constant factors out of every max_i comparison in the Viterbi recursion, and δ_t(j) becomes proportional to B(j,o_t) alone. In that special case, and only that case, the naive per-day rule and true Viterbi decoding agree exactly. The misconception survives specifically because real transition matrices are almost never uninformative — states usually have some memory, which is the entire reason to model them as a chain in the first place.

The Third Question: Learning the Model Itself

Evaluation assumed you already knew π, A, and B. Decoding assumed the same. But where do those numbers come from in a real system? If you have a large log of observation sequences but no one ever recorded the true hidden states, you need to learn π, A, B from data alone. This is the third classic HMM problem, solved by the Baum-Welch algorithm, a specific instance of the general Expectation-Maximization (EM) strategy. It alternates two steps: (1) using the current π, A, B estimates, compute the expected number of times each transition and each emission would have occurred, using forward probabilities together with a mirror-image "backward" pass; (2) re-estimate π, A, B as the ratios implied by those expected counts. Each round is guaranteed to not decrease the overall likelihood of the observed data, so the algorithm climbs steadily uphill, though (like most EM procedures) it can settle in a local rather than global optimum depending on where it starts. A full derivation of the backward pass and the re-estimation formulas is beyond this chapter, but knowing what problem Baum-Welch solves, and that it rests on the same forward-style recursion you have just derived by hand, is enough to recognise it wherever it appears next.

Where This Shows Up

Speech recognition systems historically modelled each phoneme as a hidden state and each short slice of audio as a noisy observation, using Viterbi to decode the most likely phoneme sequence from a waveform. Part-of-speech tagging in natural language processing treats grammatical categories (noun, verb, adjective) as hidden states and the words themselves as observations, since the same word can be more than one part of speech and only context (the transition structure) disambiguates it. Bioinformatics uses HMMs to find gene-coding regions hidden inside raw DNA sequences. And the continuous-valued cousin of this exact idea, the Kalman filter, is the standard tool for tracking a satellite's or aircraft's true position from a stream of noisy sensor readings, precisely because "true state hidden, noisy observation visible, want the best estimate" is the same problem restated with real-valued positions instead of discrete weather.

On the exam side: CBSE's core Class 12 Mathematics probability chapter (conditional probability and Bayes' theorem) is exactly the tool this whole chapter has been applying twice per day, at every α and δ update — if you are comfortable with P(A∩B)=P(A)P(B|A), you already have the one idea the forward and Viterbi recursions repeat. Students on the CBSE Applied Mathematics elective will meet transition-probability matrices formally as "Markov chains," which is exactly the A matrix of this chapter, minus the hidden layer. HMMs themselves sit outside the JEE and BITSAT syllabi, but the recursive, DP-style reasoning used here — build the answer for step t purely from step t-1's cached results — is precisely the kind of problem-solving JEE Advanced probability questions reward, and KVPY/Olympiad-style problems frequently hide a DP-over-probability structure exactly like this one inside a combinatorics dressing. For GATE-foundation study, this chapter is a direct on-ramp: the forward/Viterbi pattern is the textbook example of dynamic programming taught in GATE CS's algorithms section, and probabilistic sequence models of this kind appear in the newer GATE Data Science & AI paper's coverage of probabilistic reasoning.

Check Your Understanding

Work these using the umbrella model (π, A, B as defined above) before checking the answers underneath.

1. Your cousin sends a fourth report: Umbrella again (sequence becomes U,U,N,U). Using the forward recursion, compute α₄(Sunny) and α₄(Rainy), and hence P(U,U,N,U).
2. Without recomputing from scratch, explain why P(U,U,N,U) must come out smaller than P(U,U,N) = 0.09237.
3. Extend the Viterbi trace to day 4 and find the new most probable 4-day weather story.
4. P(U,U,N,U) turns out to be a small number, smaller than any single day's emission probability. Does that mean the model is a bad fit? What is this number actually useful for comparing?
5. Suppose Ooty's weather became far less persistent, so that A(S,S)=A(S,R)=A(R,S)=A(R,R)=0.5. Would the naive "best state per day" shortcut from the misconception section now agree with true Viterbi decoding on this model? Justify using the recursion, not intuition.

Answers: (1) α₄(S) = (0.07119×0.7 + 0.02118×0.4)×0.1 = 0.0058305; α₄(R) = (0.07119×0.3 + 0.02118×0.6)×0.8 = 0.027252; P(U,U,N,U) = 0.0330825. (2) Extending the sequence adds one more multiplicative emission/transition factor, each ≤1, to every surviving path, so the total probability mass, spread across a strictly longer and more specific event, cannot increase. (3) δ₄(S)=max(0.055296×0.7, 0.018432×0.4)×0.1=0.00387072 (from Sunny); δ₄(R)=max(0.055296×0.3,0.018432×0.6)×0.8=0.01327104 (from Sunny); the day-4 winner is Rainy (0.01327104>0.00387072) with backpointer Sunny, so the new best path is Rainy, Rainy, Sunny, Rainy. (4) It is not a defect — P(observations) is a joint probability over one specific sequence out of many possible ones, so it is expected to be small; its real use is comparative, e.g. computing this same quantity under two rival models (or two candidate parameter settings) and preferring whichever gives the observed data higher likelihood. (5) Yes, they would agree: with every A(i,j) equal to the same constant 0.5, that constant factors out of the max_i(δ_t-1(i)·A(i,j)) comparison identically for every j, leaving δ_t(j) directly proportional to B(j,o_t) — exactly the naive per-day rule.

Summary

A Hidden Markov Model separates a system into two coupled layers: a Markov chain of true states you cannot see, governed by a transition matrix A and a starting distribution π, and a sequence of noisy observations you can see, governed by an emission matrix B that depends only on the current hidden state. Three questions define the model's use: evaluation (how likely is this observation sequence overall, solved by the forward algorithm's α_t(j) = [Σ_iα_t-1(i)A(i,j)]B(j,o_t) recursion), decoding (what is the single most probable hidden path, solved by Viterbi's identical recursion with max replacing sum, plus backpointers), and learning (how to estimate π, A, B from unlabelled data, solved by Baum-Welch/EM). Both forward and Viterbi replace an exponential N^T brute-force search with an O(N²T) dynamic program by caching one number per state per time step. The single most important trap to avoid is conflating the individually-best state at each time step with the jointly-best path over the whole sequence — they coincide only in the degenerate case where the transition matrix carries no information at all; whenever the hidden states have real memory, ignoring transitions the way the naive shortcut does can understate the true best path's probability by a large factor, as the P/Q example showed directly.

Think About It

Think about this: How would you explain hidden markov models: seeing through noise to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.