Hidden Markov Models: Inferring the Unobserved State From the Observed One

The world is full of situations where the quantity you actually care about is hidden, and the data you can collect is only a noisy proxy. A doctor cannot directly measure whether a patient has a disease — only the symptoms. A speech recognition system cannot directly read what the speaker meant to say — only the audio waveform it picks up. A weather forecaster cannot directly observe atmospheric pressure at every point — only sparse measurements at scattered stations. The underlying state is hidden, and inference is needed to recover it.

When the hidden state evolves according to a Markov chain — its next state depends only on its current state, not on the deeper history — and the observations depend probabilistically on the current state, the resulting model is a Hidden Markov Model (HMM). HMMs are one of the most successful classes of probabilistic models in the history of applied mathematics. They were used in cryptography in the 1960s, in DNA sequence analysis from the 1980s, in speech recognition (with overwhelming impact) from the 1970s through 2010s, and remain widely used today across many fields.

This article is about what HMMs are, the three classical problems they pose, and how their algorithmic solutions made the model so dominant.

The setup

An HMM consists of three ingredients:

1. A finite set of hidden states $\{S_1, S_2, \dots, S_N\}$. At each time step $t$, the system is in some state $X_t$.

2. A transition matrix $A = (a_{ij})$, where $a_{ij} = P(X_{t+1} = S_j \mid X_t = S_i)$ is the probability of moving from state $i$ to state $j$.

3. An emission distribution: at each time step $t$, the system emits an observation $Y_t$ whose probability depends only on the current hidden state. For discrete observations $\{O_1, O_2, \dots, O_M\}$, the emission matrix $B = (b_i(O_k))$ specifies $b_i(O_k) = P(Y_t = O_k \mid X_t = S_i)$.

The system evolves over time. Starting from some initial state distribution $\pi$, the hidden state follows the Markov chain $A$, and at each step an observation is emitted according to $B$. You see the observation sequence $Y_1, Y_2, \dots, Y_T$ but not the hidden state sequence $X_1, X_2, \dots, X_T$.

The graphical structure makes the conditional independence assumptions vivid. Each $X_t$ depends only on $X_{t-1}$ (Markov property), and each $Y_t$ depends only on $X_t$ (emission property). The model has a great deal of mathematical structure precisely because of these assumptions.

The three classical problems

The HMM literature traditionally identifies three computational problems, with three corresponding algorithms.

Problem 1: Evaluation. Given an HMM with parameters $\lambda = (A, B, \pi)$ and an observation sequence $Y_1, \dots, Y_T$, compute the probability $P(Y_1, \dots, Y_T \mid \lambda)$ that the model produces this observation sequence.

This is solved by the forward algorithm. The naïve approach — sum over all $N^T$ possible hidden state sequences — is exponential and unusable. The forward algorithm uses dynamic programming: define $\alpha_t(i) = P(Y_1, \dots, Y_t, X_t = S_i \mid \lambda)$ and compute these recursively:

$\alpha_t(j) = \left[\sum_{i=1}^N \alpha_{t-1}(i) \, a_{ij}\right] b_j(Y_t).$

The forward algorithm runs in $O(T \cdot N^2)$ time. The total probability of the observation sequence is $\sum_i \alpha_T(i)$.

The forward algorithm answers the question “how likely is this observation, under this model?” This is useful for model selection (which HMM best explains a given dataset?) and for anomaly detection (does this new observation sequence look like the past?).

Problem 2: Decoding. Given an HMM and an observation sequence, find the most likely sequence of hidden states $X_1, \dots, X_T$.

This is solved by the Viterbi algorithm, discovered by Andrew Viterbi in 1967 for decoding convolutional codes in noisy communication channels. Like the forward algorithm, it uses dynamic programming, but it propagates the maximum probability path rather than the sum over paths. Define $\delta_t(i) = \max_{X_1, \dots, X_{t-1}} P(X_1, \dots, X_{t-1}, X_t = S_i, Y_1, \dots, Y_t \mid \lambda)$ and compute:

