A problem introduced to me by Professor Peter Yum. Consider random walk on integers. The simplest one is on

\[\mathbb{Z}=\{\cdots, -2, -1, 0, 1, 2, \cdots\}\]

and we start on 0 at step 0. The random walk proceed y flipping a coin at each step to decide to go left or right.

We can also define the counterpart on a higher dimensional lattice \(\mathbb{Z}^d\), which we decide on each step one of the \(2d\) possible direction to go. We always start with the position 0 in such lattice and concern whether we will return to 0 (aka equalization) in some future step. Formally, the random walk is defined as

\[S_n = S_0 + \sum_{i=1}^n X_i\]

where \(S_n\in\mathbb{Z}^d\) is the position of the random walk at step \(n\) and \(S_0=0\). \(X_i = \pm e_j\) is the direction taken at each step \(i\) where \(e_j\) is the \(d\)-dimensional standard basis vector, i.e. only the \(j\)-th element of the vector is 1 and all other elements are 0.

If at each step, all direction can be taken at equal probability, i.e.

\[\Pr[X_i = e_j] = \Pr[X_i = -e_j] = \frac{1}{2d}\quad\forall j=1,\cdots,d\]

the random walk is called symmetric.

Polya studied this and some of the following are developed:

We define \(u_n\) to be the probability that the random walker returned to 0 at step \(n\). For any lattice, only \(u_{2n}\) makes sense as no random walk can return to 0 in odd number of steps. We define \(u_0 = 1\) as the random walk starts at 0.

We further define \(f_n\) to be the probability that the random walk returns to 0 for the first time. And we define \(f_0=0\) for notational convenience (and at step 0 is not really a return). With this, we can define the probability that a random walk will ever return to 0 as

\[f = \sum_{n=0}^{\infty} f_n = \sum_{n=0}^{\infty} f_{2n}\]

Considering the definition of \(u_n\) and \(f_n\), we have the following relations are established:

\[\begin{align} u_1 &= f_0 u_1 + f_1 u_0 \\ u_2 &= f_0 u_2 + f_1 u_1 + f_2 u_0 \\ \vdots \\ u_n &= f_0 u_n + f_1 u_{n-1} + \cdots + f_k u_{n-k} + \cdots + f_n u_0 \\ &= \sum_{k=0}^n u_k f_{n-k} \end{align}\]

or equivalently,

\[u_{2n} = \sum_{k=0}^n u_k f_{n-k} = \sum_{k=0}^n u_{2k} f_{2(n-k)}\]

where \(f_k u_{n-k}\) represents the probability that the random walker returned to 0 for the first time after \(k\) steps and then returned to 0 again in \(n-k\) more steps. And if we define the generator functions

\[\begin{align} S(x) = \sum_{n=0}^{\infty} u_{2n} x^n \\ F(x) = \sum_{n=0}^{\infty} f_{2n} x^n \end{align}\]

then we have:

\[\begin{align} S(x)F(x) &= u_0 f_0 + (u_0 f_2 + u_2 f_0) x + \cdots + \left(\sum_{k=0}^n u_{2k} f_{2(n-k)} \right) x^n + \cdots \\ &= 0 + u_2 x + \cdots + u_{2n} x^n + \cdots \\ &= S(x) - 1 \end{align}\]

The above we substituted the coefficients of each \(x^n\) with \(u_{2n}\), according to the relations enumerated above. And from this we have:

\[\begin{align} F(x) &= \frac{S(x) - 1}{S(x)} \\ f &= \lim_{x\nearrow 1} F(x) = 1 - \lim_{x\nearrow 1}\frac{1}{S(x)} = 1 - \frac{1}{\sum_{n=0}^{\infty} u_n} \end{align}\]

The equation above, \(f\) is the probability that equalization occurs and \(\sum_{n=0}^{\infty} u_n\) is the expected number of visits to 0. Rearranging, we also have:

\[\sum_{n=0}^{\infty} u_n = \frac{1}{1-f}\]

