The Teetotaler’s Walk

by Brian Hayes

Published 22 February 2010

Writing about Pólya’s recurrence theorem led me to pick up Gerry Alexanderson’s book The Random Walks of George Pólya. He tells a sweet anecdote about the origin of the theorem.

The random walk is sometimes called the drunkard’s walk, but Pólya’s musings on the subject were not inspired by a disorienting pub crawl. On the contrary, the idea came to him while he was living at the Kurhaus Zürichberg, which Alexanderson notes was founded as a temperance hotel. (It seems to be a somewhat different establishment now, and probably beyond the means of a Privatdozent.)

Alexanderson describes the incident that led Pólya to the recurrence theorem:

There was a particular wooded area near the hotel where he enjoyed taking extended walks while thinking about mathematics. He would carry pencil and paper so he could jot down ideas as they came to him. Some students also lived at the Kurhaus and Pólya got to know some of them. One day while out on his walk he encountered one of these students strolling with his fiancée. Somewhat later their paths crossed again and even later he encountered them once again. He was embarrassed and worried that the couple would conclude that he was somehow arranging these encounters. This caused him to wonder how likely it was that walking randomly through paths in the woods, one would encounter others similarly engaged. This led to one of his most famous discoveries, his 1921 paper on random walk, a phrase used for the first time by Pólya.

It’s interesting that the question raised by those embarrassing woodland encounters differs from the usual statement of the recurrence theorem, which talks about a single walker’s return to the point of origin. The answer is the same, however. In an appendix to the Alexanderson book, K. L. Chung mentions an easy proof of this equivalence: Suppose two walkers begin together at A and run into each other again at B. Nothing about the statistics of a random walk changes if you reverse the direction of all the steps. Thus the probability of the rencontre at B is the same as that of one walker going from A to B and then back to A again.

The illustration below shows the paths of two random walkers that meet three times (green circles) after leaving the origin, supporting the plausibility of Pólya’s claim that he was not stalking those young lovers in the woods.