Monday, March 30, 2015

Intuitive Proofs

As I mentioned a few months ago, I briefly joined an undergraduate research seminar my freshman year at Cornell. In that seminar I was asked if a two-dimensional random walk on a lattice would return to the origin infinitely often. I said of course. The advisor was impressed until he asked about three-dimensional walks and I said they also hit the origin infinitely often. My intuition was wrong.

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.

4 comments:

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

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

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

      Delete
  2. I 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.

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

    ReplyDelete
  3. 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