Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 38 · Simulation of Systems

Simulating Random Walks

Simulate random walks, measure how far they wander, and test when they return home. A first model of a system built from random steps.

So far you have estimated numbers: an integral, a probability, an expectation. Now we simulate systems, things that evolve over time through random events. The simplest system is a random walk: a point that takes a random step, then another, then another. It models a gas molecule bumping around, a stock price wobbling, a drunk person leaving a bar, or the position of a gambler's fortune.

Random walks are both a useful model and a training ground. They show how to simulate many independent trajectories at once with array operations, and how to read a property of the system (how far it wanders, whether it comes back) off the simulated paths.

The one-dimensional walk

Start at 0. At each step move +1 or −1, each with probability 1/2. After n steps the position is the sum of n independent steps S_n = X₁ + … + X_n, each with mean 0 and variance 1. So:

Text
E[S_n] = 0            Var(S_n) = n            E[S_n²] = n

The typical distance from the start grows like √n, not like n: doubling the time multiplies the typical displacement by only √2 ≈ 1.41. By the central limit theorem, S_n/√n is approximately standard normal for large n. This square-root law is the signature of diffusion.

Python Mean squared displacement of a 1-D walk

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All 5,000 paths are generated in one array operation; each row is a walk. This "vectorize across trials" habit makes Python simulations hundreds of times faster than writing loops.

Walks in the plane

In two dimensions, at each step choose one of the four neighbors (up, down, left, right) with probability 1/4. The squared distance from the origin still satisfies E[R_n²] = n, because every step has length 1 and the steps are uncorrelated.

Python Plot a few 2-D random walks

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The walks look like tangled rope: they revisit regions many times and drift away only slowly, which is what diffusion looks like.

Do they come back? Dimensions 1, 2 and 3

A beautiful result by George Pólya (1921): a simple symmetric random walk on the integer lattice returns to its starting point with probability 1 in one and two dimensions, but in three dimensions it returns with probability only about 0.34 (0.3405), and may wander off forever. As a saying goes, a drunk man will eventually find his way home, but a drunk bird may be lost forever.

Simulation can show the trend, but never the exact value: a computer can only run finitely many steps. So we measure the chance of returning within a fixed number of steps and watch how the dimensions differ.

Python Return probability within 1000 steps, in 1, 2 and 3 dimensions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In d = 1 and d = 2 the fractions keep creeping toward 1 as you allow more steps, but slowly (especially in 2-D). In d = 3 the curve flattens below 0.34.

A fixed number of steps cannot prove "returns with probability 1". A simulation gives evidence and intuition; the proof is a calculation with the number of paths that return to the origin.

What walks teach us about simulation

  • Vectorize across trials: each row of an array is an independent run.
  • Record what you need: paths for plots, just final values for statistics, to save memory.
  • Compare with theory when you can: E[S_n²] = n gave us a built-in check.
  • Extend easily: bias the steps, add boundaries (gambler's ruin), or let steps have random lengths; the same code structure works.

Random walks also underlie Brownian motion, which you will use for option pricing and diffusion.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. After n steps of a symmetric +1/-1 walk, E[S_n^2] equals:

    Steps are independent with mean 0 and variance 1, so Var(S_n) = n and E[S_n^2] = n.
  2. 2. Doubling the number of steps multiplies the typical distance by about:

    Typical distance is proportional to the square root of n.
  3. 3. Polya's theorem says a simple random walk on the lattice returns to the origin with probability 1 in:

    In three or more dimensions the return probability is less than 1 (about 0.34 in 3-D).
  4. 4. Why simulate many walks as rows of one array?

    Vectorization lets NumPy do the work for all trials at once.

Summary

  • A random walk adds independent random steps; Var(S_n) = n, so distance grows like √n.
  • Simulate many walks at once with array operations, one row per walk.
  • Walks return home with probability 1 in 1-D and 2-D, but only about 0.34 in 3-D (Pólya).
  • Finite simulations give evidence and intuition; theory supplies exact values to check against.

Next: Simulating a Queue