This mathematician proved the random walk theorem to clear his name as a lurker

More than 100 years ago, Hungarian-born mathematician George Pólya found himself trapped in a spiral of social awkwardness. A professor at the Swiss Federal Institute of Technology in Zurich, he liked to walk alone in the woods outside the city. During one of these hikes, he came across one of his students and the student’s fiancée. Then, some time later, still wandering aimlessly, he came across the couple again. And then later, he did it again.

Writing about this experience in an essay published in a 1970 book, Pólya recounted: “I don’t remember how many times [this happened]but certainly far too often and I felt embarrassed: I seemed to be snooping, which was, I assure you, not the case.

Desperate to clear his name as a prowler, Pólya did what any good mathematician would do: he generalized the problem. Are two wanderers mathematically destined to cross paths? Its original formulation simplified the picture by considering only a single walker on an infinite grid. Every second, the walker randomly chooses the direction of the compass, independently of previous steps. Pólya’s mathematical goal was to determine the probability that the walker would eventually return to his starting point. This answer turns out to be equivalent to the probability that two walkers starting from the same place will meet again one day. He discovered that if a walker wanders forever, he will return to their starting point.

On supporting science journalism

If you enjoy this article, please consider supporting our award-winning journalism by subscription. By purchasing a subscription, you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

The answer not only absolved him, but also revealed a fundamental divide in how the laws of chance interact with physical space. Pólya’s calculations showed that on a two-dimensional surface (like a forest floor), a random walker is destined to return to their starting point, but in three-dimensional space, that person is more likely to never return to the starting point. The discovery is found in all areas of chemistry and biology, even explaining how certain molecules efficiently find the appropriate receptor on the surface of cells.

As described in the 2019 fifth edition of Probability: theory and examplesby Rick Durrett, mathematician Shizuo Kakutani summed up the theorem with a witticism: “A drunk man will eventually find his way home, but a drunk bird can get lost forever.” »

Here, “drunk bird” refers not to a buzzing buzzard, but to a random process on a three-dimensional grid (imagine a jungle gym). Every second, the bird chooses between north, south, east, west and up or down, at random, regardless of previous choices. Pólya proved that if you walk forever randomly through an infinitely extensive urban network, you will not only be guaranteed to return to your starting point, but you will also reach each placed on the grid an infinite number of times. However, if you perform the same process in an infinite jungle gym, you will have almost a 66% chance of never returning to where you started. Likewise two wanderers in a jungle gym may never meet, but two wanderers on a flat surface must meet an infinite number of times – Pólya was not lacking in social grace; he lacked a third dimension to escape into.

Even the one-dimensional case, which behaves mathematically like two dimensions, has concrete implications. Imagine arriving at a casino with $500 in your pocket. One table offers a game with a 50 to 50 chance of winning (better than what you’ll find in Monte Carlo). If you continue to play, no matter what betting strategy you use, you will eventually go bankrupt. This is because we can model the game as a random walk on a number line. You start at 500 and after each round of play you move right or left on the line with equal chance. Pólya tells us that, just like in the two-dimensional case, if you play long enough you will inevitably explore the entire number line. This includes 0, in which case you will go bankrupt. Mathematicians call this “gambler ruin,” and it explains why they recommend quitting while you’re ahead or, better yet, not playing at all.

Why do random walks suddenly change character between two and three dimensions? Although three dimensions naturally provide more space to move around than two, that alone is not enough of an explanation. After all, two dimensions provide more space than one, but both exhibit the same behavior.

If you do a random walk over a finite number of steps we will call t, then you generally won’t stray further than √t (the square root of t) far from the origin. Concretely, after 100 steps, most walkers will find themselves only 10 steps, or √100, from the start. Intuitively, random walks tend to hover near the origin because successive steps can cancel each other out (a walker who takes a step to the east followed by a step to the west has not made any progress at all). Mathematically, √t is equal to standard deviation (a statistical measure of the distribution of a set of values) of the distance from the origin of a t-random walk step.

In other words, if many distinct walkers all start at the same location and move independently, then plotting their distances from the origin after t steps would look like a bell curve centered at 0 and with standard deviation √t. Deriving the standard deviation for the one-dimensional case is an accessible exercise if you have taken a statistics course: try it.

This √t the figure is valid in all dimensions and is the key to understanding Pólya’s theorem. Think of it as the radius of the region in which a walker will explore t measures. This radius has very different implications depending on the dimensions, because the number of dimensions determines whether it is length, area, or volume. A line segment of radius √t has a size of the order of √t; a circle of radius √t has a size of the order of t (the area of ​​a circle is proportional to the square radius); and a sphere of radius √t has a size of the order of t^1.5 (the volume of a sphere is proportional to the radius cubed).

But whatever its size, a walker who takes steps cannot visit more than t distinct points. In one dimension, the number of steps exceeds the size of the explored region (t > √t), forcing the walker to constantly retrace his steps. In two dimensions, the number of steps corresponds to the size of the region (t = t), allowing the walker to eventually cover the grid, albeit thinly. But in three dimensions, the space is vast compared to the number of steps (t < t^1.5), leaving most points unvisited and the origin unlikely to be revisited.

Of course, the real world rarely resembles a perfect grid, and birds don’t toss coins with every flap of their wings. However, this contrast between two- and three-dimensional walks presents surprisingly interesting practical issues in the natural sciences. A compelling example concerns how chemicals react in our bodies. Researchers often use random walks to model molecules diffusing through another substance. Consider the example of a hormone trying to find a specific receptor on the surface of a cell. It has no referral mechanism, so such reactions occur during chance encounters.

The hormone could wander aimlessly in the three-dimensional fluid surrounding the cell until it hits its target. Instead, many molecules bind weakly to any first point to the cell membrane. Once attached, they slide on the two-dimensional surface of the membrane until they reach their target. This reduction in dimensionality transforms slow three-dimensional walking into efficient two-dimensional walking.

The next time you encounter someone you’ve been avoiding, try turning the encounter into a deep mathematical thought process. It’s much better than hiding behind a tree.