The Bird Does Not Come Home
Two Drunks, One Pub, and All the Time in the World
At closing time the pub throws out a man and a pigeon.
The man cannot remember which way home is. So at every corner he picks a street at random and walks one block. Then he does it again. He never gets a clue, a landmark or a lucky break — just coin flips, forever. He is immortal, because this is mathematics and we are allowed.
The pigeon has exactly the same problem and one extra move. As well as picking a direction on the map, it picks up or down.
Does either of them ever find the pub again?
The man does. Not probably — with probability one, guaranteed, no exceptions. And then he finds it again. And again. He is condemned to stumble back into that pub infinitely many times, for eternity, entirely by accident.
So the pigeon, with the same infinite time and one more way to move, surely does at least as well.
It gets home 34% of the time. The other two-thirds it flies off and never comes back. Not “takes a very long time” — never. It passes the pub a handful of times and then leaves for good, and eternity does not help it.
One extra dimension turns a certainty into a bet you mostly lose.
Infinity Is Not Enough
This is Pólya’s theorem, from 1921, and the statement is as blunt as the story. Take the simple random walk on the lattice $\mathbb{Z}^d$ — at each step, pick one of the $2d$ neighbours uniformly and move there.
For $d = 1$ and $d = 2$ the walk is recurrent: it returns to where it started with probability one, and having done it once it does it infinitely often. For $d \geq 3$ it is transient: it returns with probability strictly less than one, visits the origin finitely many times, and then leaves forever.
The proof is one line, and the line is a convergence test. Let $G_d$ be the expected number of visits to the origin, counting the one at time zero. If $u$ is the probability of ever returning, then each visit is followed by another with probability $u$, so the visits are geometric and
An infinite $G_d$ forces $u = 1$. A finite one forces $u < 1$. So the whole theorem is about whether a sum converges, and the sum is over time:
After $n$ steps the walk is spread over a distance of about $\sqrt{n}$, so it is somewhere inside a ball of volume $n^{d/2}$, and the chance it is standing on any one particular site is about $n^{-d/2}$. Which makes the sum $\sum_n n^{-d/2}$ — and that diverges for $d \le 2$ and converges for $d \ge 3$.
That is the entire content. The dimension enters only as an exponent, and two is the boundary, and two is just barely on the safe side, because $\sum 1/n$ diverges only logarithmically. The plane keeps its drunks by a hair.
There is a nice corollary hiding in the geometry. In $d \le 2$ the walk keeps trampling its own path; in $d = 3$ it visits a fresh site on about $65.9\%$ of its steps, forever. The low-dimensional walk fills its world. The high-dimensional one threads through it and leaves most of it untouched.
The Number Took Another Eighteen Years
Pólya proved the dichotomy. He did not produce the 34%.
Getting an actual probability out of it means evaluating $G_3$, which is a triple integral over the lattice’s Fourier dual, and that had to wait for Watson in 1939. The value is one of the prettier constants in probability — four gamma functions at twenty-fourths:
which through equation (1) gives the pigeon’s chances: $u_3 = 0.3405373296\ldots$
You do not need the triple integral to compute these. Writing $1/(1-\varphi)$ as $\int_0^\infty e^{-t(1-\varphi)}dt$ and doing the Fourier integral first makes it factorise into $d$ identical copies of a Bessel function, and the whole thing collapses to one dimension:
Which is a thirty-second computation in any dimension you like. In four dimensions the walk comes home 19.3% of the time, in five 13.5%, in ten 5.6% — and the tail behaves exactly as it should, drifting toward $1/(2d)$, because in a very high-dimensional world the only realistic way back is to turn round immediately and retrace the step you just took.
Algorithm — Does the Drunk Get Home?
input: d, the number of directions to get lost in
# ---- the exact answer, collapsed to ONE dimension ----------
G(d) <- integral 0..inf of exp(-t) * BesselI0(t/d)^d dt
u(d) <- 1 - 1/G(d) # probability of EVER returning
For d <= 2 the integral DIVERGES and u = 1. That refusal to
converge is the theorem announcing itself, not an error.
I0(x) grows like exp(x), so I0(t/d)^d grows like exp(t) and
cancels the exp(-t) EXACTLY -- in exact arithmetic. In
floating point the integrand is inf/inf past t ~ 700 and the
answer is nan. Use the scaled Bessel i0e(x) = I0(x)*exp(-x):
then i0e(t/d)^d IS the whole integrand, with nothing left
over to overflow.
# ---- the check, sharing no code with the above -------------
simulate N paths for T steps:
pick an axis uniformly, pick a sign uniformly, move one
mark a path the first time it stands on the origin again
report the fraction marked
This rises toward u(d) and never arrives, because T steps is
not eternity. The gap is the answer being honest.
# ---- the twist: put a floor and a roof on the sky ----------
the same walk on Z^2 x {0..L-1}, with WALLS, not wrap-around:
a vertical step that would leave the slab is refused, and
the walk stays where it is
For EVERY finite L this is recurrent. Once the walk has mixed
across the thickness, the height carries no information and
the slab is two-dimensional at large scales.
return u(d), and the simulated fraction beside it
Where the Story Breaks
Here is the part the joke does not tell you.
A real bird does not fly in $\mathbb{Z}^3$. It is pinned between the ground and a few kilometres of usable altitude. That is not three-dimensional space — that is a slab: unbounded in two directions, finite in the third.
And a random walk on a slab is recurrent, for every finite thickness. Once the walk has mixed across the height — which takes about $L^2$ steps and then is over with — the vertical coordinate stops carrying any information, the return probability decays like $c/n$, and the sum diverges exactly as it does on the plane. A slab a thousand layers thick and a slab one layer thick are the same theorem with a different constant in front.
So the bird comes home. Put a ceiling on the sky — any ceiling, a kilometre, a hundred kilometres, whatever a pigeon can actually reach — and the pigeon is a man again, home with probability one.
Its freedom was never the flying. It was the ceiling it does not have.
The right-hand panel is the honest version of the claim. A simulation of finite length cannot show a probability arriving at one, and this one does not pretend to. What it shows is the thing that is visible in finite time: the open-sky walk has already finished — it lies on 0.3405 and it will lie there for eternity — while both ceilinged walks passed that line within twenty steps and are still climbing at twelve thousand.
It Is Not Really About Dimension Either
One more demolition, and then we can stop.
A random walk on a 3-regular tree — a branching graph, locally as thin as a piece of string — is transient. It never comes home. The tree has no dimension to speak of, so dimension cannot be the operative thing.
What actually decides it is how much room there is to get lost in at distance $r$. The lattice $\mathbb{Z}^d$ offers about $r^d$ places to be, and $r^2$ is the exact threshold between coming home and not. The tree offers exponentially many and blows past the threshold without needing a second dimension at all.
Chung and Fuchs later made the lattice part general: any random walk with mean zero and finite variance on $\mathbb{Z}^d$ is recurrent precisely when $d \le 2$. It is not about the step distribution, and it is not about the lattice. Pólya’s theorem is the case where the growth rate happens to be an integer you can point at — which is why it is the one that gets told with animals.
Pólya’s Own Version Is Better Than Mine
He did not find this by thinking about drunks.
He told it as a walking story. He was staying at a hotel, wandering the gardens to think, and kept blundering into the same engaged couple — repeatedly, awkwardly, often enough that he was sure they had decided he was following them. So he went back to his room and worked out how likely it is that two people wandering at random keep running into each other.
Treat the furniture of that story as the version he told rather than a verified itinerary — the shape of it is his and the gravel may have drifted in the retelling. But the mathematics is exactly the same question. Two independent walkers meeting is one walker returning to the origin, because the difference of two random walks is itself a random walk. The couple were in a garden, which is a plane, which is two-dimensional, which is recurrent.
He was always going to keep meeting them. With probability one, infinitely often, forever. It genuinely was not his fault.
Interested in applying these ideas to your work? Get in touch.