Deriving Polya’s Random Walk Constants It is a well known theorem of Pólya that a random walk in 1 or 2 dimensions has a probability of 1 of returning to the origin. However, the probability in the 3-dimensional case is given by a strange triple integral.
How is this integral derived?
 A: The integral for Polya's constant $P$ is derived as follows.  First you need a formula for $p(n)$, the probability that a random walk of length $n$ starting at the origin ends at the origin in $\mathbb{Z}^3$.  Then the probability $P$ of returning to the origin at least once satisfies $1 + P + P^2 + \cdots = \sum_{n=0}^\infty p(n) = u(3) = \frac{1}{1-P}$, so $P = 1-\frac{1}{u(3)}$.
The main thing is to give a formula for $p(n)$.  Namely it is the average value
of $f(x,y,z)^n$, where $f(x,y,z) = \frac{\cos(x) + \cos(y) + \cos(z)}{3}$ and $x,y,z$ each range in $[0,2\pi]$.  Once you know this, the sum of $p(n)$ is the average value of $1+f+f^2 + \cdots = \frac{1}{1-f}$, which gives a single integral formula for $u(3)$.
Now where does the formula for $f(x,y,z)$ come from?  Consider first the simpler case of a random walk on $\mathbb{Z}$.  Then the same formula works with $f(x) = \cos(x)$, that is, the probability of return to the origin after $n$ steps in the average value of $\cos(x)^n$.  To see this write $\cos(x) = \frac{z+z^{-1}}{2}$, where $z = e^{ix}$.  Then $\cos(x)^n$ is a sum of powers $z^i$, each times the probability that a random walk of length $n$ ends in position $i$.  The average of $z^i$ is zero unless $i=0$.  The same reasoning applies in dimension 3 using $f(x,y,z)$.
