Trajectories X(t)
Cumulative position as a function of step t
What is a random walk?
A random walk is a sequence of steps in which the direction of each step is chosen randomly and independently. The simplest model in one dimension is the simple random walk: a particle starts at position X₀ = 0 and at each instant t moves +1 (with probability p) or −1 (with probability 1 − p).
If p = 0.5, the walk is symmetric: there is no trend or preferred direction. If p ≠ 0.5, there is a drift that systematically pushes the trajectory in one direction, although random noise is still the dominant component in the short term.
Formally, the position at step n is:
\( X_n = \sum_{i=1}^{n} \xi_i \)
where each \(\xi_i\) is an independent random variable with P(\(\xi_i = +1\)) = p and P(\(\xi_i = -1\)) = 1 − p.
Mathematical properties
Mean and variance
Since E[\(\xi_i\)] = p − (1−p) = 2p − 1 and Var(\(\xi_i\)) = 1 − (2p−1)² = 4p(1−p), by linearity of expectation and independence:
- Mean: E[Xn] = n(2p − 1). For p = 0.5, the mean is 0 for all n.
- Variance: Var(Xn) = 4p(1−p) · n. For p = 0.5, Var = n.
- Standard deviation: σ(Xn) = 2√(p(1−p)) · √n. For p = 0.5, σ = √n.
The fact that the spread grows as √n rather than n is the most characteristic property of the random walk. The trajectories "fan out," but more slowly than one might expect. For example, after 10,000 steps, the standard deviation of the position is only √10,000 = 100.
Asymptotic distribution and the connection to the CLT
By the central limit theorem, Xn is a sum of n iid variables, so for large n:
\( X_n \approx \mathcal{N}\!\left(n(2p-1),\; 4p(1-p)\,n\right) \)
This justifies the theoretical ±2σ bands you can see in the simulator: approximately 95% of trajectories should fall within the band E[Xn] ± 2 · 2√(p(1−p)n). Notice how the bands widen following the √n curve rather than a straight line.
The random walk in 2D
In two dimensions, the particle moves with equal probability 1/4 along each of the four axes (north, south, east, west). Now Xn and Yn are two independent 1D random walks that evolve on alternating steps: on average, each component receives n/2 effective steps.
The Euclidean distance to the origin is still of order √n:
\( \mathrm{E}\!\left[\,r_n^2\,\right] = \mathrm{E}[X_n^2 + Y_n^2] = n \) ⟹ \( r_{\mathrm{RMS}} = \sqrt{n} \)
The dashed circle in the 2D simulator has radius √n and corresponds to this root-mean-square distance. Notice how the endpoints of the trajectories cluster roughly within that circle.
Recurrence: the walk always returns to the origin
One of the most counterintuitive properties of the random walk was proved by the Polish mathematician George Pólya in 1921. His most famous theorem states:
- In 1D and 2D: the simple random walk is recurrent — the probability of returning to the starting point (and to any point already visited) is exactly 1. Given enough time, the walker always comes back.
- In 3D and higher dimensions: the walk is transient — the probability of returning to the origin is less than 1 (≈ 0.3405 in 3D). A drunk bird can get lost forever.
The intuition behind this result is that in low dimensions the space is "small" compared to how thoroughly the walk explores it, whereas in high dimensions there are too many possible directions and the particle disperses irreversibly. This property has deep implications in statistical physics, graph theory and ecology.
In the 2D simulator, set a large number of steps (5,000–10,000) with a single trajectory and watch how the particle repeatedly returns to the origin even though it seems to have wandered off for good.
The gambler's ruin
Imagine a gambler who starts with $a and plays a series of $1 bets against an opponent with $b. On each round, the gambler wins $1 with probability p or loses $1 with probability q = 1 − p. The game ends when someone goes broke.
This classic problem is equivalent to a random walk with absorbing barriers at 0 and a + b. The probability that the gambler goes broke is:
\[ P(\text{ruin}) = \begin{cases} \dfrac{(q/p)^a - (q/p)^{a+b}}{1 - (q/p)^{a+b}} & \text{if } p \neq \tfrac{1}{2} \\[1.4em] \dfrac{b}{a+b} & \text{if } p = \tfrac{1}{2} \end{cases} \]
For a fair game (p = 0.5), the probability of ruin depends only on the ratio of capital: if the gambler has $100 and the house has $900, the probability that the gambler goes broke is 900/1000 = 90%. Even with a perfectly fair game, the asymmetry in capital makes ruin nearly certain for the poorer player.
With p < 0.5 (the real situation in a casino, where the house has the edge), ruin is practically inevitable in the long run. Only with p > 0.5 can the gambler have a positive probability of ruining the opponent before going broke.
In the 1D simulator, change p to 0.40 or 0.30 with negative drift and watch how the trajectories decline systematically — that's the house edge at work.
Brownian motion: the continuous limit
When the step size and the time interval both shrink toward 0 in a coordinated way, the random walk converges in distribution to Brownian motion (also called the Wiener process), the continuous model of diffusion.
Formally, if we define Bt = X⌊nt⌋/√n, then Bt → Wt where W is a standard Wiener process with W₀ = 0, independent increments and Wt − Ws ~ N(0, t − s).
Brownian motion was first observed by Robert Brown (1827), who noted the erratic movement of pollen grains in water, and was explained mathematically by Albert Einstein in 1905 as the result of molecular bombardment. The same mathematics of the random walk describes:
- Molecular diffusion in a fluid (Fick's diffusion equation, D = σ²/2t).
- Heat conduction (the heat equation is a diffusion equation).
- Financial prices (the Black-Scholes model, geometric Brownian motion).
- Polymers in chemistry (the conformation of a polymer chain follows a random walk in 3D).
Applications of the random walk
📈 Finance
The efficient market hypothesis of Eugene Fama (1970) proposes that asset prices follow a random walk, implying that future prices cannot be predicted from past history. The Black-Scholes model assumes geometric Brownian motion for the underlying price.
🧬 Biology and ecology
The movement of microorganisms such as bacteria is modeled with random walks. In ecology, the dispersal of seeds and animals follows random-walk patterns, although many species use more efficient strategies (Lévy flights).
💻 Algorithms and AI
Google's PageRank algorithm is based on the stationary vector of a random walk over the web graph. Markov Chain Monte Carlo (MCMC) methods in Bayesian statistics explore complex distributions using random walks in parameter space.
⚛️ Physics
The diffusion of charged particles in plasmas, neutron transport in nuclear reactors, electrical resistivity in metals, and molecular dynamics in computer simulations all use the random-walk formalism.
Frequently asked questions
Why do positions spread as √n and not as n?
Because the position Xn is a sum of n independent random variables, and by the central limit theorem the standard deviation of a sum grows as √n. If each step can be ±1, the variance of the sum is n·Var(ξ), and the standard deviation is √n·σ. This sublinear growth is the mathematical signature of diffusion.
Does the random walk actually predict stock prices?
It's an active debate. The weak form of the efficient market hypothesis says that past prices do not allow you to predict future ones — which is consistent with the random walk. However, behavioral finance has documented numerous anomalies (mean reversion, momentum, calendar effects) suggesting that markets are not perfectly efficient. In practice, the random walk is a useful first approximation, not an exact description.
What's the difference between p = 0.5 and p = 0.51?
In the short run, very little: noise dominates. But in the long run, the difference is enormous. With p = 0.51 and n = 10,000 steps, the expected drift is n(2p−1) = 10,000 × 0.02 = 200 positions, while the standard deviation is √10,000 ≈ 100. The drift far exceeds the random variability. This is why a small but consistent edge (like the house edge in blackjack) dominates the outcome over the long run.
How does the 2D walk relate to Markov chains?
The 2D random walk on the grid ℤ² is a special case of a Markov chain with an infinite state space. The Markov property holds because the next position depends only on the current position, not on the history. However, since there are infinitely many states, analyzing the stationary distribution differs from the finite chains in the Markov chain simulator.
What are Lévy flights?
Lévy flights are a generalization of the random walk in which the steps do not have finite variance: most are small, but occasionally very large jumps occur, following a heavy-tailed distribution (stable Lévy distribution). Many animals, from albatrosses to sharks, use search strategies that resemble Lévy flights because they are optimal for exploring environments where prey is scarce and randomly distributed.