less code, more software: Feller's walk

Feller's walk

Image you have a fair coin, and you flip it 1000 times, adding 1 or subtracting 1 each time you flip either a head or a tail respectively. How do you think the cumulative total will behave as the number of coin flips progresses from 1 to 1000?

Don Reinersten poses this question in his excellent book the Principles of product development FLOW. Don read it in William Feller's book An introduction to probability theory and its applications.

Feller says most people, even trained mathematicians and statisticians, assume that the cumulative total will hover around zero. It doesn't. It tends to drift further and further above or below zero. In fact, there is only a 50% chance the cumulative total will cross the zero line in the second 500 flips! Intrigued by this I've written a short javascript program to simulate 5000 walks and plot two graphs (using the jQuery flot library). You can grab my code from github if you're interested.

The first graph plots the cumulative total on a single walk.

Y-axis is cumulative total, marked -40,-20,0,20,40
X-axis is walk step, marked 0,100,200,...,900,1000

The walk plotted above is fairly typical - it drifts down and ends with a cumulative total of about Y=-42 at X=1000.

The second graph plots the probabilities for the cumulative total after N flips at

N=10 (orange line)
N=30 (blue line)
N=100 (red line)
N=1000 (green line)

Y-axis is probability, marked 0.00, 0.05, 0.10, 0.15, 0.20, 0.25
X-axis is cumulative total, marked -125,-100,-75,-50,-25,0,25,50,75,100,125

The most probable value for the cumulative total is always zero, but this probability gets lower and lower as N increases. After 1000 flips of a fair coin, there's only about a 1 in 50 chance the cumulative total will be zero. I find that pretty amazing. Without constraints variance will accumulate. As Don says