Random walks · Probability & Statistics

A random walk is the sum of independent random steps:

$S_n = X_1 + X_2 + \cdots + X_n, \qquad S_0 = 0$

It's the simplest process that moves, and despite that simplicity its behaviour is repeatedly counter-intuitive. It's also the discrete ancestor of Brownian motion, which is the next lesson.

The simple random walk

Take X_i = \pm 1 with probability 1/2 each. Then

$E[S_n] = 0, \qquad \operatorname{Var}(S_n) = n, \qquad \operatorname{SD}(S_n) = \sqrt n$

The expectation stays at zero — the walk has no drift. But the spread grows like \sqrt n, so the walk wanders further and further from the origin even though its average position never moves.

That \sqrt n is the same one from §3's standard error, and for the same reason: variances of independent steps add, so standard deviations grow as the square root.

Typical distance after n steps is about \sqrt n. After 10,000 steps you are typically 100 away from where you started, not near zero.

By the CLT (§3), for large n:

$\frac{S_n}{\sqrt n} \;\xrightarrow{d}\; N(0, 1)$

Recurrence: the dimension result

Does the walk return to its starting point?

In one dimension, yes — with probability 1. And in two dimensions, also with probability 1. But in three dimensions or more, the probability is strictly less than 1: about 0.34 in 3-D.

Pólya's theorem, memorably summarised by Kakutani: a drunk man will find his way home, but a drunk bird may not.

The intuition: in low dimensions there just aren't many places to be, so the walk keeps stumbling back over its own territory. In three dimensions there's enough room to wander off and never come back.

A crucial qualifier. "Returns with probability 1" does not mean it returns quickly. In 1-D the expected time to return is infinite. The walk is recurrent but null recurrent — it always comes back, but the average wait is unbounded. Both facts are true simultaneously, which takes some getting used to.

The arcsine laws — where intuition fails hardest

Consider a fair coin-flipping game where you track your cumulative winnings over n flips. Two natural questions:

How much of the time are you ahead? Intuition says "about half". The truth is that the fraction of time spent positive follows the arcsine distribution, whose density is U-shaped:

$f(x) = \frac{1}{\pi\sqrt{x(1-x)}}, \qquad 0 < x < 1$

The most likely outcomes are spending almost all the time ahead, or almost all the time behind. Splitting the time near-evenly is the least likely outcome.

When does the walk last cross zero? Also arcsine — so the last tie is most likely to occur very near the start or very near the end, rarely in the middle.

Why this matters. In a fair game, one player typically leads for most of it. That is not evidence of skill, momentum, or a "hot hand" — it is what fairness looks like. The same reasoning applies to fund managers beating an index and to teams on winning streaks.

Variations

With drift. If E[X_i] = \mu \ne 0:

$E[S_n] = n\mu, \qquad \operatorname{Var}(S_n) = n\sigma^2$

The drift grows like n while the noise grows like \sqrt n, so drift eventually dominates — a walk with any positive drift escapes to +\infty with probability 1.

Gambler's ruin. Start at k, with absorbing barriers at 0 and N. For a fair walk, the probability of reaching N before 0 is exactly k/N, and the expected duration is k(N-k).

Against an opponent with much deeper pockets, ruin is nearly certain even in a perfectly fair game — which is the mathematical core of why bankroll matters more than edge.

Multiplicative walks. If each step multiplies rather than adds, take logs and you have an ordinary random walk. That's the standard model for asset prices, and it's why log-returns are the quantity people model.

Worked example

A gambler starts with ₹10, bets ₹1 on fair coin flips, and stops at ₹0 or ₹25. What's the probability of reaching ₹25?

This is gambler's ruin with k = 10, N = 25:

$P(\text{reach } N) = \frac{k}{N} = \frac{10}{25} = 0.4$

Expected number of bets:

$E[\text{duration}] = k(N - k) = 10 \times 15 = 150$

Both results are worth pausing on.

The 40% is exactly the fair-odds answer — the game is fair, so the expected final wealth must equal the starting wealth: 0.4(25) + 0.6(0) = 10. ✓ No edge exists in either direction.

But 150 bets is a long time to reach a decision. The walk wanders extensively before absorption, which is the \sqrt n spread at work.

