A hidden Markov model (HMM) describes a system that hops between unseen hidden states (here Sunny / Rainy / Foggy) while emitting visible observations (Walk / Shop / Clean). You only see the observations; the states are hidden.

Two matrices

• Transition A: A[i][j] is the probability of moving from state i to state j.
• Emission B: B[i][k] is the probability that state i emits observation k.

Sampling

Start from the initial distribution, draw a state, emit an observation from B, then draw the next state from A. Repeat T times to build the observation strip and the (hidden) true path.

Viterbi decoding

The Viterbi algorithm finds the single most likely state path. It fills a trellis with δ_t(j) = max_i δ_{t−1}(i)·A[i][j]·B[j][o_t], stores back-pointers, then traces back from the best final state. The highlighted path on the lattice is this recovered sequence.

Forward algorithm

The forward pass sums over all paths to give per-step state probabilities P(state | observations) and the total sequence likelihood P(O). We use log-arithmetic to avoid underflow.