insideout Get Pro

11 · Random walks

Pro

Probability, lesson 11

Random walks

Gambler's ruin, hitting times, and how far a random path wanders.

Bet 1 chip at a time and your pile moves up or down one step per bet. That path is a random walk, and the same maths describes prices and risk limits. You need the square root rule from the lesson on variance, and fair games from the last lesson.

By the end, you can:

  1. Work out how far a random walk typically gets in n steps.
  2. Find the chance a walk reaches one wall before the other.
  3. Work out how many steps a walk takes, on average, to hit a wall.

Part 1. How far a walk wanders

Work out how far a random walk typically gets in n steps.

Flip a fair coin and take a step: up 1 for heads, down 1 for tails. Every step averages zero, so on average you go nowhere. But any one walk does go somewhere. The question is how far, and the square root rule answers it.

Example 1.1

400 coin-flip steps

A walk takes 400 steps, each +1 or −1 on a fair coin. How far from the start does it typically end?

  1. Mean of one step(+1 − 1) / 2 = 0

    Up and down are equally likely.

  2. Variance of one step(1² + (−1)²) / 2 − 0² = 1

    The average square minus the square of the average. Every step squares to 1.

  3. Add 400 independent stepsvariance 400, σ = √400 = 20

    Variances add, so the spread grows like √n.

AnswerAbout 20 from the start, either way. About 95% of walks end within 40.

Steps cancel. Of 400 flips, about 200 come up heads, and where the walk ends is just the gap between heads and tails. That gap is the noise left after the cancelling, and it grows only like √n. Turned around: to wander a distance d, a walk needs about d² steps.

Random walk

A random walk is a path built by adding up independent random steps. After n steps of +1 or −1 on a fair coin, its position has mean 0 and standard deviation √n.

σ after n steps = √n

Six walks of 400 steps +40 0 −40 0 200 400 steps +2√n −2√n
Six walks of 400 steps +40 0 −40 0 200 400 steps +2√n −2√n
Figure 1Six simulated walks of 400 steps. They fan out like √n: the dashed curves, 2√n either side, reach ±40 at step 400. The orange walk ends at 36.

The average end is 0, yet a walk is back at exactly 0 after 400 steps only about 4% of the time. A small drift hides for a long time, too: at 51% heads, a walk drifts 0.02 a step, just 8 after 400 steps, well inside a spread of 20.

Your turn

After 10,000 steps of ±1, a typical distance from the start is about:

√10,000 = 100. A walk gets far less distance than it takes steps, because steps cancel each other. 0 is where walks end on average, not how far a typical one gets.

Part 2. Gambler's ruin

Find the chance a walk reaches one wall before the other.

Keep going with Pro

You've done the first part. Pro opens the rest of this lesson, and every other one.

Still to come
  1. Gambler's ruin
  2. How long until it hits
See Pro plansI have Pro: sign in
Next lessonInterview puzzles, workedClassic interview puzzles, solved step by step. Start lesson 12

Probability overviewSpotted a mistake? Tell us.