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/n0.5. Since the sum of 1/n0.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/n0.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/n0.5)3 = 1/n1.5. Since the sum of 1/n1.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