Hidden Markov Models, drawn out

Taras Trishchuk · November 2026 · Infographic | Українська

You see the ice creams someone ate; you want the weather. A hidden Markov model (HMM) is the smallest honest model of that situation: a chain of hidden states that you cannot see, each of which emits something you can. This poster walks the whole story from the Markov chain to training, using one tiny example so that every number can be checked by hand.

Everything on the poster is computed by the same code that powers the calculator below it, not copied from a figure. The example and the three-problem framing follow Appendix A of Jurafsky & Martin; the commentary and the practice notes are mine.

trishchuk.com / learn

Infographic

Hidden Markov Models

Recover a hidden sequence (weather, part-of-speech tags, phonemes) from what you can actually observe. One model, three problems, three dynamic-programming algorithms.

Ice creams eaten each day (the scoops) and the weather Viterbi infers from them (the lit path). Amber is hot, blue is cold.

Markov assumption

P(q_i | q₁ … q_i−1) = P(q_i | q_i−1)

The next state depends only on the current one, not on the history.

Output independence

P(o_i | q₁ … q_T, o₁ … o_T) = P(o_i | q_i)

An observation depends only on the hidden state that emitted it.

Markov chain: states you can see

Weather chain, Fig. A.1a of the book

Transition matrix A

from ↓ / to →	HOT	COLD	WARM
HOT	.6	.1	.3
COLD	.1	.8	.1
WARM	.3	.1	.6

Every row sums to 1. Start distribution: π = [.1, .7, .2].

Same chain, two sequences

hot hot hot hot .0216
cold hot cold hot .0007

hot-hot-hot-hot is about 31× more likely than cold-hot-cold-hot: weather is sticky, and the heavy diagonal of A encodes exactly that.

Where does it settle? πA = π

after 0 steps 10 70 20
after 1 steps 19 59 22
after 2 steps 24 51 25
after 3 steps 27 46 27
after 5 steps 30 39 30
after 10 steps 33 34 33

Start from π and apply A again and again. A is symmetric, so its columns also sum to 1 and the uniform distribution is stationary: in the long run every state gets ⅓. A stationary distribution satisfies πA = π.

Hidden Markov model: add a layer you can’t see

The Eisner ice-cream task, Fig. A.2

Hidden: whether a day was cold (C) or hot (H). Observed: how many ice creams (1, 2 or 3) Jason ate. Given the diary, infer the weather.

Transitions A

	C	H
C	.5	.5
H	.4	.6

Emissions B

	1	2	3
C	.5	.4	.1
H	.2	.4	.4

Start π

	C	H
π	.2	.8

Q: N hidden states (here C, H)
A: transition matrix, rows sum to 1
B: emission probabilities, P(o | state)
π: initial state distribution
O: T observations, one per step

One model, three problems

Problem 1

Likelihood

How probable is this diary under the model?

P(O | λ)

Forward algorithm

O(N²T), one pass

Problem 2

max

Decoding

Which weather sequence best explains it?

best Q

Viterbi algorithm

O(N²T) time, O(NT) memory

Problem 3

E → M

Learning

Which A and B make the diary most likely?

A, B

Forward-Backward (Baum–Welch)

O(N²T) per iteration

Forward: sum over all paths without listing them

Observations 3 1 3 (Jason ate 3, then 1, then 3 ice creams)

α_t(j) = NΣi=1 α_t−1(i) · a_ij · b_j(o_t)

Each cell αₜ(j) is the probability of seeing the first t observations and being in state j. It is built from the previous column: multiply by a transition, add the incoming paths, multiply by the emission.

Start: α₁(j) = π_j · b_j(o₁) End: P(O | λ) = Σ α_T(i)

Forward values α_t(j)
	t=1 o=3	t=2 o=1	t=3 o=3
H	.32	.0404	.0235
C	.02	.069	.005066

Total likelihood P(O | λ) = .028562 Matches the brute-force sum below.

Why not just enumerate?

All 2³ = 8 hidden paths for 3 1 3, with joint probability P(O, Q)

HCH .0128
HHH .009216
HCC .0032
HHC .001536
CCH .001
CHH .00048
CCC .00025
CHC .00008

Their sum is the likelihood Σ = .028562

10²⁰ paths to enumerate N^T

2 000 forward steps N²·T

N = 10 states, T = 20 steps

Here N = 2, T = 3: 8 paths vs 12 steps. The gap is invisible at this size and astronomical at real sizes.

Viterbi: same trellis, max instead of sum

