Pólya's Random Walk Constants

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Let $p(d)$ be the probability that a Random Walk on a $d$-D lattice returns to the origin. Pólya (1921) proved that

$$p(1)=p(2)=1,$$ (1)

but

$$p(d)<1$$ (2)

for $d>2$. Watson (1939), McCrea and Whipple (1940), Domb (1954), and Glasser and Zucker (1977) showed that

$$p(3)=1-{1\over u(3)} = 0.3405373296\ldots,$$ (3)

where

$$u(3) = {3\over(2\pi)^3}\int_{-\pi}^\pi \int_{-\pi}^\pi \int_{-\pi}^\pi {dx\,dy\,dz\over 3-\cos x-\cos y-\cos z}$$ (4)

$$= {12\over\pi^2} (18+12\sqrt{2}-10\sqrt{3}-7\sqrt{6}\,)\{K[(2-\sqrt{3}\,)(\sqrt{3}-\sqrt{2}\,)]\}^2$$ (5)

$$= 3(18+12\sqrt{2}-10\sqrt{3}-7\sqrt{6}\,)\left[{1+2\sum_{k=1}^\infty \mathop{\rm exp}\nolimits (-k^2\pi\sqrt{6}\,)}\right]^4$$ (6)

$$= {\sqrt{6}\over 32\pi^3}\Gamma({\textstyle{1\over 24}})\Gamma({\te... ...yle{5\over 24}})\Gamma({\textstyle{7\over 24}})\Gamma({\textstyle{11\over 24}})$$ (7)

$$= 1.5163860592\ldots,$$ (8)

where $K(k)$ is a complete Elliptic Integral of the First Kind and $\Gamma(z)$ is the Gamma Function. Closed forms for $d>3$ are not known, but Montroll (1956) showed that

$$p(d)=1-[u(d)]^{-1},$$ (9)

where

$$u(d) = {d\over (2\pi)^d} \underbrace{\int_{-\pi}^\pi\int_{-\pi}^\pi\cdot... ...i}^\pi}_d \left({d-\sum_{k=1}^d \cos x_k}\right)^{-1}\,dx_1\,dx_2\,\cdots\,dx_d$$

$$= \int_0^\infty \left[{I_0\left({t\over d}\right)}\right]^d e^{-t}\,dt,$$ (10)

and $I_0(z)$ is a Modified Bessel Function of the First Kind. Numerical values from Montroll (1956) and Flajolet (Finch) are

$d$	$p(d)$
4	0.20
5	0.136
6	0.105
7	0.0858
8	0.0729

See also Random Walk

References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/polya/polya.html

Domb, C. ``On Multiple Returns in the Random-Walk Problem.'' Proc. Cambridge Philos. Soc. 50, 586-591, 1954.

Glasser, M. L. and Zucker, I. J. ``Extended Watson Integrals for the Cubic Lattices.'' Proc. Nat. Acad. Sci. U.S.A. 74, 1800-1801, 1977.

McCrea, W. H. and Whipple, F. J. W. ``Random Paths in Two and Three Dimensions.'' Proc. Roy. Soc. Edinburgh 60, 281-298, 1940.

Montroll, E. W. ``Random Walks in Multidimensional Spaces, Especially on Periodic Lattices.'' J. SIAM 4, 241-260, 1956.

Watson, G. N. ``Three Triple Integrals.'' Quart. J. Math., Oxford Ser. 2 10, 266-276, 1939.