Now make the game slightly unfair — say a 49% chance of winning each bet, roughly a casino's edge. The probability of reaching ₹25 drops from 40% to 28.6%, a reduction of more than a quarter. Drop to 45% per bet and it collapses to 4.3%.

A 1% disadvantage per bet compounds so sharply because the drift term grows like n while the fluctuations that might rescue you only grow like \sqrt n. Over the ~150 bets this game takes, the edge has time to assert itself and the noise does not.

Doing it in Python

The \sqrt n growth, measured:

import numpy as np

rng = np.random.default_rng(0)
trials = 50_000

print(f"{'n':>8} {'E[S_n]':>10} {'SD(S_n)':>10} {'sqrt(n)':>10} {'E|S_n|':>10}")
for n in (10, 100, 1_000, 10_000):
    steps = rng.choice([-1, 1], size=(trials, n))
    S = steps.sum(axis=1)
    print(f"{n:>8} {S.mean():>10.3f} {S.std():>10.3f} {np.sqrt(n):>10.3f} "
          f"{np.abs(S).mean():>10.3f}")

print("\nThe mean stays at 0; the spread grows like sqrt(n).")
print("Typical DISTANCE from the origin grows without bound.")

The arcsine law — the result that most contradicts intuition:

import numpy as np

rng = np.random.default_rng(1)
trials, n = 100_000, 1_000

steps = rng.choice([-1, 1], size=(trials, n))
paths = np.cumsum(steps, axis=1)
frac_positive = (paths > 0).mean(axis=1)

print("Fraction of time spent AHEAD in a fair game:\n")
bins = [0, 0.1, 0.25, 0.4, 0.6, 0.75, 0.9, 1.0]
for lo, hi in zip(bins[:-1], bins[1:]):
    share = ((frac_positive >= lo) & (frac_positive < hi)).mean()
    print(f"  {lo:.2f}-{hi:.2f}: {share:.4f}  {'#' * int(share * 200)}")

print(f"\nnear the extremes (<10% or >90% of the time): "
      f"{((frac_positive < 0.1) | (frac_positive > 0.9)).mean():.4f}")
print(f"near even (40-60% of the time)               : "
      f"{((frac_positive >= 0.4) & (frac_positive < 0.6)).mean():.4f}")
print("\nU-shaped: dominating or being dominated is far more likely than a")
print("close-run game. In a FAIR game.")

Gambler's ruin, fair and slightly unfair:

import numpy as np

rng = np.random.default_rng(2)

def ruin(start, target, p_win, trials, rng):
    wins, steps_taken = 0, []
    for _ in range(trials):
        k, n = start, 0
        while 0 < k < target:
            k += 1 if rng.random() < p_win else -1
            n += 1
        wins += (k == target)
        steps_taken.append(n)
    return wins / trials, np.mean(steps_taken)

start, target = 10, 25
for p in (0.50, 0.49, 0.45):
    prob, dur = ruin(start, target, p, 3_000, rng)
    theory = (start / target if p == 0.5 else
              (1 - ((1-p)/p) ** start) / (1 - ((1-p)/p) ** target))
    print(f"p(win each bet) = {p}: P(reach {target}) = {prob:.4f} "
          f"(theory {theory:.4f})   mean duration {dur:.0f}")

print("\nA 1% edge against you cuts the chance of success by more than half.")

Recurrence by dimension — Pólya's theorem, simulated:

import numpy as np

rng = np.random.default_rng(3)

def returns_to_origin(dim, max_steps, trials, rng):
    hits = 0
    for _ in range(trials):
        pos = np.zeros(dim, dtype=int)
        for _ in range(max_steps):
            axis = rng.integers(dim)
            pos[axis] += rng.choice([-1, 1])
            if not pos.any():
                hits += 1
                break
    return hits / trials

for dim in (1, 2, 3):
    rate = returns_to_origin(dim, 2_000, 2_000, rng)
    print(f"{dim}-D: returned to origin within 2000 steps in {rate:.4f} of runs")

print("\n1-D and 2-D return with probability 1 (given unlimited time).")
print("3-D returns only about 34% of the time, however long you wait.")

Your turn

1. After 100 steps of a simple random walk, what are E[S_{100}] and \operatorname{SD}(S_{100})?

