Random Walks

Imagine a drunk leaving a bar. Each step, he flips a coin and lurches left or right. After a thousand steps, will he find his way home?

The answer — yes, with probability one — sounds like folk wisdom. But Pólya's theorem (1921) turns it into a sharp mathematical fact, and the proof reveals something genuinely strange: the dimension of the space determines the outcome entirely.

• In 1D (a line) and 2D (a grid), the walk is recurrent: it returns to the starting point infinitely often, with probability 1. The drunk always comes home.
• In 3D (and any higher dimension), the walk is transient: there is a positive probability of never returning. A lost bird in the air may be lost forever.

This is not a quirk of the drunk's coordination. It is a precise theorem about random processes on lattices, proven by the Hungarian mathematician George Pólya in 1921. The result has since turned up in physics, finance, biology, and the theory of algorithms — a simple coin flip hiding one of the deepest surprises in all of mathematics.

Press Start to watch a drunkard take random steps on a 2D grid. The blue dot is the current position; the faint trail shows the path. The chart below the grid tracks the distance from the origin over time.

<div class="controls">
  <button id="startBtn" type="button">{{start}}</button>
  <button id="stepBtn" type="button">{{step_btn}}</button>
  <button id="resetBtn" type="button" class="ghost">{{reset}}</button>
  <span class="label">{{dimension_label}}</span>
  <button id="dim2d" type="button" class="dim active">{{dim2d_label}}</button>
  <button id="dim3d" type="button" class="dim">{{dim3d_label}}</button>
</div>
<div class="stats">
  {{steps_label}}: <strong id="stepCount">0</strong> &nbsp;|&nbsp;
  {{distance_label}}: <strong id="distVal">0.00</strong> &nbsp;|&nbsp;
  {{returns_label}}: <strong id="returnCount">0</strong>
</div>
<canvas id="canvas" width="460" height="200"></canvas>
<div class="chart-label">{{chart_label}}</div>
<canvas id="chart" width="460" height="100"></canvas>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; }
.label { font-size: .85rem; color: #555; margin-left: .3rem; }
.stats { font-size: .85rem; color: #444; margin-bottom: .4rem; }
button {
  font: 600 13px system-ui; padding: .35rem .75rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
  border-radius: 7px; cursor: pointer;
}
button.ghost { background: #fff; color: #1d3557; }
button.dim { background: #e8eef3; color: #1d3557; border-color: #cdd9e3; }
button.dim.active { background: #1d3557; color: #fff; }
canvas { display: block; border-radius: 8px; background: #f4f7fa; margin-bottom: .3rem; }
.chart-label { font-size: .75rem; color: #888; margin-bottom: .2rem; }

// Code not found

Notice how the walk wanders far out, then doubles back and crosses the origin again. That crossing is guaranteed — given enough time, the 2D walk returns with certainty. Compare this to what Brownian motion looks like in physics: the same mathematics, scaled to atomic distances.

Status: proven. George Pólya established the recurrence/transience dichotomy in 1921 — one of the earliest and cleanest results in the theory of stochastic processes.

The key quantity is the expected number of returns to the origin. For a simple symmetric random walk on the integer lattice ℤᵈ:

• If this expected count is infinite, the walk is recurrent: it returns to the start infinitely often with probability 1.
• If the expected count is finite, the walk is transient: it eventually escapes and never comes back.

The threshold falls at dimension 2:

• d = 1: at step 2n, the probability of being at the origin is roughly $\frac{1}{\sqrt{\pi n}}$. Summing over all n diverges — infinitely many returns, certainty of recurrence.
• d = 2: the return probability at step 2n falls like $\frac{1}{\pi n}$. Summing still diverges — recurrence survives into two dimensions.
• d ≥ 3: the return probability at step 2n decays like $n^{-d/2}$. For d ≥ 3, the sum converges — finite expected returns, transience.

Pólya's proof relies on counting paths and comparing series. A modern route uses the Green's function $G(0,0) = \sum_n p_n(0,0)$, where $p_n$ is the probability of being at the origin after n steps. Recurrence ⟺ G diverges.

The result is exact and complete — there is no open case. Dimension 2 is the last refuge: any random walk in the plane is guaranteed to come home, but lift the walk into three-dimensional space and the guarantee evaporates. This is connected to why the Navier–Stokes equations for turbulent fluids behave so differently in 2D versus 3D.

The random walk is one of the most productive models in all of science:

• Diffusion and heat: a particle buffeted by molecules in a liquid follows a random walk. Einstein's 1905 paper on Brownian motion used exactly this model to calculate diffusion coefficients and — famously — estimate Avogadro's number.
• Finance: stock prices are often modeled as a random walk (the "efficient market hypothesis"). The recurrence theorem tells you that a 1D or 2D price path returns to any level infinitely often, which matters for options pricing.
• Algorithms: random walks on graphs underlie the PageRank algorithm (Google), and Markov Chain Monte Carlo methods use random walks to sample from probability distributions too complex to handle directly. These power modern machine learning and Bayesian inference.
• Polymer physics: a long polymer chain in solution behaves like a self-avoiding random walk. Predicting how it folds connects directly to Pólya-type recurrence arguments.
• Electrical networks: the probability that a walk from node u reaches v before returning to u equals the effective resistance between them — a beautiful bridge between probability and graph theory.

Whenever you model anything that accumulates random shocks over time — prices, gene frequencies, robot navigation, epidemic spread — you are working with a random walk. Pólya's theorem sets the foundational ceiling: whether the process can find its way back depends entirely on the dimension it lives in.

A coin flip repeated forever on a line will bring you home — not probably, but certainly. The same on a grid. But add one dimension and the guarantee vanishes: in three-dimensional space, the walk escapes with positive probability and may never return.

This is Pólya's theorem, settled since 1921, with no open questions remaining. What makes it beautiful is the starkness of the answer: two dimensions is the exact threshold. One dimension above the boundary and the mathematics flips entirely.

The theorem also anchors a vast ecosystem of results. Every time an algorithm uses a random walk to explore a graph, every time a physicist models diffusion, every time a financial model assumes prices move randomly, Pólya's insight is at work in the background. The drunk who always finds the bar is, quietly, one of the most useful characters in all of mathematics.