Symmetric Random Walk on n-Dimensonal Integer Lattice From: flajolet@alfleila.inria.fr (Philippe Flajolet) Newsgroups: sci.math.research Subject: Re: Symmetric Random Walk on n-Dimensonal Integer Lattice Date: 10 Jul 1995 12:42:35 GMT Organization: INRIA-Rocquencourt In an earlier article, asimov@nas.nasa.gov (Daniel A. Asimov) writes: |> In Feller, volume I, it is mentioned that the symmetric random walk on |> the integer lattice in 1 or 2 dimensions has probability = 1 of |> eventually returning to the origin, but in 3 dimensions |> the probability is only .35.... |> |> Is there a precise expression, or at least an asymptotic formula, for |> this probability P(n) as a function of dimension n ??? |> |> Feller indicates an infinite series that gives P(n), but I don't see |> a simple way to calculate its value to 4 or 5 decimal places, |> which I would like to do. |> |> Any references would be appreciated. |> |> Daniel Asimov |> NASA Ames Research Center |> asimov@nas.nasa.gov I propose below an asymptotic formula and also an exact formula involving an integral of Bessel functions (the latter result is classical, I think!) The probability of ever returning to the origin in d-dimensional space is 1 P(d) = 1 - ------------------------------- infinity / | d (- t) | j(1/2 t/d) E dt | / 0 where j(z) is a modified Bessel function infinity ----- (2 n) \ z j(z) = ) ------ / 2 ----- (n!) n = 0 1. LOOPS. Let b_{2n}={2n choose n} and b_{2n+1}=0 be the number of 1-dimensional walks that start and end at 0 ("loops"). The exponential generating function [EGF} of such walks satisfies infinity ----- n \ b[n] z ) ------- = j(z) / n! ----- n = 0 Let W_n be the number of walks from 0 to 0 (loops that may also touch 0 at intermediate stages) in d-dimensional space. Then the corresponding EGF is infinity ----- n \ W[n] z d ) ------- = j(z) / n! ----- n = 0 a fact that is simply checked by means of the multinomial convolutions implied by this relation on EGF's. The corresponding ordinary generating function [OGF] obtains by the Laplace transform: infinity infinity ----- / \ n | d w(z) := ) W[n] z = | exp(- t) j(z t) dt / | ----- / n = 0 0 2. PRIMITIVE LOOPS. Let S_n be the number of "simple" loops (primitive loops, that never touch 0 except at their end-points) of length n. Then, infinity ----- \ n 1 s(z) := ) S[n] z = 1 - ---- / w(z) ----- n = 0 since it is more or less obvious that w(z)=1/(1-s(z)) [i.e., a loop is a sequence of primive loops]. (Note: It is an amusing exercise to determine the asymptotics of the Taylor coefficients of s(z) when d=2). 3. PROBABILITIES. The probability of touching 0 for the first time at step n is S[n]/(2d)^n. Thus, the probability of ever returning to 0 is by summing over n: 1 1 s(---) = 1 - ------ 2 d 1 w(---) 2 d and the result follows. 4. EXACT COMPUTATIONS. The integral is slowly convergent as are the Taylor series of s(z), w(z), etc at z=1. Roughly the decay is like n^{-d/2} for the series and t^(-d/2) for the integral. Not too good for precise numerical estimates! 5. ASYMPTOTICS. Assuming (without proof!) the Laplace method for integrals to work, a simple Maple program will give you an asymptotic expansion as a function of d, as follows; walk:=proc(order) local n,j; option trace; j:=sum(t^(2*n)/(2*d)^(2*n)/n!^2,n=0..order); eval(subs(O=0,asympt(exp(d*log(j)),d,order+2)))*exp(-t); 1-1/int(",t=0..infinity); asympt(asympt(",d,2*order+5),d,order+1); end; For instance, walk(6) will give the expansion: 1 1 7 35 215 1501 1 --- + ---- + ---- + ----- + ----- + ----- + O(----) 2 d 2 3 4 5 6 7 2 d 8 d 16 d 32 d 64 d d which instantiates to 0.34 when d=3. There is a combinatorial meaning for the terms in this expansion: for instance 1/(2d) is expected since in high dimension your greatest chance to return is to make one step with the next step being just the reverse step (this has probability 1/(2d)), etc. The corresponding "correction" series however does not appear in Sloane's "Encyclopedia of Integer Sequences", 2 3 4 5 6 7 8 w + 2 w + 7 w + 35 w + 215 w + 1501 w + 11354 w + 88978 w 9 10 + 675569 w + 4175664 w + ... The asymptotic series is divergent, unfortunately! Rough computations indicate that: P(4)=0.20, P(5)=0.136, P(6)=0.105, P(7)=0.0858, P(8)=0.0729, etc. I hope to report on exact numerical computations later. Philippe Flajolet -- --------------------------------------------------- Philippe Flajolet Algorithms Project, INRIA Rocquencourt F-78153 Le Chesnay (France) Tel: +33 (1) 39.63.56.26 / 39.63.54.43 [secr.] Fax: +33 (1) 39.63.53.30 E-mail: Philippe.Flajolet@inria.fr ---------------------------------------------------