# 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?

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)$$.

Start with dimension 1 and denote $$A_j$$ the probability that the walk returns to the origin, when it starts at the state $$j$$. We have $$A_j = \frac12 (A_{j+1} + A_{j-1}),\qquad j\neq 0$$

and $$A_0 = 1$$ by definition (we can reimagine that if the walk returns to the origin, it stays there forever, the ratio of those paths versus all the paths must be exactly the probability of returning to the origin from your original problem).

The probability of return can be evaluated as $$P = \tfrac12(A_1+A_{-1})$$. Thus, we can write more compactly

$$A_j = \frac12 (A_{j+1} + A_{j-1}) + (1-P)\delta_{0j}.\tag{1}$$

Denote $$A(x)$$ a $$2\pi$$-periodic function having $$A_j$$ as its Fourier series coeficients. That is

$$A(x) = \sum_{j\in \mathbb{Z}} A_j e^{i j x}.$$

Summing $$(1)$$ with $$e^{i j x}$$, we get

$$A(x) = \frac12 (e^{-ix} + e^{ix})A(x) + (1-P) = A(x)\cos x + (1-P),\tag{2}$$

so

$$A(x) = \frac{(1-P)}{1+\cos x}.$$

Note that as $$A_j$$ are the coefficients of $$A(x)$$ function, we can write

$$A_j = \frac{1}{2\pi} \int_{0}^{2\pi} A(x) e^{-ijx} \, \mathrm{d}x,\tag{3}$$

For $$j=0$$, we get

$$1 = A_0 = \frac{1}{2\pi} \int_{0}^{2\pi} \frac{(1-P)}{1-\cos x} \, \mathrm{d}x$$

Thus

$$P = 1 - 2\pi \left(\int_{0}^{2\pi} \frac{\mathrm{d}x}{1-\cos x} \right)^{-1}\tag{4}.$$

In $$d$$ dimensions, $$(2)$$ generalises as

$$A(x_1,\ldots,x_d) = \frac{A(x_1,\ldots,x_d)}{d}(\cos x_1 + \cos x_2 + \cdots + \cos x_d) + (1-P),$$

and the Fourier coefficient formula $$(3)$$ generalises as

$$A_{j_1,\,\ldots,j_d} = \frac{1}{(2\pi)^d} \int_{\left[0,2\pi\right]^d} A(x) e^{-ij_1 x_1}\cdots e^{-ij_d x_d} \, \mathrm{d}x_1\cdots\mathrm{d}x_d,$$

so $$(4)$$ should generalise as

$$P = 1 - (2\pi)^d \left(\int_{\left[0,2\pi\right]^d} \frac{\mathrm{d}x_1\cdots \mathrm{d}x_d}{1-\frac{1}{d}\left(\cos x_1 + \cdots + \cos x_d\right)} \right)^{-1}\tag{5}.$$

which is the cosine integral you are looking for.