Random Walks

Processes built from repeated random steps, modeled with transition matrices, absorbing boundaries, and diffusion-like spread.

Simple random walk: each step is +1 or -1 with probability 1/2

Individual paths wiggle, but after many steps the endpoints cluster near the center and spread out like the square root of time.

Definition

A random walk is a process that moves by taking random steps. The simplest version starts at position $X_0 = 0$ and, at each time step, moves either $+1$ or $-1$ :

$X_{t+1} = X_t + \xi_{t+1}, \qquad P(\xi_{t+1}=1)=P(\xi_{t+1}=-1)=\frac12$

The individual steps are unpredictable, but the distribution of the position becomes predictable. After many steps, most paths remain near $0$ , while a few wander far away. That is the central tension: random locally, structured statistically.

Gambler's ruin

A gambler starts with $10$ dollars and repeatedly bets $1$ dollar on a fair coin. Heads increases their money by $1$ ; tails decreases it by $1$ . The game stops at $0$ dollars or $20$ dollars. This is a random walk with absorbing boundaries.

By symmetry, starting at $10$ gives a $50\%$ chance of reaching $20$ before $0$ . Starting at $i$ dollars gives probability $\frac{i}{20}$ of reaching $20$ first.

Try it

In a fair random walk, why is $E[X_t] = 0$ for every $t$ ?

Solution

Each step has expected value $E[\xi_i] = 1\cdot\frac12 + (-1)\cdot\frac12 = 0$ . Since $X_t = \xi_1 + \cdots + \xi_t$ , linearity of expectation gives

$E[X_t] = E[\xi_1] + \cdots + E[\xi_t] = 0.$

The walk spreads out over time, but it does not drift upward or downward on average.

Related concepts

Needs first

Law of Large Numbers Probability

Graph Theory Basics Markov Chains Markov Chain Monte Carlo

View in full concept graph →