Keep only the best way into each cell, and remember where it came from

v_t(j) = max_i v_t−1(i) · a_ij · b_j(o_t)

bt_t(j) = argmax_i v_t−1(i) · a_ij · b_j(o_t)

Replace the sum by a max and store a backpointer for every cell. At the end, pick the best last cell and follow the pointers back.

Viterbi values v_t(j)
	t=1 o=3	t=2 o=1	t=3 o=3
H	.32	.0384←H	.0128←C
C	.02	.064←H	.0032←C

Best path HCH p = .0128 Runner-up: H H H = .009216

Intuition says “3 ice creams ⇒ hot, so H H H”. But on day 2 Jason ate just one, which is far likelier on a cold day (.5 vs .2), and the chain is not sticky enough to outweigh that. The best path dips to cold: H C H.

Learning: Forward-Backward (Baum–Welch)

No labels? Guess A and B, soft-count what the guess implies, re-estimate, repeat

Backward probability: what happens after t

β_t(i) = NΣj=1 a_ij · b_j(o_t+1) · β_t+1(j)

γ: how likely was state j on day t?

γ_t(j) = α_t(j) β_t(j) / P(O | λ)

ξ: how likely was the move i → j at t?

ξ_t(i, j) = α_t(i) a_ij b_j(o_t+1) β_t+1(j) / P(O | λ)

M-step: re-estimate

â_ij = Σt ξ_t(i, j) / ΣtΣk ξ_t(i, k)

b̂_j(v_k) = Σt: o_t=v_k γ_t(j) / Σt γ_t(j)

E-step compute γ and ξ from the current A, B (needs α and β)
M-step recompute A and B from the expected counts
↻ repeat until the likelihood stops improving

Posterior state probabilities for 3 1 3 γ_t(j)
	t=1 o=3	t=2 o=1	t=3 o=3
H	.937	.396	.823
C	.0634	.604	.177

Example: ξ₁(H→C) = .5602 · β₃ = [1, 1], β₂ = [.25, .28]

With labelled data none of this is needed: count transitions and emissions and divide (maximum likelihood), exactly as for a Markov chain.

Key properties

First-order: one step of memory. Longer memory means a bigger state space.
Generative: it models P(O, Q). Discriminative cousins (CRFs) model P(Q | O) directly.
Geometric durations: staying d steps in state i has probability aᵢᵢ^(d−1) · (1 − aᵢᵢ).
Viterbi ≠ posterior: the best joint path is not the same as picking argmax γ at each step.

Applications

Part-of-speech tagging: tags are hidden, words are observed.
Speech recognition: sub-phone states, acoustic frames as observations.
Bioinformatics: gene finding, profile HMMs; the cousin of sequence alignment.
Communications: Viterbi (1967) decoded convolutional codes first.
Also: GPS map matching, activity recognition, regime switching in finance.

In practice

Underflow: products of many probabilities vanish. Use log probabilities for Viterbi; use log-sum-exp or per-step scaling for Forward.
Local optima: EM never decreases the likelihood but can stall. Initialise sensibly, restart randomly, zero out impossible transitions.
Zero counts: an unseen emission gets probability 0 and kills a path. Smooth B.
Pick N honestly: more states always fit better. Validate on held-out data.

↓ Download the poster as PNG

Try it

Type ice-cream counts (1, 2 or 3 per day, up to 30 days) and watch the same Forward and Viterbi code from the poster run on your sequence.

Observations

Forward α_t(j)
	day 1 o = 3	day 2 o = 1	day 3 o = 3
H	.32	.0404	.0235
C	.02	.069	.005066

Viterbi v_t(j)
	day 1 o = 3	day 2 o = 1	day 3 o = 3
H	.32	.0384	.0128
C	.02	.064	.0032

Likelihood P(O | λ): .028562
Best hidden path: HCH
its probability: .0128

Model: the Eisner HMM above. Very small values are shown as ×10⁻ⁿ.

Sources and further reading

Jurafsky & Martin, Speech and Language Processing (3rd ed. draft), Appendix A: Hidden Markov Models. Source of the weather chain, the ice-cream HMM and the three-problem framing.
L. R. Rabiner (1989), A tutorial on hidden Markov models and selected applications in speech recognition, Proc. IEEE 77(2). The classic tutorial.
J. Eisner (2002), An interactive spreadsheet for teaching the forward-backward algorithm. Origin of the ice-cream task.
A. J. Viterbi (1967), Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. L. E. Baum et al. (1966–72) for the forward-backward algorithm.