33 years later I'd like to give the right intuition. This is rough intuition, not a proof, and I'm sure none of this is original with me.

In a 1-dimensional random walk, you will be at the origin on the nth step with probability about 1/n

^{0.5}. Since the sum of 1/n^{0.5}diverges this happens infinitely often.
In a 2-dimensional random walk, you will be at the origin on the nth step with probability about (1/n

^{0.5})^{2}= 1/n. Since the sum of 1/n diverges this happens infinitely often.
In a 3-dimensional random walk, you will be at the origin on the nth step with probability about (1/n

^{0.5})^{3}= 1/n^{1.5}. Since the sum of 1/n^{1.5}converges this happens finitely often.
I really appreciate this intuition. Before, all I had was a vague idea that 3-dimensions was too "sparse" but 2-dimensions wasn't, which was pretty unsatisfying.

ReplyDeleteAny chance this intuition can generalize to biased random walks? (I don't see it, but maybe someone else does...)

A guess at how to try it: consider only the direction you're more biased towards, since you're more likely to get lost that way.

DeleteI had asked a similar question on cstheory a while back, and the intuition you describe is confirmed in even more detail by the answers (and the linked MO question). In other words, even "2+eps" dimensional walks are transient.

ReplyDeletehttp://cstheory.stackexchange.com/questions/8058/drunken-birds-vs-drunken-ants-random-walks-between-two-and-three-dimensions

This is explored in great detail in the book "Random Walks and Electrical Networks" by Peter Doyle and J. Laurie Snell. (now available free via a GNU FDL on the web.)

ReplyDelete