Markov Chain

A Markov chain is a stochastic process over a set of states in which the probability of the next state depends only on the current state, not on the full history of how we got there.

States and the Markov Property

Let $X_0,X_1,X_2,\dots$ be a sequence of random variables taking values in a state space $\mathcal{S}$. The chain satisfies the Markov property (memorylessness):

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

The future is conditionally independent of the past given the present.

Transition Matrix

For a finite chain, the one-step dynamics are collected in a transition matrix $P$ where $P_{ij}=P(X_{t+1}=j\mid X_t=i)$. Each row is a probability distribution, so $P$ is row-stochastic:

$P_{ij}\ge 0,{\sum }_j{P}_{ij}=1$

If ${\pi }_t$ is a row vector giving the distribution over states at time $t$, then ${\pi }_{t+1}={\pi }_{t}P$.

n-Step Transitions

The probability of going from $i$ to $j$ in exactly $n$ steps is the $(i,j)$ entry of the matrix power (Chapman-Kolmogorov):

$P^{(n)}=P^n,P(X_{t+n}=j\mid X_t=i)=(P^n{)}_{ij}$

Stationary Distribution

A distribution $\pi$ is stationary if it is unchanged by one step:

$\pi P=\pi ,{\sum }_i{\pi }_i=1$

So $\pi$ is a left eigenvector of $P$ with eigenvalue 1.

Ergodicity

If the chain is irreducible (every state reachable from every other) and aperiodic, it is ergodic: a unique stationary distribution exists and ${\pi }_t\to \pi$ regardless of the starting distribution. This convergence is what MCMC sampling relies on.

Absorbing chains

A state $i$ is absorbing if $P_{ii}=1$ (once entered, never left). A chain with absorbing states does not converge to a single interior stationary distribution; instead the interesting questions are absorption probabilities and expected time to absorption, computed from the fundamental matrix $(I-Q{)}^{-1}$ over the transient block $Q$.

Code

import numpy as np
 
# 3-state weather chain: sunny, cloudy, rainy
P = np.array([
    [0.8, 0.15, 0.05],
    [0.3, 0.4,  0.3 ],
    [0.2, 0.45, 0.35],
])
assert np.allclose(P.sum(axis=1), 1)   # rows are distributions
 
# n-step transitions via matrix power
P3 = np.linalg.matrix_power(P, 3)
print("3-step:\n", P3)
 
# same thing with einsum (chaining three factors)
P3_einsum = np.einsum('ij,jk,kl->il', P, P, P)
assert np.allclose(P3, P3_einsum)
 
# stationary distribution = left eigenvector with eigenvalue 1
# left eigenvectors of P == right eigenvectors of P.T
vals, vecs = np.linalg.eig(P.T)
idx = np.argmin(np.abs(vals - 1.0))
pi = np.real(vecs[:, idx])
pi = pi / pi.sum()
print("stationary:", pi)
 
# check: pi P == pi
print("fixed point check:", np.allclose(pi @ P, pi))

Cross-check by iteration

Running pi = np.ones(3)/3 then for _ in range(200): pi = pi @ P converges to the same vector, confirming ergodic convergence numerically.

Connections

Diffusion models define a forward process as a fixed Markov chain that gradually adds Gaussian noise, then learn to reverse it; each denoising step conditions only on the current noisy sample, exactly the Markov property. Adding actions and rewards to a Markov chain yields Markov Decision Processes, the foundation of reinforcement learning.

Related

See Diffusion Models for Markov chains as noising processes, Markov Decision Processes for the decision-theoretic extension, Hidden Markov Models where the state is latent and only emissions are observed, and Bayes Theorem and Conditional Probability for the conditioning that underlies every transition.