Therefore:

  • Always for any \(N\), \(\sum_{n=0}^N u_n \le \lim_{s\nearrow 1} U(s)\)
  • If \(\sum_{n=0}^{\infty} u_n = \infty\), then \(\lim_{s\nearrow 1} U(s) = \infty\) and \(f = \sum_{n=0}^{\infty} f_n = \lim_{s\nearrow 1} F(s) = 1\)
  • If \(\sum_{n=0}^{\infty} u_n < \infty\), then \(\lim_{s\nearrow 1} U(s) < \infty\) and \(f = \sum_{n=0}^{\infty} f_n = \lim_{s\nearrow 1} F(s) < 1\)

or the probability of returning to 0 is one iff \(\sum_{n=0}^{\infty} u_n = \infty\).

Case of specific dimensions

d=1

We now apply the above result to a particular dimension. For \(d=1\), a symmetric random walk can have \(2^{2n}\) possible routes in \(2n\) steps. But there are only \(\binom{2n}{n}\) routes will have equal number of left and right moves, i.e., return to 0 at step \(2n\). Therefore,

\[\begin{align} u_{2n} &= \frac{\binom{2n}{n}}{2^{2n}} \\ &= \frac{(2n)!}{(n!)^2} \frac{1}{2^{2n}} \\ &\approx \frac{\sqrt{2\pi(2n)}(2n)^{2n}e^{-2n}}{(\sqrt{2\pi n}n^ne^{-n})^2} \frac{1}{2^{2n}} \\ &= \frac{1}{\sqrt{\pi n}} \end{align}\]

The approximation above is using Stirling’s formula, \(n! = \sqrt{2\pi n}n^n e^{-n}\). And so,

\[\sum_{n=0}^{\infty} u_n = \sum_{n=0}^{\infty} u_{2n} \approx \sum_{n=0}^{\infty} (\pi n)^{-1/2} = \infty\]

The last equality can be found by considering:

\[\sum_{n=0}^{\infty} (\pi n)^{-1/2} \approx \int_0^{\infty} (\pi n)^{-1/2} dn\]

Asymmetric random walk

The case of asymmetric random walk on \(\mathbb{Z}\): If we assume the probability of going right at each step is \(p\) and that of going left is \(1-p\), then we have \(u_{2n} = p^n (1-p)^n \binom{2n}{n}\), which the above derivation becomes:

\[\begin{align} u_{2n} &= p^n (1-p)^n \binom{2n}{n} \\ &= p^n (1-p)^n \frac{(2n)!}{(n!)^2} \\ &\approx p^n (1-p)^n \frac{\sqrt{2\pi(2n)}(2n)^{2n}e^{-2n}}{(\sqrt{2\pi n}n^ne^{-n})^2} \\ &= (4p(1-p))^n \frac{1}{\sqrt{\pi n}} \end{align}\]

which will converge iff \(p\ne \frac{1}{2}\). In other words, there is a probability greater than zero that the random walk will never return to 0.

d=2

If \(d=2\), at each step we may go in one of the four directions. Therefore, there are \(4^{2n}\) possible routes in \(2n\) steps and for equalization, the number of steps going up and down must equal as well as left and right must equal, which enumerated to be

\[\sum_{k=0}^n \binom{2n}{k,k,n-k,n-k} = \sum_{k=0}^n \frac{(2n)!}{k!k!(n-k)!(n-k)!}\]

possible routes.

Considering the multinomial expression, we have:

\[\begin{align} (2n)! &= n!n!\frac{(2n)!}{n!n!} = n!n!\binom{2n}{n} \\ \sum_{k=0}^n {\binom{n}{k}}^2 &= \binom{2n}{n} \end{align}\]

therefore

\[\begin{align} \sum_{k=0}^n \binom{2n}{k,k,n-k,n-k} &= \sum_{k=0}^n \frac{(2n)!}{k!k!(n-k)!(n-k)!} \\ &= \sum_{k=0}^n \frac{n!n!}{k!k!(n-k)!(n-k)!}\binom{2n}{n} \\ &= \sum_{k=0}^n {\binom{n}{k}}^2 \binom{2n}{n} \\ &= {\binom{2n}{n}}^2 \\ \end{align}\]

and the probability

