04/04/2026
"A drunk man will find his way home, but a drunk bird may get lost forever."
-Shizuo Kakutani
In early 2025 I wrote a blog post discussing random walks on regular lattices in various dimensions, under the theme of randomly exploring "The Backrooms", an endless maze of halls and rooms, with the goal of returning to the point of origin. I laid out and gave simple proofs for Pólya's Recurrence Theorem, which states that a simple random walk on $\mathbb{Z}^d$ (the integer lattice in d dimensions) is recurrent (meaning it will always eventually return to the origin) in dimensions $d = 1,2$ and transient (meaning it may never return to the origin) for dimensions $d \geq 3$. Specifically, I gave proofs of recurrence for $d = 1,2$ and partial explanations for the cubic lattice $d = 3$, and I briefly discussed other types of lattices.
In this work, we will more rigorously re-examine the results for $d = 1,2$, further explore various types of lattices (A.K.A "Crystal structures") in the third dimension, and compare these results to those derived from computer simulation.
A random walk is simply a path on a graph or lattice where each step is chosen randomly, and we assume it to be simple (steps are to nearest neighbors only) and symmetric (all neighbors are equally likely). The most basic form of a regular (infinite) lattice is a one-dimensional "number line", where at each step the walk has a 50/50 chance of going "left" (-1) or "right" (+1). Assuming this walk begins at 0, it "returns to the origin" if it starts moving and then, after a finite number of steps, returns to 0. Note that it is easy to imagine both a scenario where the walk returns to the origin (such as moving left then right) and a scenario where it does not (such as moving left for every single step). However, escaping to infinity by moving in only one direction is like flipping a coin and getting only heads forever; the probability of this occurring is 0.
In fact, it is possible to construct both an infinite number of walks that return to the origin and an infinite number that don't. Since the number of each case cannot be counted, the relative probability of either case is not immediately apparent. Hungarian Mathematician George Pólya proved that on this one-dimensional lattice, the probability of a random walk returning to the origin in a finite number of steps is 1. In other words, the walk is "recurrent". We will aim to arrive at our own proof to gain insight into why this is the case.
Theorem 1: A simple random walk on $\mathbb{Z}^1$ will return to the origin in a finite number of steps with probability 1.
We can find the probability of returning to the origin if we can determine the expected number of visits to the origin on any given walk. Specifically, $p = 1 - \frac{1}{G}$, where $p$ is the probability of returning to the origin, and $G$ is the expected number of visits. For example, if the probability of the walk returning to the origin in a finite number of steps is 1 then we should intuitively expect it to return an infinite number of times, and indeed $1 - \frac{1}{\infty} = 1$. $G$ is also known as the lattice Green's function at the origin, or in other words, the "total accumulated time" (expected number of visits) at that point.
Let $u_n$ be the probability that a random walk on a lattice is at 0 (the origin point) after $n$ steps. It is immediately apparent for our number line that $u_0 = 1$, and that $u_1 = u_3 = u_5 = ... = 0$, since it is impossible to be on an even-numbered point on the line after an odd number of steps. If we add up all of these probabilites, we will receive the total number of times we should expect to return to the origin, which is $G$. From there we can determine the recurrence of the walk: The random walk is recurrent iff $p = 1$, and $p = 1$ iff $G = \infty$. Thus, this random walk is recurrent iff \[ G = \sum_{n=0}^{\infty} u_n = \infty \]
otherwise it is transient. Now, consider the number line again; First of all, since $u_n = 0$ for odd values of $n$ we know that $\sum_{n=0}^{\infty} u_n = \sum_{n=0}^{\infty} u_{2n}$. In order to be at 0 (the origin point) at step $2n$, you must have taken the same number of steps in both directions. Since at each step there are 2 options, the total number of possibilities at step $2n$ is $2^{2n} = 4^n$, and of those there are ${2n} \choose n$ combinations that have the same number of steps in both directions, meaning the probability $u_{2n}$ is equal to ${2n} \choose n$ divided by ${2^{2n}}$. Thus, we must determine whether this is true or false: \[ \sum_{n=0}^{\infty} \frac{{2n} \choose n}{2^{2n}} = \infty \]
Here we can use Stirling's approximation for the factorial to simplify the equation.
Lemma 2: \[ {{2n} \choose n} \sim \frac{2^{2n}}{\sqrt{\pi n}} \]
Proof: Stirling's formula states that $n! \sim \sqrt{2 \pi n} (\frac{n}{e})^n$. Thus:
\[ {{2n} \choose n} = \frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{2 \pi \cdot 2n} (\frac{2n}{e})^{2n}}{(\sqrt{2 \pi n} (\frac{n}{e})^n)^2} = \frac{\sqrt{2} \cdot \sqrt{2 \pi n} \cdot 2^{2n} \cdot (\frac{n}{e})^{2n}}{(\sqrt{2 \pi n})^2 (\frac{n}{e})^{2n}} = \frac{2^{2n}}{\sqrt{\pi n}} \]
Note that $2^{2n}$ is the denominator in $\frac{{2n} \choose n}{2^{2n}}$ and the numerator in $\frac{2^{2n}}{\sqrt{\pi n}}$. Thus:
\[ u_{2n} = \frac{{2n} \choose n}{2^{2n}} \sim \frac{1}{\sqrt{\pi n}}\]
Because $u_{2n} \sim \frac{1}{\sqrt{\pi n}}$, we know by the limit comparison test that the series $\sum_{n=1}^{\infty} u_{2n}$ will diverge if $\sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}}$ diverges.
$\sum_{n=1}^{\infty} \frac{1}{n}$ is the well-known harmonic series, which is known to diverge to infinity. Since the terms of $\frac{1}{n^x}$ shrink to 0 slower than $\frac{1}{n}$ for all $0 \lt x \lt 1$, the series must also diverge (this is known as the p-series test). Thus, $\sum_{n=1}^{\infty} \frac{1}{\sqrt{n}} = \sum_{n=1}^{\infty} \frac{1}{n^{\frac{1}{2}}} = \infty$. For our case of $\sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}}$ we can factor out the constant $\frac{1}{\sqrt{\pi}}$ to get $\frac{1}{\sqrt{\pi}} \sum_{n=1}^{\infty} \frac{1}{\sqrt{n}}$, which must also equal $\infty$. Note that we have switched from $n=0$ to $n=1$ for our formula since $\frac{1}{0}$ is undefined. This is no problem, since we know $u_0 = 1$ and thus $\sum_{n=1}^{\infty} u_{2n}$ = $\sum_{n=0}^{\infty} u_{2n} - 1$, meaning if one is infinite then the other will be as well. We can now determine:
\[ \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \frac{1}{\sqrt{\pi}} \sum_{n=1}^{\infty} \frac{1}{\sqrt{n}} = \infty \implies \sum_{n=1}^{\infty} u_{2n} = \infty \]
\[ G = 1 + \sum_{n=1}^{\infty} u_{2n} = \infty \]
Since $p = 1 - \frac{1}{G} = 1$, theorem 1 is proven.
Pólya's theorem also states that a random walk on a two-dimensional lattice $\mathbb{Z}^2$ is recurrent.
Theorem 3: A simple random walk on $\mathbb{Z}^2$ will return to the origin in a finite number of steps with probability 1.
To prove this theorem, we must again show that the expected number of returns $G$ is infinite.
Determining the case for a two-dimensional square lattice is not too difficult once we understand the one-dimensional case. We can use a trick for it: If we rotate our lattice by 45° and dilate it by a factor of $\sqrt{2}$, we have effectively created a diagonal lattice where each move is either (+1, +1), (+1, -1), (-1, +1), (-1, -1). If we consider the x and y components separately, this is effectively equivalent to two independent one-dimensional random walks occurring simultaneously, where a return to the origin only occurs if both axes are 0. Since they are independent, the probability of both returning to the origin at step $2n$ is simply the square of the probability for $\mathbb{Z}^1$. Thus, \[ u_{2n} \sim (\frac{1}{\sqrt{\pi n}})^2 = \frac{1}{\pi n}\]
By the LCT, because our probabilities scale as $\frac{1}{\pi n}$, the sum of our probabilities must also diverge:
\[ \sum_{n=1}^{\infty} \frac{1}{\pi n} = \infty \implies \sum_{n=1}^{\infty} u_{2n} = \infty \]
Therefore, $G = \infty$, and thus theorem 3 is proven.
Pólya's theorem states that a random walk on a three-dimensional cubic lattice $\mathbb{Z}^3$ is transient, meaning there is a chance that it will never return to the origin. Although the combinatorics for the three-dimensional case are far more complex than the previous two cases, the asymptotic behaviour follows the same logic: For one dimension, $u_2n$ scales asymptotically with $\frac{1}{n^{1/2}}$, and for two dimensions it scales asymptotically with $\frac{1}{n^{1}}$. For three dimensions, we will show that $u_{2n}$ is bounded by $C \cdot \frac{1}{n^{3/2}}$ where $C$ is some constant.
We cannot use the same simple geometric rotation trick for the standard cubic lattice. In $\mathbb{Z}^3$ there are 6 possible directions to move in, so the total number of possible paths after $2n$ steps is $6^{2n}$. To return to the origin, the walk must take an equal number of steps in the positive and negative directions for each axis. Let $i$ be the number of steps taken in the $+x$ direction, $j$ in the $+y$ direction, and $k$ in the $+z$ direction. This means it must also take $i$ steps in $-x$, $j$ steps in $-y$, and $k$ steps in $-z$. The total number of steps is $2i + 2j + 2k = 2n$, which simplifies to $i + j + k = n$.
The number of ways to arrange these steps is given by the multinomial coefficient $\frac{(2n)!}{i! i! j! j! k! k!} = \frac{(2n)!}{(i!j!k!)^2}$. Summing this over all valid combinations of $i, j,$ and $k$, the probability of returning to the origin at step $2n$ is:
\[ u_{2n} = \frac{1}{6^{2n}} \sum_{i+j+k=n} \frac{(2n)!}{(i! j! k!)^2} \]
This can be rewritten by multiplying the inside of the sum by $\frac{(n!)^2}{(n!)^2}$ and splitting $6^{2n}$ into $2^{2n} \cdot 3^{2n}$. By pulling terms that do not depend on $i, j,$ or $k$ outside the sum, we get an elegant rearrangement:
\[ u_{2n} = \left[ \frac{\binom{2n}{n}}{2^{2n}} \right] \cdot \left[ \frac{1}{3^{2n}} \sum_{i+j+k=n} \left( \frac{n!}{i! j! k!} \right)^2 \right] \]
Evaluating the exact asymptotic of this sum is mathematically burdensome. However, to prove transience, the exact formula is not needed, only need an upper bound. So, we will look at the two bracketed components separately.
The first bracket is identical to the formula for the one-dimensional case. From Lemma 2, we already know this is asymptotically equivalent to $\frac{1}{\sqrt{\pi n}}$.
For the second bracket, recall from the standard multinomial theorem that the sum of the base terms without the squares is $\sum_{i+j+k=n} \frac{n!}{i!j!k!} = 3^n$. To find an upper bound for the sum of squares, we can find the maximum value of the term $\frac{n!}{i!j!k!}$ and factor it out:
\[ \sum_{i+j+k=n} \left( \frac{n!}{i! j! k!} \right)^2 \le \max\left(\frac{n!}{i! j! k!}\right) \sum_{i+j+k=n} \frac{n!}{i! j! k!} = \max\left(\frac{n!}{i! j! k!}\right) \cdot 3^n \]
The maximum term occurs when the steps are distributed as evenly as possible, meaning $i \approx j \approx k \approx \frac{n}{3}$. By applying Stirling's approximation to $\frac{n!}{((n/3)!)^3}$, the terms simplify to show that this maximum value scales as $\frac{c}{n} 3^n$ for some constant $c$. Substituting this back into the second bracket gives:
\[ \frac{1}{3^{2n}} \left( \frac{c}{n} \cdot 3^n \right) \cdot 3^n = \frac{1}{3^{2n}} \left( \frac{c}{n} \cdot 3^{2n} \right) = \frac{c}{n} \]
The two bounded brackets can now be multiplied together to find the combined upper bound for $u_{2n}$:
\[ u_{2n} \le \left( \frac{1}{\sqrt{\pi n}} \right) \cdot \left( \frac{c}{n} \right) = \frac{C}{n^{3/2}} \]
(Where $C$ is a new combined constant). Because $u_{2n}$ scales with $\frac{1}{n^{3/2}}$, we can determine its convergence. By the p-series test, any sum $\sum \frac{1}{n^p}$ where $p > 1$ converges to a finite number. Since $1.5 > 1$, the series $\sum_{n=1}^{\infty} u_{2n}$ converges. Therefore, $G \lt \infty$, meaning $p \lt 1$. Because the probability of returning is less than 1, the walk is transient.
While proving the transience of the cubic lattice (referred to as the simple cubic lattice (or simply 'sc') going forward) is viable combinatorically, solving the exact probability of return for both the SC case and other regular 3D lattices requires a switch to an analytical framework. This is where we reintroduce the concept of the lattice Green's function (LGF), a probability-generating function commonly used in condensed matter physics. The general form is as follows: \[ P(\vec{l}; z) = \frac{1}{(2\pi)^d} \int_{-\pi}^{\pi} \dots \int_{-\pi}^{\pi} \frac{\text{d}^d \vec{k}}{1 - z\lambda(\vec{k})} \]
The coefficient of $z^n$, denoted as $[z^n] P(\vec{l}; z)$, is the probability that a walker starting at the origin will be at position $\vec{l}$ after n steps. In this case, $P(\vec{0}; 1)$ is equivalent to $G$, and thus $p = 1 - 1/P(\vec{0}; 1)$.
Here, $\lambda(\vec{k})$ is the structure function of the lattice, given by the discrete Fourier transform of the individual step probabilities. It effectively encodes the geometry of the lattice into a continuous mathematical formula. As an example, the structure function for a lattice in $\mathbb{Z}^d$ is \[ \lambda(\vec{k}) = \frac{1}{d} (\text{cos } k_1 + \text{cos } k_2 + \dots + \text{cos } k_d)\]
In two dimensions, the LGF becomes \[ P(\vec{0}; 1) = \frac{1}{(2\pi)^2} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \frac{\text{d} k_1 \text{d} k_2}{1 - \lambda(\vec{k})} \]
which we know to diverge. The four standard 3D lattices have structure functions as follows:
\[ \lambda(\vec{k})_{sc} = \frac{1}{3} (\text{cos } k_1 + \text{cos } k_2 + \text{cos } k_3)\]
\[ \lambda(\vec{k})_{bcc} = (\text{cos } k_1 \text{cos } k_2 + \text{cos } k_3)\]
\[ \lambda(\vec{k})_{fcc} = \frac{1}{3} (\text{cos } k_1 \text{cos } k_2 + \text{cos } k_1 \text{cos } k_3 + \text{cos } k_2 \text{cos } k_3)\]
\[ \lambda(\vec{k})_{diam} = \frac{1}{4} (1 + \text{cos } k_1 \text{cos } k_2 + \text{cos } k_1 \text{cos } k_3 + \text{cos } k_2 \text{cos } k_3)\]
These are for the simple cubic, body-centered cubic, face-centered cubic and diamond lattices respecticely. These will be the 3D lattices that we cover in this write-up. Setting $P(\vec{0}; 1)$ produces the famous Watson integrals for the 3-dimensional case.
\[ P(\vec{0}; 1) = \frac{1}{(2\pi)^3} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \frac{\text{d} k_1 \text{d} k_2 \text{d} k_3}{1 - \lambda(\vec{k})} \]
Notoriously difficult to solve, the bcc LGF was first solved by van Peype in 1938 and the other three were solved by Watson in 1939. Thus, I will skip any calculations for this portion and give the evaluated values directly. The Watson integrals have been evaluated to yield
\[ P(\vec{0}; 1)_{sc} \approx 1.51639 \]
\[ P(\vec{0}; 1)_{bcc} \approx 1.39320 \]
\[ P(\vec{0}; 1)_{fcc} \approx 1.34466 \]
\[ P(\vec{0}; 1)_{diam} \approx 1.79288 \]
These give approximate $p$ values of 0.341, 0.282, 0.256 and 0.442 respectively. The takeaway is that the probability of a random walk returning to the origin on $\mathbb{Z}^3$ has a 34.1% chance of returning to the origin in a finite number of steps.
I created a Rust program to simulate large numbers of random walks on the four previously covered lattice structures, with an argument for the number of maximum steps each walk (N). All simulations were run with at least 100,000 walks.
These results match those obtained through theory. As expected, for small values of N the obtained probability of return is noticeably lower than the value from theory, as all walks that would hypothetically return to the origin after a large number of steps would be considered to have not returned.
| Max Steps (N) | Simple Cubic (SC) | BCC | FCC | Diamond |
|---|---|---|---|---|
| 100 | 0.311825 | 0.256251 | 0.230698 | 0.410721 |
| 1,000 | 0.331036 | 0.274176 | 0.247924 | 0.433397 |
| 10,000 | 0.337948 | 0.278539 | 0.253792 | 0.441580 |
| 100,000 | 0.338610 | 0.281900 | 0.257670 | 0.440310 |
| 1,000,000 | 0.341690 | 0.281650 | 0.255800 | 0.443860 |
| Theoretical Limit | 0.340537 | 0.282178 | 0.256318 | 0.442238 |
The source code for the program can be found here.
Much of the content in parts 1, 2 and 3 is based on the article by Tyler Zhu [1], especially the translation trick used for proving the recurrence of walks in $\mathbb{Z}^2$. The work in part 5 was assisted by the work of Anthony J Guttmann [2].
[1] Tyler Zhu, Pólya's Recurrence Theorem. https://tylerzhu.com/assets/handouts/polya_rec.pdf
[2] Anthony J Guttmann (2010), Lattice Green's functions in all dimensions. DOI: 10.1088/1751-8113/43/30/305205
[3] W. H. McCrea, F. J. W. Whipple (1940), Random Paths in Two and Three Dimensions. DOI: 10.1017/S0370164600020265
[4] Eric W. Weisstein, Pólya's Random Walk Constants. https://mathworld.wolfram.com/PolyasRandomWalkConstants.html