Step +1 or −1 with equal probability. In 1D and 2D, the walk returns to the origin infinitely often. In 3D and higher, it escapes forever. This dimension-dependent recurrence is one of the deepest results in probability.
Simple random walk
Start at 0. At each step, move +1 with probability p or −1 with probability 1 − p. The position after n steps is Sₙ = X₁ + … + Xₙ. For the symmetric walk (p = ½), E[Sₙ] = 0 and Var(Sₙ) = n.
Scheme
; Simple random walk: +1 or -1 with equal probability; Track returns to origin
(define *seed* 137)
(define (rand!)
(set! *seed* (modulo (+ (* 1103515245 *seed*) 12345) 2147483648))
*seed*)
(define (random-step) (if (< (modulo (rand!) 2) 1) 1-1))
(define (random-walk n)
(let loop ((i 0) (pos 0) (returns 0) (path '()))
(if (= i n)
(list (reverse path) returns)
(let* ((step (random-step))
(new-pos (+ pos step))
(new-ret (if (= new-pos 0) (+ returns 1) returns)))
(loop (+ i 1) new-pos new-ret (cons new-pos path))))))
(define result (random-walk 20))
(display "path: ") (display (car result)) (newline)
(display "returns: ") (display (cadr result)) (newline)
; Longer walk: more returns
(define result2 (random-walk 100))
(display "100 steps, returns: ") (display (cadr result2))
; In 1D, the walk returns to 0 infinitely often
A gambler starts with k dollars and bets $1 each round. The game ends when the gambler reaches 0 (ruin) or N (target). With a fair coin, the probability of ruin starting from k is (N − k)/N. With an unfair coin (p < ½), ruin is almost certain for large N.
Scheme
; Gambler's ruin: probability of ruin starting from k, target N; Fair game (p = 1/2): P(ruin from k) = (N - k) / N
(define (ruin-fair k N)
(/ (- N k) N))
(display "Fair game, k=3, N=10: P(ruin) = ")
(display (ruin-fair 310)) (newline)
; Unfair game (p != 1/2):; P(ruin from k) = (r^N - r^k) / (r^N - 1) where r = (1-p)/p
(define (ruin-unfair k N p)
(let ((r (/ (- 1 p) p)))
(/ (- (expt r N) (expt r k))
(- (expt r N) 1))))
(display "p=0.49, k=50, N=100: P(ruin) = ")
(display (ruin-unfair 501000.49)) (newline)
; Even slight disadvantage makes ruin very likely
(display "p=0.45, k=50, N=100: P(ruin) = ")
(display (ruin-unfair 501000.45)) (newline)
(display "p=0.51, k=50, N=100: P(ruin) = ")
(display (ruin-unfair 501000.51)) (newline)
; Slight advantage makes ruin unlikely
Recurrence and transience
A random walk is recurrent if it returns to the origin with probability 1. Pólya proved: the symmetric random walk is recurrent in 1D and 2D, but transient in 3D and higher. The probability of return in 3D is approximately 0.3405. A drunk person on a plane will find their way home. A drunk bird will not.
Scheme
; Polya's recurrence theorem; 1D: P(return) = 1 (recurrent); 2D: P(return) = 1 (recurrent); 3D: P(return) ~ 0.3405 (transient); In 1D, P(return to 0 by step 2n) involves Catalan-like counting; P(first return at step 2n) = C(2n,n) / (2^2n * (2n-1)); Probability of return to origin after exactly 2n steps (1D)
(define (binom n k)
(let loop ((i 0) (acc 1))
(if (= i k) acc
(loop (+ i 1) (* acc (/ (- n i) (+ i 1)))))))
(define (p-at-origin-1d n)
(/ (binom (* 2 n) n) (expt 2 (* 2 n))))
; These probabilities decrease but their sum diverges => recurrent
(display "1D P(at origin):") (newline)
(display " step 2: ") (display (p-at-origin-1d 1)) (newline)
(display " step 4: ") (display (p-at-origin-1d 2)) (newline)
(display " step 10: ") (display (p-at-origin-1d 5)) (newline)
(display " step 20: ") (display (p-at-origin-1d 10)) (newline)
; Sum diverges ~ 1/sqrt(pi*n) => returns infinitely often
(display "3D return probability ~ 0.3405") (newline)
(display "A drunk bird never comes home.")
Reflection principle
To count paths from (0, 0) to (n, k) that touch or cross zero, reflect the portion before the first crossing. This bijection between "bad" paths and paths starting from a reflected origin is the reflection principle. It gives exact formulas for first-passage times and maximum positions.
Scheme
; Reflection principle: count paths that touch the x-axis; Paths from (0,a) to (n,b) that touch 0; = total paths from (0,-a) to (n,b) [by reflection]; Number of lattice paths from 0 to b in n steps; that take +1 or -1 each step; Requires n and b have same parity, and |b| <= n
(define (lattice-paths n b)
(if (not (= (modulo n 2) (modulo (abs b) 2))) 0
(let ((ups (/ (+ n b) 2)))
(if (or (< ups 0) (> ups n)) 0
(binom n ups)))))
; Ballot problem: P(S_k > 0 for all k=1..n | S_n = b); = b/n (for b > 0)
(display "Ballot problem:") (newline)
(display "P(always positive | S_10=2) = 2/10 = ")
(display (/ 210)) (newline)
(display "P(always positive | S_10=4) = 4/10 = ")
(display (/ 410)) (newline)
; First passage time: P(first visit to k at step n); = (k/n) * C(n, (n+k)/2) / 2^n
(define (first-passage k n)
(if (not (= (modulo n 2) (modulo k 2))) 0
(* (/ k n) (/ (binom n (/ (+ n k) 2)) (expt 2 n)))))
(display "P(first reach +2 at step 2) = ")
(display (first-passage 22)) (newline)
(display "P(first reach +2 at step 4) = ")
(display (first-passage 24))
Notation reference
Textbook
Scheme
Meaning
Sₙ = X₁ + … + Xₙ
(random-walk n)
Position after n steps
P(ruin from k)
(ruin-fair k N)
Gambler's ruin probability
C(n, k)
(binom n k)
Binomial coefficient
recurrent / transient
sum diverges / converges
Returns infinitely often, or not
Neighbors
Probability chapters
๐ฐ Ch 11 — Markov Chains (random walks are Markov chains on integers)
๐ฐ Ch 9 — Central Limit Theorem (the walk's position is approximately normal)
The random walk simulation uses a deterministic pseudo-random generator for reproducibility. The gambler's ruin formula is exact. The reflection principle is stated without proof; the textbook derives it via a bijection on lattice paths. Pólya's recurrence theorem is stated as a fact; the proof uses generating functions from Chapter 10. Panangaden 2009 extends these ideas to continuous-state stochastic processes, where bisimulation replaces exact equality of paths.
Ready for the real thing? Read Chapter 12 of Grinstead & Snell.
Random walk
The Handshake