Lecture 11.2: Markov Chains and Hidden Markov Models

A comprehensive analysis of Markov Chains, state properties, stationary distributions, and Hidden Markov Models (HMM).

When modelling sequential processes over time (like weather patterns, speech phonemes, or web page navigation paths), variables are rarely independent. A Markov Chain is a statistical model designed to represent sequences of events where transitions from state to state are governed by probability.

The Markov Property (Memorylessness)

A Markov Chain operates under a crucial assumption known as the Markov Property:

The future state in a sequence depends only on the current state. The path taken to reach the current state has no bearing on the future.

Mathematically, a sequence of random states $X_1, X_2, \dots, X_t$ satisfies the Markov property if: $P(X_{t+1} = s | X_t = s_t, X_{t-1} = s_{t-1}, \dots, X_1 = s_1) = P(X_{t+1} = s | X_t = s_t)$

This memoryless assumption significantly reduces computational complexity since we only need to store the current state to predict future steps.

State Transition Matrix

The probabilities of transitioning from any state to another in a single step are organized into a square matrix called the State Transition Matrix ( $A$ ).

For a system with $k$ states, $A$ is a $k \times k$ matrix where element $a_{ij}$ represents the probability of transitioning from state $i$ to state $j$ : $a_{ij} = P(X_{t+1} = j | X_t = i)$

Key Characteristics:

Row-Stochastic: Because a state must transition to one of the possible system states, the sum of probabilities in each row must equal exactly one: $\sum_{j=1}^k a_{ij} = 1.0 \quad \text{for all } i$

Concrete Examples

1. Weather Transition Scenario (2 States: Sunny, Rainy)

Suppose weather transitions are modeled as:

If it is Sunny today, the probability of it being Sunny tomorrow is $0.9$ , and Rainy is $0.1$ .
If it is Rainy today, the probability of it being Rainy tomorrow is $0.6$ , and Sunny is $0.4$ .

The corresponding transition matrix is:

From \ To	Sunny	Rainy
Sunny	$0.9$	$0.1$
Rainy	$0.4$	$0.6$

$\text{Transition Matrix } A = \begin{pmatrix} 0.9 & 0.1 \\ 0.4 & 0.6 \end{pmatrix}$

A user browsing a website transitions between pages with probabilities represented by:

$\text{Transition Matrix } A = \begin{pmatrix} 0.5 & 0.3 & 0.2 \\ 0.2 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.7 \end{pmatrix}$

Types of States in a Markov Chain

Different configurations of paths in a Markov chain yield various state classifications:

Transient State: A state that, once left, has a non-zero probability of never being visited again.
Recurrent State: A state to which the process is guaranteed to return eventually (with probability $1.0$ ).
Absorbing State: A state that is impossible to leave once entered (transition probability $a_{ii} = 1.0$ ).
Periodic State: A state that can only be returned to in multiples of a fixed number of steps $d > 1$ (e.g., you can only return to it on steps $3, 6, 9 \dots$ ).
Aperiodic State: A state with no fixed return cycles ( $d = 1$ ).
Ergodic State: A state that is recurrent, aperiodic, and positive recurrent (finite expected return time). If all states in a chain are ergodic, the chain is ergodic.
Accessible State: State $j$ is accessible from state $i$ if there is a path of transitions with non-zero probability leading from $i$ to $j$ .
Communicating States: States $i$ and $j$ communicate if they are mutually accessible ( $i \rightarrow j$ and $j \rightarrow i$ ).

Stationary Distribution

A stationary distribution $\pi^*$ is a probability distribution over states that remains unchanged after applying the transition matrix. It satisfies the matrix equation:

$\pi^* A = \pi^*$

Where $\sum \pi_i^* = 1.0$ . In an ergodic Markov chain, the system will eventually converge to this unique stationary distribution regardless of the initial starting state.

Step-by-Step Numerical Example

Consider a 3-state Markov chain (States: $R$ , $C$ , $S$ ) with the transition matrix:

$A = \begin{pmatrix} 0.5 & 0.3 & 0.2 \\ 0.4 & 0.2 & 0.4 \\ 0.0 & 0.3 & 0.7 \end{pmatrix}$

Let the current state probability distribution at step $t$ be: $\pi_t = [0.2, 0.5, 0.3]$

