Random Walks

Random Walk

A random walk is the simplest non-trivial discrete-time stochastic process: cumulative sums of independent, identically distributed shocks. Starting from $x_0=0$, the process is defined by the recursion
$x_t=x_{t-1}+w_t,t=1,2,\dots ,$
where $\{w_t\}$ are i.i.d. with mean $0$ and variance ${\sigma }^2$. Equivalently, in closed form,
$x_t={\sum }_{j=1}^t{w}_j.$
The mean function is $\mathbb{E}[x_t]=0$ for every $t$, but the variance grows linearly with time, $\mathrm{Var}(x_t)=t{\sigma }^2$, so the process spreads out without bound. Because the variance depends on $t$, the random walk is not stationary, and consequently the autocovariance depends on absolute times rather than just on lag.

Adding a constant drift $\delta$ at every step gives the random walk with drift:
$x_t=\delta +x_{t-1}+w_t,x_t=\delta t+{\sum }_{j=1}^t{w}_j.$
The mean function becomes the deterministic line $\mathbb{E}[x_t]=\delta t$ while the variance still grows as $t{\sigma }^2$. The drift adds a slope; the noise adds the wiggle.

The autocovariance of a random walk has the same form as the covariance of Brownian motion sampled at integer times,
$\gamma (s,t)=\mathrm{Cov}(x_s,x_t)={\sigma }^2\min (s,t),$
because two random-walk values at times $s\le t$ share exactly the shocks accumulated up to time $\min (s,t)$, and the shocks after that point are independent and contribute nothing.

The most useful single fact about random walks for time-series modeling is that differencing recovers the underlying noise: $\nabla x_t=x_t-x_{t-1}=w_t$. So a random walk is the integral of white noise, and white noise is the increment of a random walk. This is why an ARIMA(0, 1, 0) model, which differences once an otherwise-uncorrelated series, describes a random walk exactly.

Intuition

A random walk is the path traced out by an object that, at each tick of the clock, takes a step of random size and direction independent of its history. The position at time $t$ is the sum of all the steps taken so far, so even though each individual step has zero expected size, the cumulative deviation from the starting point grows steadily with time. The process has no preferred level (nothing pulls it back toward the origin), so it will eventually wander arbitrarily far in either direction. This is the fundamental difference from a stationary process: a random walk has no equilibrium distribution to settle into.

The drift extension simply adds a deterministic slope on top of this aimless wandering. With drift $\delta$, each step has expected size $\delta$ rather than $0$, so the path tilts upward (or downward) at rate $\delta$. The wiggle around the trend is the same random walk as before. This is the standard model for many phenomena that combine a slow systematic change with day-to-day randomness: stock prices over long horizons, populations of growing species, atmospheric CO₂ concentrations, or accumulated evidence in a cognitive decision-making task. The drift captures the systematic component; the noise captures everything that is not.

Properties

(Independent Increments) The shocks $w_t$ are i.i.d. and equal the first differences of the walk.

By construction, $x_t-x_{t-1}=w_t$, so the first-difference series $\{w_t\}$ is the original i.i.d. white noise. The differences over disjoint time intervals are sums of disjoint subsets of the $w_t$, and therefore independent. This independent-increments property is what makes the random walk a Markov process and what lets the Brownian motion limit theorems carry through under rescaling.

(Mean and Variance Functions) Mean is $\delta t$; variance is $t{\sigma }^2$ regardless of drift.

For the walk with drift, the mean is $\mathbb{E}[x_t]=\delta t+{\sum }_{j=1}^t\mathbb{E}[w_j]=\delta t$, and the variance is $\mathrm{Var}(x_t)=\mathrm{Var}\left({\sum }_{j=1}^t{w}_j\right)=t{\sigma }^2$ because the shocks are uncorrelated. The drift contributes nothing to the variance; only the noise does. The implication is that the signal-to-noise ratio of the trend, $\delta t/\sqrt{t{\sigma }^2}=\delta \sqrt{t}/\sigma$, grows like $\sqrt{t}$, which is why long records can detect tiny drift rates that look invisible at short horizons.

(Autocovariance) $\gamma (s,t)={\sigma }^2\min (s,t)$, depending on absolute times rather than just on lag.

Write $s\le t$ and decompose $x_t=x_s+(x_t-x_s)$. The first piece $x_s$ is independent of the second piece $x_t-x_s$, since the latter is a sum of $w_{s+1},\dots ,w_t$ and the former is a sum of $w_1,\dots ,w_s$. So $\mathrm{Cov}(x_s,x_t)=\mathrm{Var}(x_s)=s{\sigma }^2={\sigma }^2\min (s,t)$. The dependence on $\min (s,t)$ rather than on $|s-t|$ is the algebraic statement of non-stationarity: shifting both times forward by the same amount changes the covariance, because $\min (s+h,t+h)=h+\min (s,t)$ rather than $\min (s,t)$.

(Differencing Yields White Noise) $\nabla x_t=w_t$, so first differencing reduces the random walk to its noise driver.

This is the structural reason a random walk is denoted $I(1)$, integrated of order one, and modeled as ARIMA(0, 1, 0). The $d=1$ in the ARIMA triple means “difference once before fitting.” After differencing, the result is white noise that has no AR or MA structure left, so $p=0$ and $q=0$. For the random walk with drift, $\nabla x_t=\delta +w_t$ is white noise plus a constant, and the constant becomes the drift coefficient in the fitted ARIMA model.

(Markov Property) The future depends on the past only through the present.