2. You're up ₹50 after 1,000 fair coin flips. Is that surprising?

3. A gambler with ₹100 plays against a casino with effectively unlimited money, at fair odds. What's the probability of eventual ruin?

Solutions

$E[S_{100}] = 0, \qquad \operatorname{SD}(S_{100}) = \sqrt{100} = 10$

So the walk is typically about 10 steps from the origin — and by the CLT, roughly 95% of the time it lands within \pm 20.

2. Not at all. The standard deviation after 1,000 flips is \sqrt{1000} \approx 31.6, so ₹50 is about 50/31.6 \approx 1.58 standard deviations from zero.

$P(|S_{1000}| \ge 50) \approx 2(1 - \Phi(1.58)) \approx 0.114$

An 11% event — entirely ordinary. Being up ₹50 is weaker evidence of a biased coin than most people's intuition suggests, because intuition tends to anchor on "should be near zero" and forget that the spread grows.

3. Ruin is certain — probability 1.

Take the gambler's ruin formula k/N and let N \to \infty with k = 100 fixed:

$P(\text{reach } N) = \frac{100}{N} \to 0$

so P(\text{ruin}) \to 1.

The reason is recurrence. A 1-D random walk returns to every level with probability 1, given enough time — including the level "zero rupees", which is absorbing. The gambler has a finite barrier and the casino effectively doesn't, so only one of them can be wiped out.

Note the game is fair: the expected value of each bet is zero, and the gambler's expected wealth stays at ₹100 at every finite time. Ruin is certain and the game is fair, simultaneously. The resolution is that the tiny probability of enormous winnings exactly balances the near-certainty of losing everything — the expectation is carried by outcomes that essentially never happen.

This is also why the martingale doubling strategy fails (next lesson but one), and why bankroll management dominates edge in practice.

Check yourself in code

Confirm the \sqrt n growth of a simple random walk and measure the arcsine law's U shape.

Print exactly this:

SD at n=10000 100.58
sqrt(n) 100.0
ratio close to 1: True
extreme time fraction 0.409
near-even fraction 0.1269
U-shaped: True

Use default_rng(0) with 20000 trials of 10000 steps for the first part, and default_rng(1) with 100000 trials of 1000 steps for the arcsine part. Round the SD to 2 decimal places and the fractions to 4. "Extreme" means the walk is positive less than 10% or more than 90% of the time; "near-even" means between 40% and 60%.

import numpy as np

rng = np.random.default_rng(0)
n = 10_000
S = rng.choice([-1, 1], size=(20_000, n)).sum(axis=1)

print("SD at n=10000", round(S.std(), 2))
print("sqrt(n)", round(float(np.sqrt(n)), 2))
print("ratio close to 1:", bool(abs(S.std() / np.sqrt(n) - 1) < 0.05))

# With default_rng(1), simulate 100000 walks of 1000 steps, compute the
# fraction of time each spends positive, and report the extreme and
# near-even shares plus whether extreme > near-even.

import numpy as np

rng = np.random.default_rng(0)
n = 10_000
S = rng.choice([-1, 1], size=(20_000, n)).sum(axis=1)

print("SD at n=10000", round(S.std(), 2))
print("sqrt(n)", round(float(np.sqrt(n)), 2))
print("ratio close to 1:", bool(abs(S.std() / np.sqrt(n) - 1) < 0.05))

rng2 = np.random.default_rng(1)
paths = np.cumsum(rng2.choice([-1, 1], size=(100_000, 1_000)), axis=1)
frac = (paths > 0).mean(axis=1)

extreme = ((frac < 0.1) | (frac > 0.9)).mean()
near_even = ((frac >= 0.4) & (frac < 0.6)).mean()
print("extreme time fraction", round(extreme, 4))
print("near-even fraction", round(near_even, 4))
print("U-shaped:", bool(extreme > near_even))

A random walk has zero drift but a spread growing like \sqrt n, so it wanders ever further while its mean stays put. It returns to the origin with probability 1 in one and two dimensions but not in three, and even when return is certain the expected wait is infinite. The arcsine laws say a fair game usually looks lopsided — which is worth remembering before attributing a long lead to skill.

Next: what happens when the steps become infinitely small and infinitely frequent.

52. Random walks