Random Walks

Coin-flip steps summed over time: mean 0, spread √n, exact odds by counting paths.

The idea

A random walk is the process formed by adding up independent random steps. It is the basic model for a quantity that moves by accumulating small, unpredictable changes: a gambler's bankroll hand after hand, a stock price tick by tick.

The simplest version is the simple symmetric walk. Start at $0$. At each step, move one unit up with probability $\frac{1}{2}$ or one unit down with probability $\frac{1}{2}$, each step independent of all the others. Writing $X_{i}$ for the $i$-th step, so that $X_{i} = \pm 1$ with probability $\frac{1}{2}$ each, the position after $n$ steps is

$S_{n} = X_{1} + X_{2} + \cdots + X_{n}.$

Since $S_{n}$ is a random variable, questions about the walk are questions about its distribution: its average position, its typical distance from the start, the exact probability that it finishes at a given point. Two facts answer all of them — the steps are independent, and every sequence of $n$ steps has the same probability $2^{-n}$.

Ways to work on it

• Walkthrough. Mean, variance, and parity of the simple symmetric walk, then exact probabilities by path counting.
• Practice. Probabilities, path counts, and spreads of the symmetric walk.
• Hardest. Exact endpoint probabilities for walks too long to enumerate, and the walk's mean squared displacement.

Not sure where to start? Take the ten-question placement test.