Conditional on $x_t$, the next value $x_{t+1}=x_t+w_{t+1}$ is determined by adding a single fresh shock independent of everything before $t$. So $\{x_t\}$ is a discrete-time Markov chain on $\mathbb{R}$ (or on $\mathbb{Z}$ in the integer-step case). The transition density when the shocks are Gaussian is $p(x_{t+1}\mid x_t)=\mathcal{N}(x_t+\delta ,{\sigma }^2)$, a Gaussian centered on the previous value plus the drift.

(Martingale Property) The driftless random walk is a martingale; with drift $\delta$, the centered process $x_t-\delta t$ is a martingale.

For the driftless case, $\mathbb{E}[x_{t+1}\mid x_1,\dots ,x_t]=\mathbb{E}[x_t+w_{t+1}\mid x_1,\dots ,x_t]=x_t+0=x_t$, since the future shock has mean zero and is independent of the past. The conditional expectation of the next value is the current value, the defining property of a martingale. With drift, the centered version $y_t=x_t-\delta t$ satisfies the same identity. Martingale convergence and stopping theorems then apply, which is the basis of gambler’s-ruin calculations and many results in stochastic finance.

(Recurrence vs. Transience) In one and two dimensions a simple random walk returns to the origin with probability one; in three or more dimensions it does not.

For the symmetric random walk on ${\mathbb{Z}}^d$ with $\pm 1$ unit steps in each coordinate, Pólya’s theorem says the walker returns to the origin infinitely often almost surely when $d=1$ or $d=2$, and only finitely often when $d\ge 3$. The classical phrasing is “a drunk man will find his way home, but a drunk bird may not.” The intuition is that the volume of $d$-dimensional space available at distance $r$ grows as $r^{d-1}$, while the variance of the walker’s position only grows as $\sqrt{t}$, so for $d\ge 3$ the walker has too many directions to escape into.

(Brownian Limit) The rescaled random walk converges to Brownian motion.

By Donsker’s invariance principle, if $\{w_j\}$ are i.i.d. with mean $0$ and variance ${\sigma }^2$, then the scaled and interpolated process
$B_t^{(n)}:=\frac{1}{\sigma \sqrt{n}}{x}_{\lfloor nt\rfloor }$
converges in distribution (as a process on $C([0,1])$) to standard Brownian motion as $n\to \infty$. So Brownian motion is the continuous-time scaling limit of the random walk, which gives a constructive justification for treating BM as “continuous-time random walk” and lets discrete random-walk results pass to BM in the appropriate limit.

Examples

Differencing a random walk to recover white noise

You observe a series $x_1,x_2,\dots ,x_T$ that visually looks like a random walk: no preferred level, slow wandering, no obvious oscillation. How do you check whether it really is, and how do you model the noise?

Compute the first differences $w_t:=x_t-x_{t-1}$ for $t=2,\dots ,T$, then look at the sample ACF of $\{w_t\}$. If $\{x_t\}$ is a pure random walk, the differences are i.i.d. and the sample ACF of the differences should be flat (all entries inside the $\pm 1.96/\sqrt{T}$ confidence band). If the ACF of the differences shows persistent structure, the original series is not a pure random walk: it has additional autocorrelation on top of the unit-root behavior, which would call for an ARIMA(p, 1, q) model with non-trivial $p$ or $q$. The mean of $\{w_t\}$ estimates the drift; if the sample mean is significantly different from zero, fit an ARIMA with drift.

Autocovariance from definition

Verify the formula $\gamma (s,t)={\sigma }^2\min (s,t)$ for $s=3,t=7$ when the increments are i.i.d. $\mathcal{N}(0,1)$.

$x_3=w_1+w_2+w_3$ and $x_7=w_1+w_2+w_3+w_4+w_5+w_6+w_7$. The covariance is the sum of $\mathrm{Cov}(w_i,w_j)$ over all pairs $(i,j)$ with $i\in \{1,2,3\}$ and $j\in \{1,\dots ,7\}$. Since the $w$‘s are uncorrelated, only the diagonal terms with $i=j$ survive, contributing $\mathrm{Var}(w_i)=1$ each. The matching pairs are $(1,1),(2,2),(3,3)$, giving $\gamma (3,7)=3=\min (3,7)$. The same calculation generalizes to arbitrary $s\le t$: only the first $s$ shocks appear in both sums, and each contributes its variance.

Random walk with drift in disguise

Stock prices on long horizons are often modeled as a geometric random walk: $\log P_t=\log P_{t-1}+\mu +w_t$, with $w_t\sim \mathcal{N}(0,{\sigma }^2)$. What is the model in terms of $P_t$ itself, and why is the log transform standard?

Exponentiating, $P_t=P_{t-1}\cdot e^{\mu +w_t}$, so prices grow multiplicatively rather than additively. Modeling $\log P_t$ as a random walk with drift gives a process whose log returns $r_t=\log P_t-\log P_{t-1}=\mu +w_t$ are i.i.d., a much more reasonable assumption than that price changes themselves are i.i.d. (since absolute price changes scale with the price level). The drift $\mu$ is the expected continuously compounded return per period, and the variance ${\sigma }^2$ is the squared volatility. This is the simplest version of the Black-Scholes setup, with the geometric Brownian motion of stock prices as the continuous-time limit of this discrete log-random-walk.

See Also

• 4.6 Brownian Motion: continuous-time scaling limit via Donsker’s invariance principle.
• 4.3 Markov Chains: random walks are the canonical $\mathbb{R}$- or $\mathbb{Z}$-valued Markov chains.
• 4.5 Martingales: driftless random walks are the canonical discrete-time martingale.
• 2.5.6 ARIMA(p,d,q) Process: the random walk is ARIMA(0, 1, 0); modeling non-stationary series usually starts by checking whether differencing recovers stationarity.
• 2.1. Time Series: the random walk is the standard non-stationary example used to motivate stationarity assumptions.