Variations on the drunken-bird theorem, and real-world sightings

God Plays Dice exists in the real world!

My department traditionally has dinner for all the graduate students on the day before classes start. (This is preceded by the chair of the graduate program giving the annual ritual reminder of how the program is structured; I was basically told I should take some classes, teach my class, and do some research.) Anyway, I was waiting for dinner, and one of the new grad students got to talking, and I introduced myself, and he said "oh, are you the one who writes God Plays Dice?" Since you're reading this, you know I am. Someone said that he knew of two math blogs -- mine and Terence Tao's. Obviously this isn't saying that I'm as good a mathematician as him, but it's good company.

Anyway, we got to talking about how areas like combinatorics and probability are often perceived as "easier" than, say, algebra or analysis because the problems can be stated in terms that someone without much training can understand, even if the proofs aren't simple.

This led to me telling the joke about how "a drunk man always finds his way home, but a drunk bird can get lost forever". This is the colloquial statement of the following theorem about random walks. Consider a person who starts at the point (0, 0), and at each step of time takes a step to the north, east, south, or west with equal probability -- those are steps of (0, 1), (1, 0), (0, -1), or (-1, 0), respectively.¹ In order to be back at the origin after some number of steps, 2n, there must have been an equal number of up and down steps (say m of each) and an equal number of left and right steps (say n of each). Thus the number of ways that this can occur is



which can be rewritten as



by rearranging the factorials. Now, to do this sum, think about choosing n things out of 2n. To do this, we can choose m things from the first n, and then another n-m things from the remaining n; this gives the well-known identity



and thus the number of ways that we can be back at the origin after 2n steps is in fact . This is approximately 4²ⁿ/(π n) as can be seen by Stirling's approximation. Each path occurs with probability 4^-2n, and so the probability of being back at the origin after time 2n is proportional to 1/n. Since Σ_n 1/n diverges, the expected number of returns to the origin is infinite; this means (in this particular case; there's a lemma I'm not writing out) that the probability of returning to the origin is 1.
(This is basically following the exposition in Section 3.2 of Probability: Theory and Examples, third edition, by Rick Durrett.)

In three dimensions, though, we get something proportional to n^-3/2 there, and Σ_n 1/n^3/2 converges, so the expected number of returns to the origin is finite; this implies (and I'm sweeping some details under the rug) that there's a chance of the random walk getting away forever. The two-dimensional case corresponds to the drunk man; the three-dimensional case corresponds to the drunk bird.

So where's the line between "always finds his way home" and "gets lost forever"? It seems to me that this should be at 2+ε dimensions, since that's what we need to make the sum convergent, but I don't know if anyone's studied random walks on fractal spaces. But this ε has to be fairly large; we came up with two examples, one on what one might call "2+ε" dimensions and one on "3-ε" dimensions. Both of these are transient, which is basically the technical term corresponding to "gets lost forever". A "recurrent value" of a random walk on R^d is one for which the random walk almost surely gets arbitrarily close to that point infinitely often; a random walk is called "recurrent" if it has at least one recurrent value (and then, in fact, all possible values are recurrent), otherwise transient.

The (2+ε)-dimensional example is a random walk on Z² × [-n, n] for some small integer n; essentially, this is a random walk on a slab. (I'm not particularly worried about how we handle the boundaries; any reasonable way will do.) This random walk ought to be recurrent; the random walker (let's call it a "fish", swimming around in an ocean which is of finite depth), starting at (0, 0, 0), will return to points of the form (0, 0, k) infinitely often. At each of those times, the fish has third coordinate zero with some probability on the order of 1/2n; 1/2n of infinity is still infinity.

The (3-ε)-dimensional example is a random walk on Z² × [0, &infty;), which actually corresponds better to the "drunk bird" because we can take the xy-plane to be the surface of the earth. One can invoke a sort of "reflection principle" here; this can be viewed as a random walk on Z³ where we've identified points which are mirror images across the xy-plane with each other. This lets us conclude that the random walk is transient. However, the reflection principle handles the boundary condition "wrong"; the natural thing to do when at a point (x, y, 0) is to allow steps to (x ± 1, y, 0), (x, y ± 1, 0), and (x, y, 1) with equal probability. So we have a probability 1/5 of leaving the xy-plane, while in the reflection-principle version that probability is 1/3. This gives the plane a certain "stickiness", and I assume this means that the random walk has a larger expected number of returns to the origin, but that number should still be finite.

1. In combinatorics, there is the convention of referring to, say, the "northeast" or "southwest" part of a drawing, which corresponds to how those directions look on a map. Mathematicians who aren't familiar with this convention find it strange, but for some reason "northeast" seems to flow a lot better than "upper right".