\[\begin{align} u_{2n} &= \frac{1}{4^{2n}}{\binom{2n}{n}}^2 \\ &= \frac{1}{4^{2n}}\left(\frac{(2n)!}{(n!)^2}\right)^2 \\ &\approx \frac{1}{4^{2n}}\left(\frac{\sqrt{4\pi n}(2n)^{2n}e^{-2n}}{(\sqrt{2\pi n}n^ne^{-n})^2}\right)^2 \\ &= \frac{1}{\pi n} \end{align}\]

Therefore,

\[\sum_{n=0}^{\infty} u_n = \sum_{n=0}^{\infty} u_{2n} \approx \sum_{n=0}^{\infty} \frac{1}{\pi n} = \infty\]

d=3

Using similar argument,

\[\begin{align} u_{2n} &= \frac{1}{6^{2n}}\sum_{k=0}^n\sum_{j=0}^k\binom{2n}{j,j,k-j,k-j,n-k,n-k} \\ &= \frac{1}{6^{2n}}\sum_{k=0}^n\sum_{j=0}^k\frac{(2n)!}{j!j!(k-j)!(k-j)!(n-k)!(n-k)!} \\ &= \frac{1}{2^{2n}3^{2n}}\sum_{k=0}^n\sum_{j=0}^k\binom{2n}{n}\left(\frac{n!}{j!(k-j)!(n-k)!}\right)^2 \\ &= \frac{1}{2^{2n}} \binom{2n}{n} \sum_{k=0}^n\sum_{j=0}^k \left(3^{-n}\frac{n!}{j!(k-j)!(n-k)!}\right)^2 \\ &\le \frac{1}{2^{2n}} \binom{2n}{n} \max_{\substack{j,k\\ j+k=n}}\left(3^{-n}\frac{n!}{j!(k-j)!(n-k)!}\right) \end{align}\]

The last inequality is due to \(\sum_{j,k} a_{j,k}^2 \le \max_{j,k} a_{j,k}\) if \(a_{j,k}\ge 0\) and sum to 1 (due to it is a distribution). Using Stirling’s formula here, together with the result of \(d=1\),

\[\begin{align} u_{2n} &\le \frac{1}{2^{2n}} \binom{2n}{n} \max_{\substack{j,k\\ j+k=n}}\left(3^{-n}\frac{n!}{j!(k-j)!(n-k)!}\right) \\ &= \frac{1}{\sqrt{\pi n}} \left(3^{-n}\frac{n!}{(\left[\frac{n}{3}\right]!)^3}\right) \\ &= \frac{1}{\sqrt{\pi n}} \left(3^{-n}\frac{\sqrt{2\pi n}n^ne^{-n}}{(\sqrt{2\pi n/3}(n/3)^{n/3}e^{-n/3})^3}\right) \\ &= \frac{1}{\sqrt{\pi n}} \left(3^{-n}\frac{\sqrt{2\pi n}n^ne^{-n}}{2\pi n/3 \sqrt{2\pi n/3} (n/3)^n e^{-n}}\right) \\ &= \frac{1}{\sqrt{\pi n}} \left(3^{-n}\frac{1}{2\pi n 3^{-3/2} 3^{-n}}\right) \\ &= \frac{1}{\sqrt{\pi n}} \frac{3^{3/2}}{2\pi n} = O(n^{-3/2}) \end{align}\]

This makes the sum

\[\sum_{n=0}^{\infty} u_n < \infty\]

The probability of equalization \(f\) is the Pólya’s Random Walk Constants and in 3D, it is found to be 0.3405373296

d>3

On higher dimension, Polya’s result is that the probability of equalization is always less than one. Consider that the random walk is on \(d+1\) dimension and represent the position with a vector. If we restrict the \(d+1\)-th element to be always 0, that becomes a random walk on \(d\) dimension. Denote \(f^d\) to be the probability of equalization on a \(d\)-dimensional random walk. And also we define \(Z_n\) to be the event that a random walk on \(d\) dimension is at a position that the vector has first \(n\le d\) elements 0. Obviously \(Z_{n+1} \subseteq Z_n\) so does their probability. Hence by induction, we proved

\[f^{d+1} \le f^d\]

This is already established for \(d=1\) and \(d=2\).

Reference