Stochastic Processes 7: Random Walks

The random walk is one of the most classic models in stochastic-process theory. On the surface it’s just “each step randomly goes left or right,” but what it actually studies is a very general structure: what macroscopic pattern emerges once a large number of small random changes keep accumulating? A random walk ties together random variables, the Markov property, independent increments, the central limit theorem, recurrence, and Brownian motion, making it the central model for understanding the various stochastic processes that follow.

1. One-Dimensional Random Walks

1.1 Definition: independent increments, with the state as the accumulated result

Starting from $X_0=0$, each step’s random increment $\epsilon_t$ takes $+1$ or $-1$ with equal probability, and the state updates recursively as $X_{t+1}=X_t+\epsilon_{t+1}$ — this is the simplest one-dimensional symmetric random walk. Expanding the recursion gives $X_t=X_0+\epsilon_1+\epsilon_2+\cdots+\epsilon_t=\sum_{i=1}^t\epsilon_i$: $\epsilon_t$ is the new random perturbation at each step, and $X_t$ is the state after all historical perturbations have accumulated. $\epsilon_1,\epsilon_2,\dots$ are usually set to be i.i.d., but $X_1,X_2,\dots$ are clearly not independent — $X_{t+1}$‘s own definition already includes $X_t$. One concrete sample path might be 0 → 1 → 2 → 1 → 0 → -1 → 0, and another might be an entirely different 0 → -1 → -2 → -1 → 0 → 1 → 0: both paths follow the same rule, choosing each step’s direction with the same probability, yet they can trace out completely different trajectories — this is exactly what “random” really means in a random walk: the rule is fixed, but the realization is not.

1.2 Why a random walk is Markov

Suppose it’s known that $X_t=5$; the next step only has two possibilities: moving to 4 with probability $1/2$, or to 6 with probability $1/2$. How it got to 5 in the past has no additional effect on the next step, i.e., $P(X_{t+1}\mid X_t,X_{t-1},\dots)=P(X_{t+1}\mid X_t)$. A simple random walk is therefore a standard first-order Markov process — the most direct example of the conditional-independence property from Stochastic Processes 5: Markov Processes.

2. Fluctuation Scale and Drift

2.1 The mean position is 0, but the typical distance isn’t

For a symmetric random walk, $E[\epsilon_t]=0$, so $E[X_t]=0$; but this doesn’t mean the random walk stays near the origin the whole time. $\operatorname{Var}(X_t)=t$, with standard deviation $\sqrt t$: after $t$ steps, the typical distance is on the order of $\sqrt t$, not $t$. The reason is that positive and negative increments largely cancel each other out; the central limit theorem gives $X_t/\sqrt t\Rightarrow N(0,1)$, showing that $X_t$‘s own natural scale is $\sqrt t$ — this is really just another manifestation of the $1/\sqrt n$ standard-error scale from Stochastic Processes 4, except this scale describes the cumulative sum itself, rather than the average.

2.2 A random walk with drift

If each step is no longer symmetric, $P(\epsilon_t=+1)=p\neq1/2$, the increment has a nonzero expectation $\mu=E[\epsilon_t]=p-(1-p)=2p-1$, and $E[X_t]=\mu t$. The random walk can then be understood as “a deterministic trend $\mu t$ plus random fluctuation”: the long-run trend grows linearly with $t$, while the random fluctuation is still on the order of $\sqrt t$ — this is the most basic drift-plus-noise structure, and the prototype for the drift and diffusion terms in stochastic differential equations later on.

3. Dimension and Recurrence

3.1 The key difference between one, two, and three or more dimensions

Extend the position to a $d$-dimensional vector $X_t\in\mathbb Z^d$, with each step randomly choosing one of $2d$ coordinate directions — the mathematical structure isn’t fundamentally different from one dimension. But the long-run behavior of a symmetric simple random walk changes qualitatively with dimension: a one- or two-dimensional random walk almost surely returns to the origin (recurrent), while in three or more dimensions there’s a positive probability of never returning to the origin again (transient). This is one of the most famous dimensional effects in stochastic-process theory.

3.2 Why $d=2$ is exactly the critical dimension

After $n$ steps, a random walk’s typical distance is on the order of $\sqrt n$; in $d$-dimensional space, the volume of a region of radius $\sqrt n$ grows roughly as $(\sqrt n)^d=n^{d/2}$, so the probability of returning to some fixed position is roughly on the order of $P(X_n=0)\sim n^{-d/2}$. Determining recurrence amounts to determining whether the series $\sum_nP(X_n=0)$ diverges: for $d=1$, the series looks like $\sum n^{-1/2}$, which diverges; for $d=2$, it looks like the harmonic series $\sum n^{-1}$, which still diverges; for $d=3$, it looks like $\sum n^{-3/2}$, a $p$-series with $p>1$, which converges. A divergent series means “infinitely many chances to accumulate at least one true return,” which is exactly the underlying reason one and two dimensions are recurrent while three or more are transient — $d=2$ sits precisely at the critical point between divergence and convergence, the harmonic series.

3.3 The “escape” probability in three or more dimensions can actually be computed exactly

