Markov Models

Markov chains, hidden states, sensor models, filtering, prediction, smoothing, and Viterbi decoding for uncertain sequences.

Many environments evolve over time. Traffic changes, machines degrade, users switch activities, and speech unfolds as a sequence. A sequential model connects uncertain states across time rather than treating observations independently.

Markov Property

A first-order Markov model assumes:

P(X_t | X_0,...,X_{t-1}) = P(X_t | X_{t-1})

The present state contains the history needed to predict the next state. This is a modelling choice, not a universal law. If day of week affects future traffic, include it in the state.

Markov Chains

A Markov chain has an initial distribution and transition probabilities.

From \ To	Sunny	Rainy
Sunny	0.8	0.2
Rainy	0.4	0.6

If today is certainly sunny, tomorrow is (0.8, 0.2). The next day:

P(Sunny) = 0.8×0.8 + 0.2×0.4 = 0.72
P(Rainy) = 0.8×0.2 + 0.2×0.6 = 0.28

In vector form:

belief_{t+1} = belief_t T

Some chains approach a stationary distribution. Periodic or disconnected chains may not converge in the same way.

State Design

The Markov assumption depends on the state representation. Suppose failure risk depends on how long a machine has been overheated. A state containing only hot or normal loses that duration, so the next state still depends on earlier history.

Possible repairs include:

add temperature duration to the state;
use a higher-order model depending on several previous states;
introduce a hidden degradation variable;
use a model with explicit state durations.

Adding memory can improve validity but expands the state space and demands more data. State design should preserve predictive information without recording an unnecessary history.

Time Assumptions

The standard transition table is often stationary: the same P(X_t | X_{t-1}) is used at every time. Real processes may change by season, operating regime, or intervention. A stationary model can average incompatible behaviors and become badly calibrated during each regime.

Possible extensions include:

time-dependent transition matrices;
context variables such as weekday or workload;
separate regime states;
online parameter updates;
explicit change-point models.

An HMM also implies a geometric state-duration distribution: at each step, the chance of leaving depends only on the current state, not how long the system has remained there. If activities have characteristic durations, a hidden semi-Markov model can represent duration explicitly.

Time resolution is another modelling choice. Sampling every second and every hour produces different transition probabilities and may change whether first-order dependence is adequate. Train and deploy at compatible intervals, and represent missing intervals rather than pretending they are ordinary one-step transitions.

Hidden States

In a hidden Markov model (HMM), the true state is not directly observed. The model contains:

hidden state X_t;
observation E_t;
transition model P(X_t|X_{t-1});
emission model P(E_t|X_t);
initial distribution.

A machine may be healthy or degraded, while the sensor reports normal or unusual sound. Neither observation proves a state.

Filtering

Filtering computes the current belief from evidence so far. Each step:

predicts through the transition model;
multiplies by observation likelihood;
normalizes.

def normalize(values):
    total = sum(values.values())
    if total == 0:
        raise ValueError("Impossible evidence")
    return {key: value / total for key, value in values.items()}

def filter_step(previous, observation, states, transition, emission):
    predicted = {
        current: sum(
            previous[prior] * transition[prior][current]
            for prior in states
        )
        for current in states
    }
    return normalize({
        state: predicted[state] * emission[state][observation]
        for state in states
    })

Maintain the full belief distribution. Selecting one state too early discards uncertainty that later evidence may resolve.

Numeric Step

Assume the previous belief is:

P(Healthy)=0.7, P(Degraded)=0.3

and the transition model predicts:

P(Healthy_t)=0.7(0.9)+0.3(0.4)=0.75
P(Degraded_t)=0.7(0.1)+0.3(0.6)=0.25

If an unusual sound has likelihood 0.1 when healthy and 0.8 when degraded, the unnormalized update is (0.075, 0.20). After normalization:

P(Healthy | unusual) ≈ 0.273
P(Degraded | unusual) ≈ 0.727

The observation reverses the most likely state, but uncertainty remains.

Four Tasks

Prediction: estimate future state without future evidence.
Filtering: estimate the current state from evidence so far.
Smoothing: revise a past state using later evidence.
Decoding: find the most likely complete hidden-state sequence.

These answer different questions. The most likely state at each moment does not necessarily form the most likely sequence because transitions couple choices.

Smoothing

Filtering cannot use observations that have not happened yet. Smoothing combines a forward message from earlier evidence with a backward message from later evidence:

P(X_t | e_1,...,e_T) ∝ forward_t × backward_t

A later series of abnormal readings can make an earlier ambiguous reading more likely to mark the start of degradation. Smoothing is useful for retrospective diagnosis and sequence annotation, but it is not available to an online controller at that earlier time.

Viterbi Decoding