$\delta_t(j) = \max_i \big[\delta_{t-1}(i) \, a_{ij}\big] \cdot b_j(Y_t).$

Backtracking through the maximisations gives the single most-likely hidden state sequence. The Viterbi algorithm runs in $O(T \cdot N^2)$ time and is the standard tool whenever the interpretation of an observation is required: “what was the speaker actually saying?”, “what gene boundaries does this DNA contain?”, “what part-of-speech tag goes with each word?”

Problem 3: Learning. Given only a set of observation sequences (and no information about the hidden states), estimate the HMM parameters $(A, B, \pi)$ that maximise the likelihood of the observations.

This is solved by the Baum–Welch algorithm, a special case of the expectation-maximisation (EM) algorithm. The algorithm alternates two steps:

• Expectation step: using current parameters, compute the expected counts of state transitions and emissions (using the forward and backward algorithms).
• Maximisation step: re-estimate parameters by treating the expected counts as observed and computing maximum likelihood estimates.

The algorithm converges to a local maximum of the likelihood. It is iterative and does not guarantee a global optimum, but it is reliably effective in practice.

Why HMMs took over speech recognition

The clearest demonstration of HMM power came in the speech recognition industry, where they dominated from roughly 1975 until the rise of deep learning around 2010. The picture is roughly:

A speech utterance is sampled into a sequence of short audio frames (every $10$ ms, say). Each frame is converted to a feature vector capturing the spectral content of the speech. The hidden states correspond to phonemes (or sub-phonemic units), and the transitions and emissions are learned from training data — millions of hours of audio with corresponding text transcripts. To recognise a new utterance, run the Viterbi algorithm to find the most likely phoneme sequence, then combine with a language model to find the most likely word sequence.

This recipe powered Apple’s Siri (early versions), Google Voice Search (pre-deep-learning), Dragon Naturally Speaking, automated telephone systems, and many other products. The mathematical machinery — Forward, Viterbi, Baum–Welch — provided the underlying engine for billions of voice queries.

Deep learning has since displaced HMMs as the dominant technology for speech recognition. Modern systems use neural networks (often recurrent or transformer architectures) to map audio to text directly. But HMMs did not disappear; many systems still use them in hybrid architectures where neural networks compute emission probabilities while HMMs provide the temporal structure, and they remain dominant in fields like bioinformatics and finance where data is scarcer and the simpler models perform better.

Beyond speech: where HMMs live

The same architecture has been applied across an extraordinary number of domains:

Bioinformatics. HMMs are used to identify genes within DNA sequences (the hidden state distinguishes coding regions from non-coding regions; the observations are the base pairs), to find protein domains in amino-acid sequences (the hidden state encodes structural family), and to align multiple sequences via profile HMMs. The HMMER software package is the standard tool in protein sequence analysis.

Finance. Markets are sometimes modelled as switching between regimes (bull, bear, high-volatility, low-volatility) with the hidden regime not directly observable but inferable from price movements. Regime-switching HMMs have been used in asset-pricing models, risk management, and algorithmic trading.

Natural-language processing. Part-of-speech tagging — labelling each word in a sentence with noun, verb, etc. — was the standard HMM application from the 1990s. The hidden state is the part-of-speech tag; the observation is the word. The Viterbi algorithm finds the most likely tag sequence given the words.

Robotics and tracking. State estimation for a robot (where am I in the room?), object tracking from radar or video, and pedestrian tracking in autonomous vehicles all use HMM-like models — though often in the continuous-state setting of the Kalman filter rather than the discrete-state HMM.

Activity recognition. Wearable devices that determine whether the user is sitting, walking, running, or sleeping use HMMs on accelerometer data: the hidden state is the activity; the observations are sensor readings.

A unifying methodological lesson

What HMMs really demonstrate is a methodological principle: structured probabilistic models, combined with efficient inference algorithms, can solve problems that look completely different on the surface but share the same underlying mathematical structure. The same Viterbi algorithm decodes a noisy radio signal in a satellite link, parses a sentence in part-of-speech tagging, finds genes in DNA, and identifies phonemes in speech. The applications look completely unrelated; the underlying mathematics is the same.

