info prev up next book cdrom email home

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

\end{displaymath} (1)

\end{displaymath} (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,
\end{displaymath} (3)


$\displaystyle u(3)$ $\textstyle =$ $\displaystyle {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)
  $\textstyle =$ $\displaystyle {12\over\pi^2} (18+12\sqrt{2}-10\sqrt{3}-7\sqrt{6}\,)\{K[(2-\sqrt{3}\,)(\sqrt{3}-\sqrt{2}\,)]\}^2$ (5)
  $\textstyle =$ $\displaystyle 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)
  $\textstyle =$ $\displaystyle {\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)
  $\textstyle =$ $\displaystyle 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
\end{displaymath} (9)


$\displaystyle u(d)$ $\textstyle =$ $\displaystyle {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$  
  $\textstyle =$ $\displaystyle \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


Finch, S. ``Favorite Mathematical Constants.''

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.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein