Simulating a Random Walk

A walk made of coin tosses

A random walk is one of the simplest ideas in probability, and one of the most revealing. Start at zero. Toss a fair coin. If it lands heads, add 1 to your total; if tails, subtract 1. Repeat. The sequence of running totals is a random walk.

You can think of it as a score in a game where each round is a fair coin toss and you win or lose one point. At every step the chance of going up is exactly the chance of going down, so it might seem the total should hover around zero. In a sense it does, on average, but individual walks behave very differently from that picture.

A short program

In Python:

import random

def random_walk(steps):
    position = 0
    path = [position]
    for _ in range(steps):
        position += random.choice([-1, 1])
        path.append(position)
    return path

path = random_walk(1000)
print("final position:", path[-1])
print("highest:", max(path), "lowest:", min(path))
print("steps spent above zero:", sum(1 for x in path if x > 0))

Run it a few times. The final positions will differ a lot from run to run, and some walks spend almost the entire time on one side of zero.

Two different questions about the average

It helps to separate two ideas that are easy to blur.

First, the expected position after any number of steps is zero. Each step has an average of zero, and averages add up, so the average of the total is zero. If you ran thousands of walks and averaged their final positions, the result would be close to zero.

Second, the typical distance from zero is not zero at all. After n steps, the standard deviation of the position is the square root of n. For example:

So after 10,000 tosses, a typical walk ends up on the order of 100 away from zero, in one direction or the other. That is a long way from the intuitive picture of staying near even, though it is small compared with 10,000.

How this fits the law of large numbers

The law of large numbers is about the average per step, which is the position divided by the number of steps. That does shrink toward zero: 100 out of 10,000 steps is only 1%. But the absolute gap between heads and tails keeps growing, roughly like the square root of the steps.

Both statements are true together. The share of heads tends toward one half, while the count of heads minus tails typically drifts further away. People who expect the gap to correct itself are making the gambler’s fallacy: the coin has no memory, and a run of extra heads is not “paid back” by later tails. The gap simply becomes smaller relative to the total.

What walks look like

Simulating many walks reveals some features that surprise people:

• Long stretches on one side. A walk often stays above zero, or below zero, for most of its length. Spending about half the time on each side is actually not the most common outcome.
• Wide spread. If you plot several walks on the same chart, they fan out like a widening cone whose width grows with the square root of the steps.
• Returns to zero can be slow. The walk does tend to come back to zero eventually in the one-dimensional case, but the waiting time can be very long.
• Apparent trends. Because each path is a running total, it can look like it has momentum, even though every step is independent.

This is one reason random streaks and runs in a sequence can look meaningful when they are not. Coin toss streaks of a given length are normal in a long sequence.

Checking the square root claim yourself

You can test the table above with a simulation. Run, say, 5,000 walks of 100 steps each and record the final position of each. Then compute the standard deviation of those 5,000 numbers. It should come out close to 10, with a little random variation because 5,000 is a finite sample.

Then repeat with 400 steps. The standard deviation should be close to 20, since the square root of 400 is 20. Quadrupling the steps doubles the typical distance, which is a pattern worth seeing with your own results.

A histogram of the final positions will look like a bell curve centred on zero. That is the normal distribution appearing as a sum of many small independent steps.

Variations

• Biased steps. Let the walk go up with probability 0.51 instead of 0.5. The expected position now drifts steadily upward by 0.02 per step on average, but over a short run the random wandering can easily dominate the drift.
• Boundaries. Stop the walk if it hits a limit, such as zero. This models a finite pile of points running out, and it is the idea behind gamblers ruin.
• Bigger steps. Use steps drawn from a dice roll rather than plus or minus one.

Cautions

A random walk is a model, not a prediction of anything. In games with a house edge, the real step is biased against the player, so the walk drifts downward over time, with random fluctuation on top. Short-run results can be far from the long-run average, and that variation is not a signal or a system. Gambling can be harmful, and anyone worried about their play can reach out to a local support service.