Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let be the probability that a random walk on a d-D lattice returns to the origin. In 1921, Pólya proved that $p(1)=p(2)=1$ but $p(d)<1$ for $d>2$. http://mathworld.wolfram.com/PolyasRandomWalkConstants.html

I wonder what we can say about the probability for $d \to \infty$ In other words, if there is a closed formula or approximation which presents the limit of the probability for very big $d$? Does the limit exist?

Thank you in advance for any comments or approach to investigate the question.

share|improve this question
add comment

1 Answer

up vote 10 down vote accepted

The table in that Mathworld page suggests that $p(d) \rightarrow 0$ as $d \rightarrow \infty$. That page also gives a formula for $p(d)$ in terms of a definite integral: $$ p(d) = 1 - \left[ \int_0^\infty I_0(t/d)^d e^{-t} dt \right]^{-1}, $$ where $I_0$ is a "modified Bessel function" with power series $$ I_0(x) = \sum_{n=0}^\infty \frac{(x/2)^{2n}}{n!^2} = 1 + \frac{x^2}{2^2} + \frac{x^4}{8^2} + \frac{x^6}{48^2} + \cdots . $$ [For large $x$ it is known that $I_0(x) \sim (2\pi x)^{-1/2} e^x$, so the integrand decays as a multiple of $x^{d/2}$ for $x \rightarrow \infty$, and the integral is finite iff $d>2$.] Substituting the power series for $I_0(x)$ into the integral, and expanding termwise via $\int_0^\infty t^m e^{-t} dt = m!$, yields $$ 1 + \frac1{2d} + \frac3{4d^2} + \frac3{2d^3} + \frac{15}{4d^4} + \frac{355}{32d^5} + \cdots $$ (the coefficients in powers of $1/2d$ are OEIS sequence A105227). We then compute the asymptotic series $$ p(d) \sim \frac1{2d} + \frac1{2d^2} + \frac7{8d^3} + \frac{35}{16d^4} + \frac{215}{32d^5} + \cdots, $$ which seems consistent with the Mathworld table. The coefficients in powers of $1/2d$ are OEIS sequence A043546; as often happens, finding a few terms makes it easier to hunt down some of the literature. [Added later: so does posting on Mathoverflow; a comment to this answer by Folkmar Bornemann gives a reference dating back 55+ years

Montroll, Elliot W: Random walks in multidimensional spaces, especially on periodic lattices, J. Soc. Indust. Appl. Math. 4 (1956), 241–260 (MR0088110)

— thanks! Here's some gp code for this power series in $w = 1/2d$ and its coefficients, quite similar to Flajolet's Maple code reproduced in the OEIS entry:

N = 20
I1 = sum(n=0,N,x^n/n!^2,O(x^(N+1)));
Iw = subst(I1,x,w^2*x)^(1/(2*w));
g = sum(n=0,N,(2*n)!*polcoeff(Iw,n,x)) + O(w^(N+1));
p = 1 - 1/g
vector(N,n,polcoeff(p,n))

This returns

[1, 2, 7, 35, 215, 1501, 11354, 88978, 675569, 4175664, 1725333, -687775083, -19848956619, -438027976068, -8715988203509, -161989586455204, -2784493824166078, -41530410660307610, -406672888265416456, 4420077014249902362]

and gp readily computes it for $N$ as large as 50, and with some more effort even for $N=100$.]

The form of the asymptotic series can be explained as follows: for each $k=1,2,3,\ldots$, the probability of return to the origin in $2k$ steps is $O(d^{-k})$ as $d \rightarrow\infty$; so the probability of return by the $2k$-step gives $p(d)$ to within $O(d^{-(k+1)})$, and this estimate is a polynomial in $1/2d$ with integer coefficients. For example, the $k=1$ probability is $1/2d$ exactly; for $k=2$, add $2!/(2d)^2 - O(d^{-3})$; "etc.".

share|improve this answer
6  
I'd just like to add that it's relatively easy to see, using the electrical network theory, that the leading term is $1/2d$ which is the degree of vertices in $\mathbb{Z}^d$. –  Ori Gurel-Gurevich Dec 13 '11 at 6:57
3  
Indeed I was about to add that the $k$-th partial sum accounts (within $O(d^{-(k+1)})$ ) for the probability of returning by time $2k$. For example, for $k=1$ this probability is $1/2d$ exactly; for $k=2$, add $2!/(2d)^2 - O(d^{-3})$; "etc.". –  Noam D. Elkies Dec 13 '11 at 7:01
4  
Probably the earliest reference to this asymptotic expansion of $p(d)$ is: E. W. Montroll, Random walks in multidimensional spaces, especially on periodic lattices, J. Soc. Indus. Appl. Math. 4:241-260, 1956 (MR0088110). –  Folkmar Bornemann Dec 13 '11 at 8:14
    
Thank you very much!Thank you for the reference. @ Noam D. Elkies Thank you very much, amazing example and good to see how OEIS helps. I am not sure why the result is related to the cubic lattice but not other type of lattice (hexagonal etc)? Probably I've asked a "stupid" question, but would it be possible to explain it for me please? –  Mikhail Gaichenkov Dec 14 '11 at 13:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.