Markov Chains

What is a Markov Chain?

A Markov Chain is a mathematical model for a system that transitions between discrete states over time steps $t = 0, 1, 2, \dots$

Its defining characteristic is the Markov Property (Memorylessness):

The probability of transitioning to future state $X_{t+1}$ depends EXCLUSIVELY on the current state $X_t$, completely ignoring past history:

$$P(X_{t+1} = s_j \mid X_t = s_i, X_{t-1} = s_{k}, \dots) = P(X_{t+1} = s_j \mid X_t = s_i)$$

  PAST STATES (X_0, X_1 ... X_t-1)  ──► [ CURRENT STATE X_t ] ──► FUTURE STATE X_t+1
  (Completely Ignored!)                   (Determines Next Step!)

The Transition Probability Matrix ($P$)

For a system with $N$ discrete states ${S_1, S_2, \dots, S_N}$:

The probabilities of moving from state $i$ to state $j$ are stored in an $N \times N$ Transition Matrix $P$:

$$P_{ij} = P(X_{t+1} = S_j \mid X_t = S_i)$$

                     TO STATE:
                 Sunny   Rainy
  FROM   Sunny  ┌ 0.8     0.2 ┐  Sum of each row MUST equal 1.0!
  STATE: Rainy  └ 0.4     0.6 ┘

Given an initial state probability vector $\pi_0 = [P(\text{Sunny}), P(\text{Rainy})]$:

• State distribution after 1 step: $\pi_1 = \pi_0 P$
• State distribution after $k$ steps: $\pi_k = \pi_0 P^k$

Stationary Distribution ($\pi$)

As step count $k \to \infty$, many Markov Chains reach a stable equilibrium called the Stationary Distribution $\pi$:

$$\pi = \pi P$$

Once reached, taking additional transition steps does not change state probabilities!

┌──────────────────────────┬──────────────────────────┐
│ 1. IRREDUCIBLE           │ 2. APERIODIC             │
├──────────────────────────┼──────────────────────────┤
│ It is possible to reach  │ Transitions do not loop  │
│ EVERY state from EVERY   │ in fixed deterministic   │
│ state in finite steps.   │ numerical cycles.        │
└──────────────────────────┴──────────────────────────┘

An Ergodic Markov Chain (both Irreducible and Aperiodic) is guaranteed to converge to a unique, stable stationary distribution regardless of initial state $\pi_0$.

Applications in Machine Learning

1. Google PageRank: Models a random web surfer clicking links. PageRank scores equal the stationary distribution probabilities of pages in the web graph Markov Chain.
2. Hidden Markov Models (HMMs): Sequence labeling for speech recognition and POS tagging.
3. MCMC Sampling: Generating samples from complex posterior distributions by constructing Markov Chains whose stationary state matches target distributions.

Say this out loud

A Markov Chain is a memoryless stochastic model where future states depend exclusively on the current state. Governed by a Transition Matrix P, an ergodic Markov Chain (irreducible and aperiodic) converges over time to a unique stationary distribution pi where pi = pi * P.

Followups to expect

1. What is a Absorbing Markov Chain? A chain containing states that cannot be left once entered ($P_{ii} = 1.0$), useful for modeling customer churn or survival analysis death events.
2. What is Detailed Balance? A condition $\pi_i P_{ij} = \pi_j P_{ji}$ stating that probability flux between any state pair $i$ and $j$ is equal, ensuring a symmetric stationary distribution in MCMC sampling.