Random Walks

One blog I follow is GÖDEL’S LOST LETTER

In the post Do Random Walks Help Avoid Fireworks, Pip references George Polya’s proof that on regular lattices in one and two dimensions, a random walk returns to the origin infinitely many times, but in three dimensions, the probability of ever returning to the origin is strictly less than one.

He references a rather approachable paper explaining this by Shrirang Mare: Polya’s Recurrence Theorem which explains a proof of this matter using lattices of reisistors in an electrical circuit analogy.  The key is that there is infinite resistance to infinity in one or two dimensions, but strictly less than infinite resistance to infinity in three dimensions.

This is all fine, but there is another connection in science fiction. In 1959, E.E. “Doc” Smith’s The Galaxy Primes was published in Amazing Stories.

Our Heros have built a teleporting starship, but they can’t control where it goes.  The jumps appear long and random.  Garlock says to Belle:

“You can call that a fact. But I want you and Jim to do some math. We know that we’re making mighty long jumps. Assuming that they’re at perfect random, and of approximately the same length, the probability is greater than one-half that we’re getting farther and farther away from Tellus. Is there a jump number, N, at which the probability is one-half that we land nearer Tellus instead of farther away? My jump-at-conclusions guess is that there isn’t. That the first jump set up a bias.”

“Ouch. That isn’t in any of the books,” James said. “In other words, do we or do we not attain a maximum? You’re making some bum assumptions; among others that space isn’t curved and that the dimensions of the universe are very large compared to the length of our jumps. I’ll see if I can put it into shape to feed to Compy. You’ve always held that these generators work at random—the rest of those assumptions are based on your theory?”

Garlock is right – this is a three dimensional random walk and tends not to return to its starting place, but James is wrong when he says this isn’t in any of the books.  Polya proved it in 1921.