From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Infinite walk on a 3D lattice
Date: 8 Oct 1998 22:36:22 GMT

In article <6veq2r$dg9$1@cantuc.canterbury.ac.nz>, mathwft@math.canterbury.ac.nz (Bill Taylor) writes:

|> However, that there should be an essential difference between *2* and *3* -D
|> is remarkable and unexpected.  I know of know "geometric" argument that
|> would simple-mindedly convince one that the 2D walk is recurrent, though I
|> have asked on sci.math several times.  One would (*I* would) have expected 
|> it to be transient, like the 3D.

I this one geometric or simple-minded enough for you?
It's convenient to consider the variant of the 2D walk that has you take both 
a horizontal and a vertical step at the same time, thus executing an ordinary
random walk on a larger lattice at a 45 degree angle to the first (the black
squares on a checkerboard).  This makes your x and y coordinates independent
random variables, which they are not for the ordinary 2D walk.
Now the probability that x=0 at time 2n is binomial(2n,n)/2^(2 n) which is
approximately const/sqrt(n).  

A "simple-minded" plausibility argument for this is that the variance of x increases by 1 at each step, so the standard deviation
is sqrt(n), i.e. there should be something like sqrt(n) 
possible values that have comparable probabilities, so 
about 1/sqrt(n) for each.

Thus the probability that both x=0 and y=0 at time 2n is the square of this
probability, which is approximately const/n.

Now the expected number of returns to the origin is the sum of these
probabilities, which is infinity since the harmonic series diverges.

But if the probability of ever returning to the origin was p < 1, the
expected number of returns would be the finite number p/(1-p) (think
of a sequence of independent coin-flips with probability p of heads: the
expected number of consecutive heads is p/(1-p)).

In 3D, the analogous calculation (actually for a walk on a body-centred cubic
lattice) shows that the probability of return at time 2n is approximately
const/n^(3/2).  But this time the series is convergent, so the expected
number of returns is finite, and therefore the probability of ever returning
must be less than 1.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2