Reasoning Under Uncertainty
Markov Chains & Hidden Markov Models
Chapters 2-3's Bayesian networks and Naive Bayes reasoned about a single snapshot — one set of variables, one point in time. Many real problems instead involve
Jr Codex AI Notes
Level: Intermediate–Advanced Prerequisites: Chapter 3 Time to complete: ~30 minutes
Table of Contents
- Adding Time to Probabilistic Reasoning
- The Markov Assumption
- Markov Chains
- Hidden Markov Models (HMMs)
- The Three Classic HMM Problems
- The Viterbi Algorithm
- Where HMMs Are Used
- Summary & Next Steps
1. Adding Time to Probabilistic Reasoning
Chapters 2-3's Bayesian networks and Naive Bayes reasoned about a single snapshot — one set of variables, one point in time. Many real problems instead involve a sequence unfolding over time (weather day by day, words in a sentence, a robot's positions over time) — this chapter extends probabilistic reasoning to handle exactly that.
Static Reasoning (Ch.2-3) Sequential Reasoning (this chapter)
───────────────────────────── ─────────────────────────────
"Given today's symptoms, "Given the sequence of
what's the diagnosis?" observations SO FAR, what's
the most likely sequence
ONE snapshot in time of underlying states?"
MULTIPLE time steps,
connected to each other
───────────────────────────── ─────────────────────────────
2. The Markov Assumption
The key simplifying assumption that makes sequential reasoning tractable: the future depends only on the present state, not the full history of how we got there.
The Markov Assumption
─────────────────────────────────────────
P(Xt+1 | X1, X2, ..., Xt) = P(Xt+1 | Xt)
"Given the CURRENT state, the NEXT state is independent of
everything that happened BEFORE the current state."
─────────────────────────────────────────
This Is Exactly Chapter 2's Conditional Independence, Applied to Time
─────────────────────────────────────────
Chapter 2: JohnCalls depends only on Alarm, not on Burglary
directly (screened off by Alarm)
This chapter: Tomorrow's weather depends only on TODAY'S
weather, not on last week's weather directly
(screened off by today)
─────────────────────────────────────────
Is this assumption realistic? Rarely perfectly true (weather patterns can have longer-term dependencies) — but exactly like Naive Bayes' independence assumption (Chapter 3), it's a useful simplification that trades some accuracy for enormous computational tractability, and often works well enough in practice.
3. Markov Chains
A Markov chain models a sequence of states where transitions follow the Markov assumption — defined by a transition model giving P(next_state | current_state).
# A simple weather model: today's weather predicts tomorrow's
transition_model = {
"sunny": {"sunny": 0.8, "rainy": 0.2},
"rainy": {"sunny": 0.4, "rainy": 0.6},
}
import random
def simulate_markov_chain(transition_model, initial_state, n_steps):
state = initial_state
sequence = [state]
for _ in range(n_steps):
next_states = list(transition_model[state].keys())
probabilities = list(transition_model[state].values())
state = random.choices(next_states, weights=probabilities)[0]
sequence.append(state)
return sequence
weather_sequence = simulate_markov_chain(transition_model, "sunny", 10)
print(weather_sequence) # e.g. ['sunny', 'sunny', 'sunny', 'rainy', 'rainy', ...]Markov Chain, Visualized
─────────────────────────────────────────
0.8
┌───┐
▼ │
┌───────┴───┐ 0.2 ┌────────┐
│ Sunny │──────► │ Rainy │
└───────────┘ └────┬───┘
▲ │
└─────────────────────┘
0.4
(Rainy → Rainy: 0.6, looped back on itself)
─────────────────────────────────────────
def predict_n_days_ahead(transition_model, current_distribution, n_days):
"""Predict the probability distribution over weather N days from now."""
distribution = dict(current_distribution)
for _ in range(n_days):
new_distribution = {"sunny": 0, "rainy": 0}
for state, prob in distribution.items():
for next_state, transition_prob in transition_model[state].items():
new_distribution[next_state] += prob * transition_prob
distribution = new_distribution
return distribution
today = {"sunny": 1.0, "rainy": 0.0} # we KNOW today is sunny
in_5_days = predict_n_days_ahead(transition_model, today, 5)
print(in_5_days) # probabilities converge toward a stable long-run distribution4. Hidden Markov Models (HMMs)
A Markov chain assumes you can directly observe the state (today's weather is known). A Hidden Markov Model handles the more common, trickier case: the true state is hidden, and you only observe something related to it.
Markov Chain (Ch.3) Hidden Markov Model (this section)
───────────────────────────── ─────────────────────────────
You DIRECTLY see the weather You CANNOT see the weather
directly — you only see
whether a coworker brought
an UMBRELLA (an OBSERVATION
related to, but not identical
to, the true hidden state)
───────────────────────────── ─────────────────────────────
HMM Structure
─────────────────────────────────────────
Hidden states: [Sunny] → [Sunny] → [Rainy] → [Rainy] (unobserved!)
│ │ │ │
▼ ▼ ▼ ▼
Observations: [NoUmbrella][NoUmbrella][Umbrella][Umbrella] (what we ACTUALLY see)
─────────────────────────────────────────
# An HMM needs THREE components:
transition_model = { # P(next hidden state | current hidden state) — same as Section 3
"sunny": {"sunny": 0.8, "rainy": 0.2},
"rainy": {"sunny": 0.4, "rainy": 0.6},
}
emission_model = { # P(observation | hidden state) — NEW for HMMs
"sunny": {"umbrella": 0.1, "no_umbrella": 0.9},
"rainy": {"umbrella": 0.8, "no_umbrella": 0.2},
}
initial_distribution = {"sunny": 0.6, "rainy": 0.4} # P(state) on day 1, before any observationsThe emission model is the genuinely new piece — it connects the hidden state to what's actually observable, and is exactly analogous to a Naive Bayes likelihood (Chapter 3): "given the TRUE state, what's the probability of THIS observation?"
5. The Three Classic HMM Problems
Problem 1: Likelihood
─────────────────────────────────────────
"Given a sequence of OBSERVATIONS, how likely is this
sequence overall?" — useful for comparing which of several
HMMs best explains a given sequence.
─────────────────────────────────────────
Problem 2: Decoding (Section 6)
─────────────────────────────────────────
"Given a sequence of OBSERVATIONS, what's the MOST LIKELY
sequence of HIDDEN states that produced them?" — e.g.
"given this umbrella sequence, what was the weather each day?"
─────────────────────────────────────────
Problem 3: Learning
─────────────────────────────────────────
"Given observed sequences, what are the BEST transition
and emission probabilities?" — an actual LEARNING problem
(typically solved with the Baum-Welch algorithm, beyond
this introductory chapter's scope, but conceptually
similar to how Naive Bayes' probabilities were learned
from labeled data in Chapter 3)
─────────────────────────────────────────
This chapter focuses on Decoding (Problem 2) since it's the most illustrative and directly builds on this module's inference theme.
6. The Viterbi Algorithm
Viterbi efficiently solves the decoding problem — finding the single most likely sequence of hidden states, given a sequence of observations, without checking every possible sequence exhaustively (which would grow exponentially with sequence length).
def viterbi(observations, states, initial_dist, transition_model, emission_model):
"""
Returns the MOST LIKELY sequence of hidden states given the observations.
"""
n = len(observations)
# viterbi_table[t][state] = (probability of the BEST path ending in `state` at time t)
viterbi_table = [{} for _ in range(n)]
backpointers = [{} for _ in range(n)]
# Initialization — day 1
for state in states:
viterbi_table[0][state] = initial_dist[state] * emission_model[state][observations[0]]
backpointers[0][state] = None
# Recursion — each subsequent day, considering EVERY possible previous state
for t in range(1, n):
for state in states:
best_prev_state, best_prob = None, -1
for prev_state in states:
prob = (viterbi_table[t-1][prev_state]
* transition_model[prev_state][state]
* emission_model[state][observations[t]])
if prob > best_prob:
best_prob, best_prev_state = prob, prev_state
viterbi_table[t][state] = best_prob
backpointers[t][state] = best_prev_state
# Find the best FINAL state, then trace BACKWARD through backpointers
best_final_state = max(states, key=lambda s: viterbi_table[n-1][s])
path = [best_final_state]
for t in range(n - 1, 0, -1):
path.append(backpointers[t][path[-1]])
path.reverse()
return path
observations = ["no_umbrella", "no_umbrella", "umbrella", "umbrella", "umbrella"]
states = ["sunny", "rainy"]
most_likely_weather = viterbi(
observations, states, initial_distribution, transition_model, emission_model
)
print(most_likely_weather) # e.g. ['sunny', 'sunny', 'rainy', 'rainy', 'rainy']Why Viterbi Is Efficient
─────────────────────────────────────────
Naive approach: check EVERY possible state sequence —
grows as (num_states)^sequence_length,
exponential and infeasible for long sequences
Viterbi: at each time step, only keeps the SINGLE
best path leading to each state (using
DYNAMIC PROGRAMMING — building on smaller
subproblems) — grows only LINEARLY with
sequence length
─────────────────────────────────────────
This dynamic-programming structure — building the best answer incrementally from smaller subproblems, rather than re-solving from scratch — is the same fundamental idea behind @lru_cache-style memoization (Python Notes, Module 5, Chapter 4), applied here to sequences of hidden states instead of recursive function calls.
7. Where HMMs Are Used
Historical & Modern Applications
─────────────────────────────────────────
Speech recognition: hidden states = actual words/phonemes
spoken; observations = the raw audio
signal — HMMs were the DOMINANT speech
recognition technique for decades,
before deep learning (DL notes) took over
Part-of-speech tagging: hidden states = grammatical role
(noun, verb, ...); observations =
the actual words — a classical
NLP technique (NLP/LLM notes cover
its modern successors)
Bioinformatics: hidden states = gene/regulatory
regions; observations = the
DNA sequence itself
Robot localization: hidden states = the robot's
TRUE position; observations =
noisy sensor readings
─────────────────────────────────────────
HMMs were largely superseded by deep learning (RNNs, transformers — covered in the Deep Learning and NLP/LLM notes) for speech and language tasks specifically — but the underlying Markov assumption and dynamic-programming decoding technique remain foundational, and HMMs are still genuinely used today in bioinformatics and simpler sequential-modeling contexts where their transparency and lower data requirements are an advantage.
8. Summary & Next Steps
Key Takeaways
- The Markov assumption states that the future depends only on the present state, not the full history — a simplifying assumption that makes sequential reasoning computationally tractable, echoing Chapter 3's Naive Bayes independence assumption.
- A Markov chain models a sequence of directly observable states via a transition model; a Hidden Markov Model adds an emission model connecting unobservable hidden states to observable evidence.
- The Viterbi algorithm efficiently finds the most likely hidden state sequence using dynamic programming, growing linearly rather than exponentially with sequence length.
- HMMs were historically dominant in speech recognition and NLP before deep learning, and remain useful today in bioinformatics and other domains where transparency and lower data requirements matter.
Concept Check
- What does the Markov assumption simplify away, and why is that trade-off usually worth it?
- What's the key structural difference between a Markov chain and a Hidden Markov Model?
- Why is the Viterbi algorithm's dynamic-programming approach so much more efficient than checking every possible state sequence directly?
Next Chapter
→ Chapter 5: Decision Theory & Utility
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index