04 September 2007

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.1 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

\sum_{m=0}^n {(2n)! \over m! m! (n-m)! (n-m)!}

which can be rewritten as

{2n \choose n} \sum_{m=0}^n {n \choose m} {n \choose n-m}

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

{2n \choose n} = \sum_{m=0} {n \choose m} {n \choose n-m}

and thus the number of ways that we can be back at the origin after 2n steps is in fact {2n \choose n}^2. This is approximately 42n/(π 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/n3/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 Rd 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 Z2 × [-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 Z2 × [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 Z3 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".


Anonymous said...

Bleh. Everybody knows Tao's, more because of his Fields Medal than because of any math-blog cred. Go tell all the first-years about the n-Category Café, the Everything Seminar, the Secret Blogging Seminar...

(oh, and maybe The Unapologetic Mathematician, while you're at it)

Michael Lugo said...

Yeah, I know. They'd heard of the Everything Seminar and the Secret Blogging Seminar. More than anything, I was amused by the fact that I was being mentioned in the same sentence as Tao.

come to think of it, I really should add some more links.

Anonymous said...

I remember as an undergrad hearing the drunk flatlander/spacelander thing, and also hearing that the transition between returning to your home and not happens in dimension 2.5. I have never seen a proof of this and I'm not even quite sure how to formalize the idea (which 2.5 dimensional space?). I also don't know if random walks return home in 2.5 dimensions or not.

Can anybody prove or verify any of these claims?