Introduction

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.

Try It: Simulate the Walk

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 ×10</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
  <span class="label">Dimension:</span>
  <button id="dim2d" type="button" class="dim active">2D</button>
  <button id="dim3d" type="button" class="dim">3D</button>
</div>
<div class="stats">
  Steps: <strong id="stepCount">0</strong> &nbsp;|&nbsp;
  Distance: <strong id="distVal">0.00</strong> &nbsp;|&nbsp;
  Returns to origin: <strong id="returnCount">0</strong>
</div>
<canvas id="canvas" width="460" height="200"></canvas>
<div class="chart-label">Distance from origin over time</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; }

// Pólya's theorem: a symmetric random walk on Z^d is recurrent (returns to origin
// infinitely often, probability 1) for d=1,2 and transient for d≥3.
// This demo shows a 2D walk (recurrent) vs a 3D walk projected to 2D (transient).

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const chartCanvas = document.getElementById('chart');
const cctx = chartCanvas.getContext('2d');

let pos = { x: 0, y: 0, z: 0 };
let steps = 0, returns = 0;
let dim = 2;
let running = false;
let timer = null;
let history = []; // distance over time (downsampled)
const MAX_HISTORY = 460;

// Map lattice coords to canvas pixels (center = 230,100; scale = 8px per unit)
const CX = 230, CY = 100, SCALE = 8;
let trail = []; // screen coords
const MAX_TRAIL = 600;

function latticeToScreen(x, y) {
  return { sx: CX + x * SCALE, sy: CY + y * SCALE };
}

function dist() {
  if (dim === 2) return Math.sqrt(pos.x * pos.x + pos.y * pos.y);
  return Math.sqrt(pos.x * pos.x + pos.y * pos.y + pos.z * pos.z);
}

function step() {
  if (dim === 2) {
    const d = Math.floor(Math.random() * 4);
    if (d === 0) pos.x++;
    else if (d === 1) pos.x--;
    else if (d === 2) pos.y++;
    else pos.y--;
  } else {
    const d = Math.floor(Math.random() * 6);
    if (d === 0) pos.x++;
    else if (d === 1) pos.x--;
    else if (d === 2) pos.y++;
    else if (d === 3) pos.y--;
    else if (d === 4) pos.z++;
    else pos.z--;
  }
  steps++;
  if (pos.x === 0 && pos.y === 0 && pos.z === 0) returns++;
  const { sx, sy } = latticeToScreen(pos.x, pos.y);
  trail.push({ sx, sy });
  if (trail.length > MAX_TRAIL) trail.shift();
  if (history.length < MAX_HISTORY) history.push(dist());
  else { history.shift(); history.push(dist()); }
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Grid lines (faint)
  ctx.strokeStyle = '#dde3ea';
  ctx.lineWidth = 0.5;
  for (let x = CX % SCALE; x < canvas.width; x += SCALE) {
    ctx.beginPath(); ctx.moveTo(x, 0); ctx.lineTo(x, canvas.height); ctx.stroke();
  }
  for (let y = CY % SCALE; y < canvas.height; y += SCALE) {
    ctx.beginPath(); ctx.moveTo(0, y); ctx.lineTo(canvas.width, y); ctx.stroke();
  }

  // Origin cross
  ctx.strokeStyle = '#b0bec8'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(CX - 6, CY); ctx.lineTo(CX + 6, CY); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(CX, CY - 6); ctx.lineTo(CX, CY + 6); ctx.stroke();

  // Trail
  if (trail.length > 1) {
    ctx.beginPath();
    ctx.moveTo(trail[0].sx, trail[0].sy);
    for (let i = 1; i < trail.length; i++) ctx.lineTo(trail[i].sx, trail[i].sy);
    ctx.strokeStyle = 'rgba(100,140,180,0.35)';
    ctx.lineWidth = 1.2;
    ctx.stroke();
  }

  // Current position dot
  const { sx, sy } = latticeToScreen(pos.x, pos.y);
  ctx.beginPath(); ctx.arc(sx, sy, 5, 0, Math.PI * 2);
  ctx.fillStyle = returns > 0 ? '#0a7d33' : '#1d3557';
  ctx.fill();
}

function drawChart() {
  cctx.clearRect(0, 0, chartCanvas.width, chartCanvas.height);
  if (history.length < 2) return;
  const maxD = Math.max(...history, 1);
  const w = chartCanvas.width, h = chartCanvas.height;
  cctx.beginPath();
  for (let i = 0; i < history.length; i++) {
    const x = (i / (MAX_HISTORY - 1)) * w;
    const y = h - (history[i] / maxD) * (h - 4) - 2;
    if (i === 0) cctx.moveTo(x, y); else cctx.lineTo(x, y);
  }
  cctx.strokeStyle = '#1d7fd4';
  cctx.lineWidth = 1.4;
  cctx.stroke();

  // Baseline
  cctx.beginPath(); cctx.moveTo(0, h - 1); cctx.lineTo(w, h - 1);
  cctx.strokeStyle = '#ccd5de'; cctx.lineWidth = 1; cctx.stroke();
}

function updateStats() {
  document.getElementById('stepCount').textContent = steps;
  document.getElementById('distVal').textContent = dist().toFixed(2);
  document.getElementById('returnCount').textContent = returns;
}

function doSteps(n) {
  for (let i = 0; i < n; i++) step();
  draw(); drawChart(); updateStats();
}

function reset() {
  pos = { x: 0, y: 0, z: 0 };
  steps = 0; returns = 0;
  trail = [{ sx: CX, sy: CY }];
  history = [0];
  running = false;
  clearInterval(timer); timer = null;
  document.getElementById('startBtn').textContent = 'Start';
  draw(); drawChart(); updateStats();
}

document.getElementById('startBtn').addEventListener('click', () => {
  running = !running;
  document.getElementById('startBtn').textContent = running ? 'Pause' : 'Resume';
  if (running) {
    timer = setInterval(() => doSteps(5), 50);
  } else {
    clearInterval(timer); timer = null;
  }
});

document.getElementById('stepBtn').addEventListener('click', () => {
  if (running) { clearInterval(timer); timer = null; running = false; document.getElementById('startBtn').textContent = 'Resume'; }
  doSteps(10);
});

document.getElementById('resetBtn').addEventListener('click', reset);

document.getElementById('dim2d').addEventListener('click', () => {
  dim = 2;
  document.getElementById('dim2d').classList.add('active');
  document.getElementById('dim3d').classList.remove('active');
  reset();
});
document.getElementById('dim3d').addEventListener('click', () => {
  dim = 3;
  document.getElementById('dim3d').classList.add('active');
  document.getElementById('dim2d').classList.remove('active');
  reset();
});

reset();
Result
Console

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.

Pólya's Theorem

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 1πn\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 1πn\frac{1}{\pi n}. Summing still diverges — recurrence survives into two dimensions.
  • d ≥ 3: the return probability at step 2n decays like n−d/2n^{-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)=∑npn(0,0)G(0,0) = \sum_n p_n(0,0), where pnp_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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/random-walk/Content licensed under CC BY-NC 4.0.