Markov Chains & Random Walks

1. The Markov Property and Transition Matrix

A sequence of random variables X₀, X₁, X₂, … taking values in a state space S is a Markov chain if:

All information about the future is captured by the current state. The transition probability P(j | i) = pᵢⱼ is the probability of moving from state i to state j in one step. Collecting these into a matrix gives the transition matrix P where P[i][j] = pᵢⱼ and each row sums to 1 (stochastic matrix).

Example — Sunny/Rainy Weather

The distribution after n steps starting from an initial distribution π₀ is:

Matrix powers can be computed by repeated multiplication. More efficiently, eigenvalue decomposition (P = V Λ V⁻¹, so Pⁿ = V Λⁿ V⁻¹) separates the components.

2. State Classification

A chain is irreducible if every state is reachable from every other state (the underlying directed graph is strongly connected). An irreducible, aperiodic chain on a finite state space has a unique stationary distribution.

3. Stationary Distributions and Convergence

A distribution π* is stationary if it is unchanged by the transition:

The Perron-Frobenius theorem guarantees that an irreducible, aperiodic stochastic matrix has 1 as its largest eigenvalue, with a unique positive eigenvector — the stationary distribution. For the weather example above:

This is computed analytically for 2-state chains using the balance equations. For larger state spaces, power iteration is the practical algorithm: repeatedly multiply a distribution vector by P until it stops changing.

4. PageRank — Markov Chains on the Web

Google's original PageRank algorithm models a random surfer walking the web by following hyperlinks uniformly at random. The web graph defines a transition matrix; the stationary distribution gives each page its rank.

Two complications arise:

• Dangling nodes: pages with no outgoing links trap the surfer. Fixed by redistributing probability equally to all nodes when a dangling node is reached.
• Disconnected components: the chain may not be irreducible. Fixed by the damping factor d (typically 0.85): with probability 1 − d the surfer teleports to a uniformly random page.

The Google matrix is now irreducible and aperiodic regardless of the link structure, so power iteration is guaranteed to converge. In practice ~50–100 iterations of matrix-vector multiplication suffice for the web-scale graph.

5. Random Walks and Gambler's Ruin

1-D Random Walk

At each step the walker moves +1 with probability p and −1 with probability q = 1 − p. Starting at position k, the walk is recurrent (returns to start with probability 1) when p = q = 0.5; when p ≠ q it drifts toward +∞ or −∞ and is transient.

Gambler's Ruin

A gambler starts with £k and plays against a casino with infinite funds. Each round the gambler wins £1 with probability p or loses £1 with probability q. What is the probability of reaching a fortune of £N before going bankrupt (state 0)?

Even with a tiny edge against the player (p slightly below 0.5), the probability of reaching the target N before ruin plummets exponentially. Casino games are designed exactly so that p < 0.5.

Higher-Dimensional Random Walks

In 1D and 2D, a symmetric random walk is recurrent (returns to origin with probability 1). In 3D and above it becomes transient — the drunken sailor always finds home, but the intoxicated bird is lost forever. This is Pólya's theorem (1921).

6. JavaScript: Power Iteration and Random Walk

Power Iteration for Stationary Distribution

// Power iteration: find the stationary distribution π* of a Markov chain
// P[i][j] = probability of transitioning from state i to state j
function stationaryDistribution(P, tol = 1e-9, maxIter = 10000) {
  const n = P.length;
  let pi = new Float64Array(n).fill(1 / n);  // uniform start

  for (let iter = 0; iter < maxIter; iter++) {
    const next = new Float64Array(n);
    for (let j = 0; j < n; j++)
      for (let i = 0; i < n; i++)
        next[j] += pi[i] * P[i][j];    // πP row-vector multiplication

    // Check convergence via L1 norm
    let err = 0;
    for (let j = 0; j < n; j++) err += Math.abs(next[j] - pi[j]);
    pi = next;
    if (err < tol) break;
  }
  return pi;
}

// Weather example
const P = [[0.8, 0.2], [0.4, 0.6]];
console.log(stationaryDistribution(P));  // ≈ [0.667, 0.333]

Simulating a Random Walk

// 1-D Gambler's Ruin simulation — estimate ruin probability empirically
function simulateRuin(start, target, p, trials = 10_000) {
  let ruined = 0;
  for (let t = 0; t < trials; t++) {
    let x = start;
    while (x > 0 && x < target) {
      x += Math.random() < p ? 1 : -1;
    }
    if (x === 0) ruined++;
  }
  return ruined / trials;
}

// Theoretical ruin probability (fair game)
function ruinProbFair(k, N) { return 1 - k / N; }
function ruinProb(k, N, p) {
  const r = (1 - p) / p;
  return p === 0.5
    ? ruinProbFair(k, N)
    : (1 - Math.pow(r, k)) / (1 - Math.pow(r, N));
}

console.log('Simulated:',  simulateRuin(10, 20, 0.5).toFixed(3));  // ≈ 0.500
console.log('Theoretical:', ruinProb(10, 20, 0.5).toFixed(3));  // 0.500

PageRank with Power Iteration

// Tiny 4-page web graph (0-indexed adjacency list)
function pageRank(edges, n, d = 0.85, iters = 100) {
  // Build row-stochastic transition matrix with dangling-node fix
  const out = new Array(n).fill(0);
  edges.forEach(([i]) => out[i]++);

  let rank = new Float64Array(n).fill(1 / n);

  for (let it = 0; it < iters; it++) {
    const next = new Float64Array(n).fill((1 - d) / n);
    for (const [i, j] of edges) next[j] += d * rank[i] / out[i];
    rank = next;
  }
  return rank;
}

const graph = [[0,1],[0,2],[1,2],[2,0],[3,2]];
console.log(pageRank(graph, 4));  // node 2 should rank highest

7. Continuous-Time Markov Chains

In discrete-time chains steps happen at integer times. A continuous-time Markov chain (CTMC) can jump at any t ≥ 0. The key object is the generator matrix Q (also called the rate matrix):

The probability distribution evolves via the forward equation (Kolmogorov):

CTMCs model queueing systems (M/M/1 queue), chemical reaction networks (via the chemical master equation), and failure/repair processes in reliability engineering.

8. Applications

Natural Language Processing

N-gram language models are Markov chains: the probability of the next word depends only on the previous n − 1 words. Bigram (n = 2) and trigram models were the backbone of statistical NLP before neural language models and remain useful for data-scarce domains.

Reinforcement Learning

A Markov Decision Process (MDP) extends Markov chains with actions and rewards. The agent's policy defines a Markov chain; value functions are stationary expectations under this chain. Policy evaluation, policy iteration, and value iteration all solve the underlying Markov system.

Queueing and Traffic

The M/M/1 queue (Poisson arrivals, exponential service, 1 server) is a birth-death CTMC. Its stationary distribution gives average queue length, waiting times, and utilisation as closed-form expressions — foundational results in capacity planning for networks, call-centres, and cloud infrastructure.

Molecular Dynamics / Protein Folding

Markov State Models (MSMs) discretise conformational space of a protein into metastable states. By decomposing long MD trajectories into short parallel simulations, MSMs extend accessible timescales by orders of magnitude and reveal folding pathways.