This is a recurring pattern in applied mathematics. A general framework — HMMs, Bayesian networks, Markov decision processes, neural networks — gets adopted across many fields because its structural assumptions match what people need. The framework brings with it efficient algorithms (Viterbi, belief propagation, value iteration, backpropagation) that work in every instance. Domain experts customise the framework with domain-specific transition and emission distributions, and the general algorithm does the heavy computational lifting.

HMMs were one of the earliest such frameworks to achieve this kind of cross-disciplinary success. Sixty years after Andrew Viterbi designed his algorithm for a specific problem in noisy-channel decoding, the same algorithm is running, somewhere in the world, every second, to recognise speech, analyse DNA, tag text, or detect financial regime shifts. That is the mark of a foundational mathematical idea: it stops being about its original problem and becomes a general tool that an entire ecosystem of fields adopts.

The mathematics is simple — Markov chains and conditional probabilities. The applications are not. The bridge from one to the other is the kind of work that defines applied mathematics at its best.

Frequently asked

What makes a Markov chain 'hidden'?

In an ordinary Markov chain, you observe the state directly: the system is in state A at time t = 0, state B at time t = 1, and so on. In a Hidden Markov Model (HMM), the state is invisible. You can only observe some random output that the state produces. The fundamental task is to infer something about the unobserved state from the observed sequence of outputs. This is what makes HMMs the natural model for many real problems: speech recognition (the phoneme is hidden, the audio waveform is observed), DNA sequencing (the gene structure is hidden, the base-pair sequence is observed), and many others.

What is the Viterbi algorithm?

It is a dynamic-programming algorithm that finds the most likely sequence of hidden states given a sequence of observations. Discovered by Andrew Viterbi in 1967 for decoding convolutional codes in noisy communication channels, it works by maintaining at each time t the most likely path ending in each state, then extending those paths step by step. The total runtime is O(T·N²) for T observations and N hidden states — quadratic in the state-space size and linear in the sequence length. The Viterbi algorithm is the workhorse of HMM decoding.

What are the three classical HMM problems?

First, evaluation: given an HMM and an observation sequence, what is the probability that the observations were produced by this model? Solved by the forward algorithm. Second, decoding: given an HMM and observations, what is the most likely sequence of hidden states? Solved by the Viterbi algorithm. Third, learning: given just a set of observation sequences, estimate the HMM parameters (transition probabilities, emission probabilities, initial state distribution). Solved by the Baum–Welch algorithm, a special case of expectation-maximisation. Together, these three problems and their solutions form the core algorithmic toolkit of HMM applications.

Where else are HMMs used?

Beyond speech and bioinformatics: in finance for regime detection (markets switching between bull, bear, and sideways regimes), in robotics for state estimation, in natural-language processing for part-of-speech tagging, in handwriting recognition, in radar and sonar tracking, in econometrics for time-series with hidden state, and in many other domains where one observes a noisy signal generated by an unobserved discrete-state system. The general-purpose 'estimate hidden discrete state from noisy observations' problem has so many instances that HMMs and their generalisations remain among the most-used probabilistic models in applied statistics.

Continue reading

Blog

The Kelly Criterion: How Much to Bet When You Have an Edge

If you have a favourable bet, what fraction of your bankroll should you wager? Bet too little and you grow too slowly. Bet too much and you risk ruin. The Kelly formula finds the unique sweet spot.

Read →Blog

Martingales: The Mathematics of Fair Games

A martingale is a random process whose expected next value, given everything you know so far, equals its current value. From this innocent rule grow the most powerful theorems in modern probability.

Read →Blog

Chebyshev's Inequality: The Universal Bound on How Far You Can Stray From the Mean

No matter what distribution you have — bell-shaped, lopsided, jagged — the chance of being more than k standard deviations from the mean is at most 1/k². One line of arithmetic, valid forever.

Read →