To calculate the probability distribution at step $t+1$ , we multiply $\pi_t$ by the transition matrix $A$ : $\pi_{t+1}(R) = \pi_t(R)a_{RR} + \pi_t(C)a_{CR} + \pi_t(S)a_{SR} = 0.2(0.5) + 0.5(0.4) + 0.3(0.0) = 0.1 + 0.2 + 0 = \mathbf{0.3}$ $\pi_{t+1}(C) = \pi_t(R)a_{RC} + \pi_t(C)a_{CC} + \pi_t(S)a_{SC} = 0.2(0.3) + 0.5(0.2) + 0.3(0.3) = 0.06 + 0.1 + 0.09 = \mathbf{0.25}$ $\pi_{t+1}(S) = \pi_t(R)a_{RS} + \pi_t(C)a_{CS} + \pi_t(S)a_{SS} = 0.2(0.2) + 0.5(0.4) + 0.3(0.7) = 0.04 + 0.2 + 0.21 = \mathbf{0.45}$

So the updated distribution is: $\pi_{t+1} = [0.3, 0.25, 0.45]$

If we repeat this multiplication many times, the distribution stabilizes. For this matrix, the stationary distribution converges to: $\pi^* \approx [0.218, 0.273, 0.509]$

This means that in the long run, the system will spend approximately $21.8\%$ of the time in state $R$ , $27.3\%$ in state $C$ , and $50.9\%$ in state $S$ .

Hidden Markov Model (HMM)

In a standard Markov Chain, every state is directly observable. However, in many real-world systems, the true physical states are hidden from us, and we can only observe indirect outcomes (emissions) generated by those states.

A Hidden Markov Model (HMM) extends the Markov Chain by separating the hidden states from the observable events.

Components of an HMM

An HMM is mathematically defined by the tuple $\lambda = (A, B, \pi)$ :

Hidden States ( $Q$ ): A set of $N$ underlying states $\{q_1, q_2, \dots, q_N\}$ that transition according to the Markov property.
Transition Matrix ( $A$ ): An $N \times N$ matrix representing probabilities of moving between hidden states.
Observations ( $O$ ): A set of $M$ possible observable events $\{o_1, o_2, \dots, o_M\}$ .
Emission Matrix ( $B$ ): An $N \times M$ matrix representing the probability of observing event $o_j$ when in hidden state $q_i$ : $b_i(j) = P(O_t = o_j | X_t = q_i)$
Initial Distribution ( $\pi$ ): A vector representing the probability of starting in each hidden state at time $t=0$ .

Classical Example: Eisner's Ice Cream Diary

Suppose we want to reconstruct Baltimore's daily summer weather history (Hidden States: Hot (H) vs. Cold (C)) solely using Jason Eisner's diary entries listing the number of ice creams he ate each day (Observations: 1, 2, or 3 ice creams).

Weather states (H, C) follow a Markov transition matrix $A$ .
Ice cream counts (1, 2, 3) are emitted from those weather states with probabilities in emission matrix $B$ (e.g., eating 3 ice creams is highly likely on a Hot day but rare on a Cold day).

Question: Given HMM parameters $\lambda = (A, B, \pi)$ and an observation sequence $O = o_1 o_2 \dots o_T$ , what is the probability $P(O | \lambda)$ that this sequence was generated by the model?
Solution: Solved efficiently in $O(N^2 T)$ time using the Forward Algorithm or Backward Algorithm (dynamic programming algorithms that sum probabilities over all possible hidden paths).

2. The Decoding Problem

Question: Given HMM parameters $\lambda = (A, B, \pi)$ and an observation sequence $O = o_1 o_2 \dots o_T$ , what is the most likely sequence of hidden states $Q = q_1 q_2 \dots q_T$ that produced the observations?
Solution: Solved using the Viterbi Algorithm, which utilizes dynamic programming and backtracking to find the single "maximum probability path" (Viterbi path) through the hidden states.

3. The Learning Problem

Question: Given only an observation sequence $O$ and a set of states, how do we learn the optimal HMM parameters $\lambda = (A, B, \pi)$ that maximize $P(O | \lambda)$ ?
Solution: Solved using the Baum-Welch Algorithm (a specialized case of the Expectation-Maximization (EM) algorithm) which iteratively estimates state transitions and emissions to converge on local likelihood maxima.