Random Walks

The Simplest Stochastic Process

A simple symmetric random walk is $S_n = S_0 + X_1 + \cdots + X_n$, where each $X_i = +1$ or $-1$ with equal probability. Despite its simplicity, it captures the essence of randomness in finance and is the building block for Brownian motion.

Key Properties

For a walk starting at $S_0 = 0$:

$E[S_n] = 0, \qquad \text{Var}(S_n) = n.$

The expected position never changes (it's a martingale), but the spread grows as $\sqrt{n}$.

Recurrence

By Pólya's theorem, a symmetric random walk in 1D and 2D returns to the origin with probability 1 (recurrent), but in 3D and higher escapes to infinity (transient).

Gambler's Ruin

A gambler starts with $k and bets $1 per round on a fair game, stopping at $0 (ruin) or $n (target):

$P(\text{win}) = \frac{k}{n}.$

For a biased game ($p \ne 1/2$): $\displaystyle P(\text{win}) = \frac{1 - (q/p)^k}{1 - (q/p)^n}$ where $q = 1 - p$.

Interview tip: Gambler's ruin is one of the most asked probability questions at trading firms. Know both formulas cold.

Worked Example

Starting at 0, what is the probability a symmetric walk reaches $+5$ before $-3$?

This is gambler's ruin with $k = 3$ (distance from lower barrier) and $n = 8$ (total gap):

$P = \frac{3}{8} = 0.375.$

Connection to Brownian Motion

Rescale steps to size $1/\sqrt{n}$ at intervals $1/n$; as $n \to \infty$, the walk converges to Brownian motion (Donsker's theorem). Every BM property has a discrete random walk analog.