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