“Transient” sounds like a vague qualitative description, but the probability that a three-dimensional simple symmetric random walk eventually returns to the origin actually has a precise value: this constant is called Pólya’s random walk constant, approximately $0.340537$ — in other words, on a random walk over a $d=3$ lattice, only about 34% of paths ever return to the starting point, while the remaining 66% never do. At $d=4$, this probability drops further to about $0.193$ — the higher the dimension, the harder it is to return to the origin. These numbers turn “recurrent in one and two dimensions, transient in three or more” from a simple binary classification into a probability curve that decreases continuously with dimension, with $d=1,2$ landing exactly on the boundary where the probability equals 1.

4. Hitting Times and Gambler’s Ruin

4.1 Hitting time

A random walk naturally raises questions like “when does it first reach a certain position.” Define $\tau_a=\inf\{t\ge0:X_t=a\}$ as the first time position $a$ is reached; $\tau_a$ is itself a random variable. Similarly, one can study the first return to the origin, the first time a threshold is exceeded, or the first time a boundary is hit — these questions later develop into the full theory of hitting time, first-passage time, and stopping time.

4.2 The reflection principle: computing the probability of reaching a position within $n$ steps

The event $\tau_a\le n$ (having reached $a$ at some point within $n$ steps) can be computed exactly using the reflection principle, without needing to enumerate every path. The intuition: any path that “reaches $a$ at some point and ends at $b<a$” can have the portion after touching $a$ flipped upside down, mapping it one-to-one onto a path “ending at $2a-b$,” and this correspondence is one-to-one and equally likely. Working through this correspondence gives $P(\tau_a\le n)=2P(S_n\ge a)-P(S_n=a)$ (for integer $a>0$). Taking $n=100$, $a=10$ as an example, plugging into the binomial distribution gives $P(\tau_{10}\le100)\approx0.320$: after 100 steps, there’s about a 32% probability of having reached position 10 at some point, even though $S_{100}$ itself has expectation 0 and a standard deviation of only 10. The reflection principle is the discrete version of the calculation used later for Brownian motion’s first-passage probability — both use the same symmetry argument.

4.3 The Gambler’s Ruin problem, worked out

Suppose someone starts with $k$ units of wealth, winning or losing 1 unit each round with equal probability; their wealth process is then a simple random walk with two absorbing boundaries ($0$ meaning ruin, $N$ meaning reaching the goal). The question “starting from $k$, does it reach $N$ or 0 first” is the classic Gambler’s Ruin problem. For a fair coin ($p=1/2$), the probability of going broke before reaching $N$ is exactly $1-k/N$, and the probability of reaching $N$ first is $k/N$ — this clean result can be proven using the fact that the wealth process is itself a martingale, though it can be used directly without first understanding martingales. Taking $k=30$, $N=100$ as an example, the probability of reaching 100 first is $30/100=0.3$, and the probability of going broke first is $0.7$; raising $k$ to 90 increases the probability of reaching 100 first to $0.9$ — the closer the starting capital is to the goal, the more likely it is to reach the target before going broke. This linear relationship only holds for a fair coin; once $p\neq1/2$, the formula becomes $\dfrac{1-(q/p)^k}{1-(q/p)^N}$ (with $q=1-p$), no longer a simple linear proportion.

5. Generalizations of the Random Walk

5.1 Random walks on graphs

A random walk doesn’t have to happen on a line or a regular grid: if the state space is a graph and each step randomly chooses one of the current node’s neighbors, the result is a random walk on a graph, widely seen in PageRank, network analysis, community detection, MCMC, and diffusion-propagation models. The classic intuition behind PageRank is a user continually clicking random links between web pages, and studying which pages get visited more in the long run.

5.2 Brownian motion: the continuous-time limit

If both the spatial step size and time interval of each step are made progressively finer, with appropriate rescaling, a random walk’s entire sample path gradually approaches Brownian motion: Brownian motion can be understood as the continuous-time limit of a random walk — this connection is the generalization of the central limit theorem to the level of “the entire stochastic process,” not just the distribution at a single moment.

6. Common Misconceptions and Summary

The easiest misconception about random walks is conflating “the mean position is 0” with “the random walk stays near the origin the whole time” — Section 2.1 already explained that the typical distance $\sqrt t$ keeps growing over time, just far more slowly than linear growth. Another common misconception is equating recurrence with “it’s guaranteed to come back many times”: recurrence in one and two dimensions only guarantees a probability of 1 of returning to the origin at least once (in fact, infinitely often), but the expected return time can still be infinite — recurrence doesn’t mean returning “quickly.”

The most basic form of a random walk is $X_{t+1}=X_t+\epsilon_{t+1}$, that is, “current state = previous step’s state + a new random perturbation” — an extremely simple definition that nevertheless naturally gives rise to the Markov property, independent increments, the $\sqrt t$ fluctuation scale, dimension-dependent recurrence/transience, hitting times, and absorbing-boundary problems like Gambler’s Ruin, all the way connecting to random walks on graphs and Brownian motion. A random walk isn’t an isolated toy example — it’s the central model that ties together a large number of core concepts in stochastic-process theory.