Viterbi uses dynamic programming. At each time and state, it stores:

probability of the best path ending there;
predecessor on that path.

After processing the final observation, it backtracks from the best final state. This avoids enumerating exponentially many sequences.

Log probabilities prevent numerical underflow:

log(ab) = log(a) + log(b)

Impossible transitions use negative infinity in log space.

from math import log

def safe_log(probability):
    if not 0 <= probability <= 1:
        raise ValueError("invalid probability")
    return float("-inf") if probability == 0 else log(probability)

def viterbi(
    observations,
    states,
    initial,
    transition,
    emission,
):
    if not observations:
        return [], 0.0

    scores = {
        state: (
            safe_log(initial[state])
            + safe_log(emission[state][observations[0]])
        )
        for state in states
    }
    backpointers = []

    for observation in observations[1:]:
        next_scores = {}
        previous_for = {}

        for current in states:
            candidates = {
                previous: (
                    scores[previous]
                    + safe_log(transition[previous][current])
                    + safe_log(emission[current][observation])
                )
                for previous in states
            }
            best_previous = max(candidates, key=candidates.get)
            next_scores[current] = candidates[best_previous]
            previous_for[current] = best_previous

        scores = next_scores
        backpointers.append(previous_for)

    final = max(scores, key=scores.get)
    path = [final]
    for previous_for in reversed(backpointers):
        path.append(previous_for[path[-1]])
    path.reverse()
    return path, scores[final]

STATES = ("healthy", "degraded")
TRANSITION = {
    "healthy": {"healthy": 0.9, "degraded": 0.1},
    "degraded": {"healthy": 0.4, "degraded": 0.6},
}
EMISSION = {
    "healthy": {"normal": 0.9, "unusual": 0.1},
    "degraded": {"normal": 0.2, "unusual": 0.8},
}

path, log_probability = viterbi(
    ["normal", "unusual", "unusual"],
    STATES,
    {"healthy": 0.7, "degraded": 0.3},
    TRANSITION,
    EMISSION,
)
assert len(path) == 3
print(path, log_probability)

Backpointers are essential. Keeping only the highest score at the final time recovers the last state but loses which predecessor produced it. The algorithm stores one predecessor per (time, state), then reconstructs the globally best sequence backward.

Model Learning

With observed states, transition and emission probabilities can be estimated by normalized counts, usually with smoothing to avoid unjustified zeros. With hidden states, learning is harder because the training data does not say which state generated each observation.

Expectation-maximization can alternate between estimating state responsibilities and updating parameters. Different initial values may produce different local optima, and hidden-state labels may not acquire the meaning a designer expects. Domain validation is therefore necessary even when likelihood improves.

Use complete sequences for train/test splitting. Randomly splitting individual time steps leaks neighboring information and exaggerates generalization.

Sequence Metrics

Evaluation should match the use:

state accuracy measures individual labels;
sequence accuracy requires an entire path to be correct;
segment overlap evaluates detected intervals;
log likelihood evaluates probabilistic fit;
detection delay measures how late a change is recognized;
false-alarm rate matters for monitoring systems.

A model can achieve high state accuracy by predicting the common state everywhere while missing every rare failure transition. Confusion matrices, per-state recall, and transition-specific metrics expose this behavior.

Calibration over time also matters. If the filtered probability of degradation is used as an alarm score, evaluate whether predicted risk corresponds to observed frequency and whether thresholds satisfy operational costs.

Model Checks

Verify:

every transition row sums to one;
every emission distribution sums to one;
states capture relevant memory;
training and evaluation sequences are separated;
missing observations are handled explicitly;
likelihoods are calibrated against real sensor behavior.

Applications

speech recognition;
activity recognition;
equipment monitoring;
localization;
biological sequences;
user behavior;
anomaly detection.

Common Mistakes

Treating hidden state as observed.
Confusing filtering with decoding.
Using an insufficient state for the Markov assumption.
Multiplying long sequences in ordinary probability space.
Ignoring impossible evidence.
Evaluating only state accuracy when sequence quality matters.
Randomly splitting adjacent time steps across train and test sets.

Exercises

Compute three steps of a Markov chain by hand.
Implement filtering for a two-state machine model.
Compare filtering and smoothing for an early observation.
Implement Viterbi in log space.
Construct a case where per-time best states differ from the best sequence.
Design an HMM for student engagement and defend its assumptions.
Show how adding duration to the state can restore the Markov property.
Perform one forward and one backward smoothing calculation.
Explain why hidden-state labels require domain interpretation.
Trace every Viterbi table entry for a three-observation sequence.
Compare state accuracy, sequence accuracy, and detection delay.
Diagnose a nonstationary sequence and propose a model extension.
Explain how sampling interval changes transition probabilities.