Random Walks — Mathematics Knowledge System

Overview

A random walk is a stochastic process formed by summing independent random steps. The simple symmetric random walk on Z takes steps +1 or -1 with probability 1/2 each. Random walks are the discrete analog of Brownian motion (Donsker's theorem) and exhibit rich phenomena: recurrence in dimensions d <= 2 and transience in d >= 3, the reflection principle, the ballot problem, and the gambler's ruin. They are fundamental in combinatorics, finance, physics, and the analysis of algorithms.

Intuition

A random walk is the simplest model of cumulative uncertainty: each step adds a random increment. In 1D, the walk is recurrent -- it will return to the origin infinitely often with probability 1 (though the expected return time is infinite). The reflection principle provides a beautiful symmetry: paths that reach a high level can be reflected to give a bijection with paths ending at a different level, enabling exact computation of probabilities for maxima and first-passage times. The ballot problem asks: in an election, what is the probability that the winner is always ahead?

Formal Definition

Definition

A simple symmetric random walk on Z is defined by i.i.d. steps with equal probability of +1 and -1.

S_0 = 0, \quad S_n = X_1 + \cdots + X_n, \quad X_i \overset{\text{i.i.d.}}{\sim} P(X_i=+1)=P(X_i=-1)=\tfrac{1}{2}

Simple symmetric random walk

P(S_{2n}=0) = \binom{2n}{n}\frac{1}{4^n} \sim \frac{1}{\sqrt{\pi n}} \quad \text{(Stirling)}

Return to origin probability

P\!\left(\max_{0 \le k \le n} S_k \ge a\right) = P(S_n \ge a) + P(S_n > a) \approx 2P(S_n \ge a)

Reflection principle (discrete)

P(S_1>0, S_2>0,\ldots,S_{2n}>0) = P(S_{2n}=0) = \binom{2n}{n}\frac{1}{4^n}

Arc-sine law

Notation

Notation	Meaning
$S_n$	Position after n steps
$T_a$	First passage time to level a: T_a = min{n: S_n = a}
$p_k$	Probability of reaching N before 0 starting from k (gambler's ruin)

Theorems

Theorem 1: Polya's Recurrence Theorem

\text{The simple symmetric random walk on } \mathbb{Z}^d \text{ is recurrent (returns to origin with probability 1) if } d \le 2 \text{, and transient (escapes to infinity with probability 1) if } d \ge 3.

Theorem 2: Reflection Principle (Discrete)

P\!\left(\max_{0 \le k \le n} S_k \ge a\right) = P(S_n \ge a) + P(S_n > a) = 2P(S_n \ge a) - P(S_n = a) \text{ for integer } a > 0.

Theorem 3: Ballot Problem

\text{In an election where candidate A gets } a \text{ votes and B gets } b < a \text{ votes, the probability that A is strictly ahead throughout the counting is:} \quad P = \frac{a-b}{a+b}.

Worked Examples

1
The first return to 0 at time 2n requires the walk to stay positive (or negative) for steps 1 through 2n-1. This probability is u_{2n} = P(first return at 2n).
$u_{2n} = \frac{1}{2n-1}\binom{2n}{n}\frac{1}{4^n} = \frac{1}{2n-1} P(S_{2n}=0)$
2
Alternatively, u_{2n} = (1/(2n-1)) P(S_{2n} = 0) ~ 1/(2 sqrt(pi) n^{3/2}) by Stirling's approximation.
$u_{2n} \sim \frac{1}{2\sqrt{\pi}\, n^{3/2}}$

✓ Answer

P(first return at time 2n) = C(2n,n)/(2n-1) / 4^n, which decays like 1/n^{3/2}.

Practice Problems

Easyfree response

In a fair coin-flipping game, what is the probability that a walk starting at position 2 reaches 5 before reaching 0?

Mediumapplication

Explain the arc-sine law for random walks: what does it say about the fraction of time a random walk spends positive?

Common Mistakes

Common Mistake

A fair coin-flip game must spend roughly equal time above and below 0

The arc-sine law shows the opposite: most paths spend almost all their time on one side. A fair game is extremely lopsided in the short run.

Common Mistake

A random walk in 3D will eventually return to the origin

By Polya's theorem, the simple random walk in d >= 3 is transient: it escapes to infinity and returns to the origin with probability less than 1.

Quiz

Historical Background

Karl Pearson coined the term 'random walk' in 1905 in a letter to Nature, asking about a man who takes steps of unit length in a random direction. The problem was immediately solved by Lord Rayleigh. The 1D discrete random walk had been studied earlier in the gambler's ruin context. George Polya proved in 1921 that the simple random walk is recurrent in dimensions 1 and 2 but transient in dimension 3 and above, a result of deep importance. The connection to Brownian motion via Donsker's invariance principle was established in the 1950s.

1905
Pearson coins the term 'random walk'; Rayleigh solves the 2D version
Karl Pearson, Lord Rayleigh
1921
Polya proves recurrence in d <= 2 and transience in d >= 3
George Polya
1951
Donsker proves the invariance principle: scaled random walks converge to Brownian motion
Monroe Donsker

Summary

A simple symmetric random walk takes +1/-1 steps with equal probability; it is the discrete precursor to Brownian motion.
Polya's recurrence theorem: random walk is recurrent in d <= 2 (returns infinitely often) and transient in d >= 3.
The reflection principle computes maxima and first-passage distributions by establishing bijections between path classes.
Ballot problem: P(A always leads) = (a-b)/(a+b); gambler's ruin: P(reach N starting at k) = k/N.

References

BookDurrett, R. -- Probability: Theory and Examples, 4th ed., Chapter 3
BookRoss, S. -- Introduction to Probability Models
WebsiteWikipedia -- Random walk