Stochastic processes

The last lesson left three phrases on the table — Markov chain, stationary distribution, walk it — promising they were what let MCMC sample the unsampleable. Here they are, unpacked. A random variable is a single uncertain number; a stochastic process is the step up: a whole collection of random variables indexed by time, {X_t} — randomness that unfolds. Think of it as a random function: each run gives a different trajectory. It sounds abstract, but modern ML is built on these processes — a diffusion model’s noising is one, a reinforcement-learning environment is one, and MCMC, as promised, works by walking one.

Markov chains: the future depends only on the present

The most important stochastic process for ML is the Markov chain, which obeys the Markov property: the next state depends only on the current state, not the entire history.

P(X_{t+1} | X_t, X_{t-1}, ..., X_0)  =  P(X_{t+1} | X_t)

A finite Markov chain is fully described by a transition matrix P, where P[i, j] is the probability of moving from state i to state j (each row sums to 1). If p_t is the distribution over states at time t, the next step is just a matrix multiply: p_{t+1} = p_t P.

The stationary distribution

Run the chain long enough and the distribution over states stops changing — it reaches a stationary distribution π satisfying πP = π (it is the left eigenvector of P with eigenvalue 1). Under mild conditions, the chain converges to the same π regardless of where it started. Watch it happen from “definitely in state A”:

import numpy as np
P = np.array([[0.9, 0.1],
              [0.5, 0.5]])      # rows sum to 1
p = np.array([1.0, 0.0])        # start certain we're in state A

for t in [1, 2, 5, 20]:
    p_t = p @ np.linalg.matrix_power(P, t)
    print(f"t={t:>2}: {np.round(p_t, 4)}")

t= 1: [0.9 0.1]
t= 2: [0.86 0.14]
t= 5: [0.835 0.165]
t=20: [0.8333 0.1667]

The distribution marches to [0.8333, 0.1667] = [5/6, 1/6] and stays there — the stationary distribution. This single fact is the engine of MCMC: if you can build a Markov chain whose stationary distribution is the distribution you want to sample, then walking the chain long enough produces samples from it (sampling methods).

Beyond Markov chains

Other stochastic processes fill out the picture: a random walk taken to its continuous limit is Brownian motion (the Wiener process); a Poisson process models the timing of independent events; a Gaussian process is a distribution over entire functions. They share the theme — structure plus randomness, evolving over an index.

In one breath

• A stochastic process {X_t} is a collection of random variables indexed by time — a random function whose trajectory differs every run.
• A Markov chain obeys the Markov property (next state depends only on the current one); a transition matrix P defines it, and a distribution evolves by p_{t+1} = p_t P.
• Run it long enough and it reaches a stationary distribution π with πP = π (left eigenvector, eigenvalue 1) — independent of the start (the demo: [1,0] → [0.83, 0.17]).
• That convergence is the engine of MCMC — build a chain whose stationary distribution is your target, then walk it.
• Other processes: Brownian motion (continuous random walk), Poisson (event timing), Gaussian processes (distributions over functions); they underpin diffusion (forward noising), RL (MDPs), and time series.

Practice

A question to carry forward

A Markov chain slipped a new kind of question past us. The state now and the state next are not independent — they are linked by the transition matrix; knowing one shifts the odds on the other. Lift that idea clear out of time and make it general: take any two random quantities at all — a user’s age and their spend, two stock prices, two columns of a dataset — how tightly are they tied? Do they rise and fall together, pull in opposite directions, or drift along unrelated?

Here is the thread onward: what single number, covariance, captures whether two variables move together; why does its rescaled cousin correlation sit cleanly in [−1, 1] so you can compare relationships across wildly different units; and why is the matrix of all pairwise covariances the quiet object that PCA, the multivariate Gaussian, and a great deal of classical statistics are secretly built upon?