Better Know a Theorem
I gave an informal talk today on random walks. (Blog entry pre-dated to actual talk date.) In a random walk on the d-dimensional grid, we start at the origin of Zd. At each step, pick one of the d coordinates (uniformly) at random, then flip a coin, and depending on the outcome add +1 or -1 to that coordinate of your position.
In 2 dimensions there is 0 probability of never returning to the origin, while in 3 dimensions there is a positive probability of never returning to the origin. This theorem is due to Polya in 1921. The nicest proofs of this fact seem to be contained in this paper by Doyle and Snell.
I was thinking of the following today. What if the random walk is a branching process? Consider the random 3D grid walk, but after 100 steps, the walker clones itself and then the two random walkers walk independently. After every further 100 steps, all existing walkers are again cloned. Is the probability that no walkers return to the origin still positive?
Someone pointed out during the talk that a volume argument probably ensures that the origin is eventually hit with probability one: the number of walkers grows exponentially in time, but most of them are a polynomial distance from the origin.
Filed under: b.k.a.t., geometry, probability, randomness | Leave a Comment