Markov Chains: Memoryless Processes and Stationary Distributions

Weather tomorrow depends mostly on today's weather. A user's next click depends mostly on the current page. A board game's next position depends only on the current position and the dice. Processes like these, where the future is independent of the past given the present, are Markov chains. They underpin hidden Markov models, MCMC sampling, PageRank and — through Markov decision processes — reinforcement learning.

Definition#

A sequence of random variables $X_0, X_1, X_2, \dots$ on a state space $S$ is a (time-homogeneous) Markov chain if

P(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = P(X_{t+1} = j \mid X_t = i) = P_{ij}

The transition matrix $\mathbf{P}$ has rows that sum to one (a stochastic matrix). If $\boldsymbol{\pi}_t$ is the row vector of state probabilities at time $t$:

\boldsymbol{\pi}_{t+1} = \boldsymbol{\pi}_t\mathbf{P}, \qquad \boldsymbol{\pi}_t = \boldsymbol{\pi}_0\mathbf{P}^t

Stationary distributions#

A distribution $\boldsymbol{\pi}$ is stationary if $\boldsymbol{\pi}\mathbf{P} = \boldsymbol{\pi}$ — once the chain is distributed this way, it stays so. It is a left eigenvector of $\mathbf{P}$ with eigenvalue 1. For the weather chain: $\pi_S = 0.8\pi_S + 0.4\pi_R$ with $\pi_S + \pi_R = 1$ gives $\boldsymbol{\pi} = (2/3, 1/3)$.

When does a chain converge?#

A finite chain has a unique stationary distribution and converges to it from any starting state if it is:

Irreducible — every state can reach every other state;
Aperiodic — the chain does not cycle with a fixed period (e.g. a self-loop somewhere suffices).

Such chains are called ergodic. The ergodic theorem adds that time averages equal expectations under $\boldsymbol{\pi}$:

\frac{1}{T}\sum_{t=1}^{T} f(X_t) \to \mathbb{E}_{\boldsymbol{\pi}}[f]

This is precisely why MCMC works: build an ergodic chain whose stationary distribution is your target, run it, and average.

Detailed balance#

A sufficient (not necessary) condition for $\boldsymbol{\pi}$ to be stationary is detailed balance:

\pi_i P_{ij} = \pi_j P_{ji} \quad \text{for all } i, j

The probability flow from $i$ to $j$ equals the flow back. The Metropolis–Hastings acceptance rule is designed exactly to enforce detailed balance with respect to the target distribution.

Mixing time#

How quickly does the chain forget its start? The mixing time depends on the spectral gap $1 - |\lambda_2|$, where $\lambda_2$ is the second-largest eigenvalue magnitude of $\mathbf{P}$. A small gap means slow mixing — for example, a chain on two well-separated modes that rarely jumps between them. Slow mixing is the central practical problem of MCMC.

PageRank: a Markov chain on the web#

Model a web surfer who follows a random outgoing link with probability $d$ (the damping factor, typically 0.85) and jumps to a random page with probability $1 - d$. The random jump makes the chain irreducible and aperiodic. Each page's PageRank is its stationary probability — the long-run fraction of time the surfer spends there.

python

import numpy as np

links = {0: [1, 2], 1: [2], 2: [0], 3: [2]}      # page -> pages it links to
n, d = 4, 0.85
P = np.zeros((n, n))
for i, outs in links.items():
    for j in outs:
        P[i, j] = 1 / len(outs)
G = d * P + (1 - d) / n                           # "Google matrix"

pi = np.ones(n) / n
for _ in range(100):                              # power iteration
    pi = pi @ G
print("PageRank:", pi.round(4))

w, V = np.linalg.eig(G.T)                         # check: eigenvector with eigenvalue 1
v = np.real(V[:, np.argmin(abs(w - 1))]); print((v / v.sum()).round(4))

Page 2, which everyone links to, receives the highest rank; page 3, which nobody links to, receives only the random-jump share.

Absorbing chains#

Some states are absorbing — once entered, never left (game over, customer churn). With the fundamental matrix $\mathbf{N} = (\mathbf{I} - \mathbf{Q})^{-1}$, where $\mathbf{Q}$ holds transitions among transient states, we can compute expected steps before absorption and absorption probabilities. This is useful for modelling user journeys, student progression through a curriculum, or case-processing pipelines.

Where Markov chains appear in ML#

n-gram language models are Markov chains over words.
Hidden Markov models add noisy observations to a hidden chain.
MCMC samples from posteriors.
Markov decision processes add actions and rewards — the foundation of reinforcement learning.
Random-walk graph embeddings (DeepWalk, node2vec) learn node representations from random walks.
Diffusion models use a Markov chain that gradually adds noise, and learn the reverse chain.

#probability#markov chains#stationary distribution#pagerank#random walks

Written by

Janin A Apurba

B.Sc. in CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. Teaching AI, ML and Deep Learning to the next generation of engineers and researchers.