Home Statistical Dictionary Simple Random Walk

Simple Random Walk

A random walk restricted to steps of exactly $+1$ or $-1$, each chosen independently with a fixed probability, the canonical textbook example of a Markov chain on the integers.

Stochastic ProcessesBeginnerFree

In Plain English

The simple random walk is the drunkard's-walk idea reduced to its purest form: stand at some integer, flip a coin, step one unit right on heads and one unit left on tails, repeat forever. It's called 'simple' because the step size is fixed (unlike the general random walk, whose steps can follow any distribution) and the state space is just the integers, this narrow scope is exactly what makes it the go-to worked example for teaching Markov chain concepts like recurrence, transience, and the reflection principle, since every quantity can be computed exactly by hand.

Definition

A simple random walk is the process $S_{n} = \sum_{k = 1}^{n} ξ_{k}$ , where $S_{0} = 0$ and $ξ_{1}, ξ_{2}, \dots$ are independent, identically distributed steps taking value $+ 1$ with probability $p$ and $- 1$ with probability $1 - p$ . When $p = 1/2$ , the walk is symmetric, and it is precisely the Markov chain used to illustrate recurrence and transience by dimension: on $Z$ (one dimension) and $Z^{2}$ (two dimensions) the symmetric simple random walk is (null) recurrent, returning to the origin with probability 1, while in three or more dimensions it is transient (Pólya's recurrence theorem). The simple random walk also underlies the classical gambler's ruin problem (absorbing boundaries at 0 and some target wealth $N$ ) and, via Donsker's invariance principle, converges after rescaling to Brownian motion as the number of steps grows. This entry treats the walk as the specific, fixed-step-size Markov chain used as a foundational teaching example; see Random Walk for the broader family allowing arbitrary i.i.d. step distributions.

Formula

S_{n} = k = 1 \sum n ξ_{k}, ξ_{k} = {+ 1 - 1 w.p. p w.p. 1 - p

Notation

S_{n}

—Position of the walk after $n$ steps

ξ_{k}

—The $k$-th step, $+1$ or $-1$

p

—Probability of a $+1$ step; $p=1/2$ is the symmetric case

Properties

Every basic Markov chain concept, recurrence, transience, expected hitting times, has an exact, hand-computable answer for the simple random walk, which is precisely why it's the workhorse first example in every stochastic processes course.
The gambler's ruin problem, absorbing boundaries at wealth $0$ and $N$ , is solved exactly using the simple random walk's transition structure, giving closed-form ruin probabilities that generalize the intuition behind more complex absorbing Markov chains.
Pólya's recurrence theorem, that the symmetric simple random walk is recurrent in one and two dimensions but transient in three or more, is one of the most quoted results in all of probability theory, sometimes summarized as 'a drunk man will find his way home, but a drunk bird may get lost forever.'

At a Glance

Step sizefixed at

\pm 1

(unlike the general random walk's arbitrary step distribution)

As a Markov chaina nearest-neighbor chain on the integers, the standard teaching example

Symmetric case (p=1/2)recurrent in 1D and 2D, transient in 3D+ (Polya's theorem)

Scaling limitconverges to Brownian motion after rescaling (Donsker's invariance principle)

Last updated September 8, 2026← Back to the Dictionary