# Pólya's Random Walk Constants at infinity

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.

-

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.".

-
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
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
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