9
$\begingroup$

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.

$\endgroup$

1 Answer 1

13
$\begingroup$

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

$\endgroup$
4
  • 6
    $\begingroup$ 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$. $\endgroup$ Dec 13, 2011 at 6:57
  • 3
    $\begingroup$ 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.". $\endgroup$ Dec 13, 2011 at 7:01
  • 4
    $\begingroup$ 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). $\endgroup$ Dec 13, 2011 at 8:14
  • $\begingroup$ 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? $\endgroup$ Dec 14, 2011 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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