To reason over time, model the world as a sequence of states where the future depends only on the present. When the states themselves are hidden and only noisy observations are seen, you get a hidden Markov model (HMM).

Python

# weather Markov chain: rows = today, columns = tomorrow (sunny, rainy)
T = [[0.9, 0.1],
     [0.5, 0.5]]

def step(dist):
    return [sum(dist[i] * T[i][j] for i in range(2)) for j in range(2)]

dist = [0.0, 1.0]                      # it's raining today
tomorrow = step(dist)
for _ in range(50):
    dist = step(dist)
print([round(p, 3) for p in tomorrow])   # [0.5, 0.5]
print([round(p, 3) for p in dist])       # [0.833, 0.167] ← stationary distribution: the start no longer matters

Hidden Markov models

An HMM adds a sensor model P(Eₜ | Xₜ). The textbook umbrella world: a guard underground can't see the weather, only whether the director brings an umbrella. Rain persists with probability 0.7; the umbrella appears on 90% of rainy days and 20% of dry days.

Task	Computes	Algorithm
Filtering	`P(Xₜ \| e₁:ₜ)` — belief about now	Forward algorithm
Prediction	`P(Xₜ₊ₖ \| e₁:ₜ)` — the future	Forward, then transitions only
Smoothing	`P(Xₖ \| e₁:ₜ)`, `k < t` — the past, with hindsight	Forward–backward
Most likely explanation	`argmax P(x₁:ₜ \| e₁:ₜ)` — the best state sequence	Viterbi (dynamic programming)
Learning	Transition and sensor models from data	Baum–Welch (EM)

Python

TRANS = {True: 0.7, False: 0.3}          # P(rain today | rain yesterday = key)
SENSOR = {True: 0.9, False: 0.2}         # P(umbrella | rain = key)

def forward(evidence, prior=0.5):
    belief = {True: prior, False: 1 - prior}
    history = []
    for umbrella in evidence:
        predicted = {r: sum(belief[prev] * (TRANS[prev] if r else 1 - TRANS[prev]) for prev in (True, False))
                     for r in (True, False)}                                        # predict
        weighted = {r: predicted[r] * (SENSOR[r] if umbrella else 1 - SENSOR[r]) for r in (True, False)}
        total = sum(weighted.values())
        belief = {r: weighted[r] / total for r in (True, False)}                    # update + normalise
        history.append(round(belief[True], 3))
    return history

def viterbi(evidence, prior=0.5):
    like = lambda r, u: SENSOR[r] if u else 1 - SENSOR[r]
    trans = lambda prev, r: TRANS[prev] if r else 1 - TRANS[prev]
    best = {r: (prior * like(r, evidence[0]), [r]) for r in (True, False)}
    for u in evidence[1:]:
        best = {r: max(((p * trans(prev, r) * like(r, u), path + [r]) for prev, (p, path) in best.items()),
                       key=lambda x: x[0]) for r in (True, False)}
    return ["rain" if r else "dry" for r in max(best.values(), key=lambda x: x[0])[1]]

print(forward([True, True]))                         # [0.818, 0.883] ← P(rain) after day 1 and day 2
print(viterbi([True, True, False, True, True]))      # ['rain', 'rain', 'dry', 'rain', 'rain']

What is the Markov assumption?

What problems does an HMM solve, and with which algorithms?