Pólya's Random Walk Constants at infinity - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T10:00:01Z http://mathoverflow.net/feeds/question/83317 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83317/polyas-random-walk-constants-at-infinity Pólya's Random Walk Constants at infinity Mikhail Gaichenkov 2011-12-13T06:11:48Z 2011-12-13T17:15:00Z <p>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)&lt;1$ for $d>2$. <a href="http://mathworld.wolfram.com/PolyasRandomWalkConstants.html" rel="nofollow">http://mathworld.wolfram.com/PolyasRandomWalkConstants.html</a></p> <p>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?</p> <p>Thank you in advance for any comments or approach to investigate the question.</p> http://mathoverflow.net/questions/83317/polyas-random-walk-constants-at-infinity/83321#83321 Answer by Noam D. Elkies for Pólya's Random Walk Constants at infinity Noam D. Elkies 2011-12-13T06:37:40Z 2011-12-13T17:15:00Z <p>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 <strong>iff</strong> $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 <a href="https://oeis.org/A105227" rel="nofollow">OEIS sequence A105227</a>). 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 <a href="https://oeis.org/A043546" rel="nofollow">OEIS sequence A043546</a>; 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</p> <blockquote> <p>Montroll, Elliot W: Random walks in multidimensional spaces, especially on periodic lattices, <em>J. Soc. Indust. Appl. Math.</em> <strong>4</strong> (1956), 241–260 (MR0088110)</p> </blockquote> <p>— thanks! Here's some <strong>gp</strong> code for this power series in $w = 1/2d$ and its coefficients, quite similar to Flajolet's Maple code reproduced in the <a href="https://oeis.org/A043546" rel="nofollow">OEIS entry</a>:</p> <pre><code>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)) </code></pre> <p>This returns</p> <pre><code>[1, 2, 7, 35, 215, 1501, 11354, 88978, 675569, 4175664, 1725333, -687775083, -19848956619, -438027976068, -8715988203509, -161989586455204, -2784493824166078, -41530410660307610, -406672888265416456, 4420077014249902362] </code></pre> <p>and <strong>gp</strong> readily computes it for $N$ as large as 50, and with some more effort even for $N=100$.]</p> <p>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.".</p>