Markov Chains Cheat Sheet
Explains states, transition matrices, and the Markov property, and shows how to simulate chains and compute stationary distributions in Python.
2 PagesIntermediateMar 18, 2026
Core Concepts
Foundational vocabulary for Markov chains.
- Markov property- The future state depends only on the current state, not the full history ("memorylessness")
- State space- The set of all possible states the system can occupy
- Transition matrix P- P[i][j] = probability of moving from state i to state j; each row sums to 1
- Stationary distribution- A distribution pi such that pi*P = pi; describes the chain's long-run behavior if it exists and is unique
- Ergodic chain- Irreducible and aperiodic chain that converges to a unique stationary distribution regardless of start state
- Absorbing state- A state that, once entered, cannot be left (P[i][i] = 1)
Simulating a Markov Chain
Sample a sequence of states from a transition matrix.
python
import numpy as npstates = ['Sunny', 'Rainy', 'Cloudy']P = np.array([ [0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5],])def simulate(start_idx, n_steps, P): current = start_idx path = [current] for _ in range(n_steps): current = np.random.choice(len(P), p=P[current]) path.append(current) return [states[i] for i in path]print(simulate(0, 10, P))
Stationary Distribution
Solve pi*P = pi via the eigenvector for eigenvalue 1.
python
import numpy as npeigvals, eigvecs = np.linalg.eig(P.T)stationary = eigvecs[:, np.isclose(eigvals, 1)]stationary = (stationary / stationary.sum()).real.flatten()print(dict(zip(states, stationary)))# Alternative: repeatedly multiply P by itself for large powers and inspect any row
Applications
Where Markov chains show up in data science.
- PageRank- Random surfer model treats web pages as states and links as transitions
- Hidden Markov Models- Extend chains with unobserved states inferred from observed emissions (speech recognition, POS tagging)
- MCMC sampling- Markov Chain Monte Carlo builds a chain whose stationary distribution is the target posterior
- Customer journey modeling- Model transitions between marketing touchpoints or app screens
N-Step Transitions & Chapman-Kolmogorov
Compute the probability of moving between states in exactly n steps via matrix powers.
python
import numpy as npfrom numpy.linalg import matrix_power# Chapman-Kolmogorov: P^(m+n) = P^m @ P^n, so P^n is just the matrix powerP = np.array([ [0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5],])P5 = matrix_power(P, 5)print("P(state_5 = j | state_0 = Sunny):", P5[0])# Probability of being in state j after n steps from an initial distributioninitial = np.array([1.0, 0.0, 0.0]) # start deterministically in Sunnydist_n = initial @ matrix_power(P, 10)print("Distribution after 10 steps:", dist_n)
State & Chain Classification
Vocabulary for reasoning about long-run chain behavior beyond stationarity.
- Communicating class- A maximal set of states that can all reach each other; the chain's state space partitions into communicating classes
- Irreducible chain- The entire state space is a single communicating class -- every state reachable from every other
- Transient state- A state that, once left, has nonzero probability of never being revisited
- Recurrent state- A state that is revisited infinitely often with probability 1; positive recurrent if the expected return time is finite
- Periodic state- A state with period d > 1 means returns are only possible at multiples of d steps; period 1 means aperiodic
- Closed class- A communicating class the chain can never leave once entered (generalizes absorbing states to sets of states)
- Ergodic theorem- For an irreducible, positive-recurrent, aperiodic chain, time averages along a single long trajectory converge to the stationary distribution
Absorbing Chains: Fundamental Matrix
Compute expected steps to absorption and absorption probabilities using the canonical form.
python
import numpy as np# Canonical form: reorder states as [transient..., absorbing...]# P = [[Q, R], [0, I]] where Q is transient-to-transient, R is transient-to-absorbingQ = np.array([ [0.5, 0.2], [0.1, 0.6],])R = np.array([ [0.3, 0.0], [0.1, 0.2],])I = np.eye(Q.shape[0])N = np.linalg.inv(I - Q) # fundamental matrixexpected_steps = N.sum(axis=1) # expected visits to each transient state before absorptionabsorption_probs = N @ R # probability of ending in each absorbing stateprint("Expected steps to absorption:", expected_steps)print("Absorption probabilities:\n", absorption_probs)
Mean First Passage Time
Expected number of steps to first reach state j starting from state i, solved as a linear system.
python
import numpy as npdef mean_first_passage(P, target): n = P.shape[0] others = [i for i in range(n) if i != target] Q = P[np.ix_(others, others)] I = np.eye(len(others)) # m = (I - Q)^-1 @ 1 solves m_i = 1 + sum_j Q[i,j] * m_j for i != target m = np.linalg.solve(I - Q, np.ones(len(others))) result = np.zeros(n) for idx, i in enumerate(others): result[i] = m[idx] return resultP = np.array([ [0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5],])print("Expected steps to reach state 2:", mean_first_passage(P, target=2))
Checking Reversibility (Detailed Balance)
A chain is reversible w.r.t. pi if pi_i * P[i,j] == pi_j * P[j,i] for all i, j -- the property MCMC samplers rely on.
python
import numpy as npdef is_reversible(P, pi, tol=1e-8): n = len(pi) for i in range(n): for j in range(n): lhs = pi[i] * P[i, j] rhs = pi[j] * P[j, i] if abs(lhs - rhs) > tol: return False return True# Symmetric random walk on a cycle is reversible w.r.t. the uniform distributionP = np.array([ [0.0, 0.5, 0.5], [0.5, 0.0, 0.5], [0.5, 0.5, 0.0],])pi = np.array([1/3, 1/3, 1/3])print("Reversible:", is_reversible(P, pi))
Pro Tip
Before trusting a stationary distribution, verify the chain is irreducible (every state reachable from every other) and aperiodic -- otherwise pi*P = pi may not be unique or may never be reached from your starting state.
Was this cheat sheet helpful?
Explore Topics
#MarkovChains#MarkovChainsCheatSheet#DataScience#Intermediate#CoreConcepts#SimulatingAMarkovChain#StationaryDistribution#Applications#MachineLearning#CheatSheet#SkillVeris
