Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 36 · Random Walks and Brownian Motion

The Simple Random Walk

Meet the simple random walk: its mean and variance, how far it wanders, the exact probability of returning to zero, and why dimension decides recurrence.

A random walk is the cleanest model of accumulated randomness. Start at 0. At each step, flip a coin: move one unit up on heads, one unit down on tails. Where are you after 100 steps? How often do you return to the start? These questions look like a game, but the same mathematics describes diffusing particles, the position of a drunk walker, and the daily wiggles of a price, and it leads directly to Brownian motion.

Definition

Let ξ₁, ξ₂, … be independent steps with P(ξ = +1) = p and P(ξ = -1) = q = 1 - p. The simple random walk is

Text
S_0 = 0,    S_n = ξ_1 + ξ_2 + ... + ξ_n

When p = 1/2 the walk is symmetric (fair). Each step has mean E[ξ] = p - q and variance 1 - (p - q)², so for the symmetric walk:

Text
E[S_n] = 0,        Var[S_n] = n,        SD[S_n] = √n

Two lessons hide here. The walk has no drift, yet its typical distance from the start grows like √n, not like n. A walk of 10,000 steps is typically about 100 away from the origin, not 10,000.

The walk is also a Markov chain on the integers, with independent, stationary increments: the discrete cousin of a Poisson process.

Simulating paths

Python Paths of a symmetric random 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.

The dashed curves mark one standard deviation. Roughly two thirds of paths should be inside them at any fixed n, but paths cross the envelope often, since the envelope is not a barrier.

Python Mean and variance of S_n

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.

With p = 0.6 the walk drifts upward by 0.2 per step on average, and the variance per step shrinks to 1 - 0.04 = 0.96.

The exact distribution

After n steps with k up-moves, the position is 2k - n. So S_n has the distribution of 2·Binomial(n, p) - n. For the symmetric walk:

Text
P(S_n = 2k - n) = C(n, k) / 2^n

In particular S_n has the same parity as n: after an odd number of steps it cannot be 0. For large n the central limit theorem gives S_n ≈ Normal(0, n).

Returns to the origin

The walk is at 0 after 2n steps with probability

Text
u_{2n} = P(S_{2n} = 0) = C(2n, n) / 4^n  ≈  1 / √(π n)

(by Stirling's formula). The expected number of returns is Σ u_{2n}, and since 1/√n has an infinite sum, the symmetric walk in one dimension is recurrent: it returns to 0 infinitely often, with probability 1.

Python Return probabilities: exact versus asymptotic

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 expected number of returns keeps growing roughly like (2/√π)√n, never levelling off, which is the numerical face of recurrence.

Dimension matters

On the 2D grid (moving one of four neighbors at random) the walk is still recurrent, but in three or more dimensions it is transient: Pólya's theorem. In 3D the probability of ever returning to the origin is only about 0.34, so a walker has a decent chance of escaping forever. A popular summary: a drunk man will eventually find his way home, but a drunk bird may not.

The √n scaling is the signature of diffusion. If an experiment shows distances growing in proportion to √t, the underlying motion is random-walk-like. Distances growing in proportion to t mean steady drift.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A symmetric simple random walk takes 900 steps. What is the standard deviation of S_900?

    Var S_n = n = 900, so the standard deviation is √900 = 30.
  2. 2. Can a symmetric simple random walk be at position 0 after exactly 7 steps?

    Each step changes parity, so S_7 is odd and cannot be 0.
  3. 3. With p = 0.7, what is E[S_n]?

    E[ξ] = p - q = 0.7 - 0.3 = 0.4, so E[S_n] = 0.4 n.
  4. 4. In which dimension is the simple symmetric random walk transient?

    Pólya: recurrent in dimensions 1 and 2, transient in 3 and higher.

Summary

  • Sₙ = ξ₁ + … + ξₙ with ±1 steps; symmetric case has mean 0 and variance n.
  • Typical distance from the origin grows like √n; with drift p - q it grows linearly.
  • P(S_{2n} = 0) = C(2n, n)/4ⁿ ≈ 1/√(πn); the 1D walk is recurrent.
  • Pólya: the walk is recurrent in 1D and 2D, transient in 3D and higher.

Next: Gambler's Ruin