There and back again, part 3

This is part three in a three-part series about recurrence and transience on the integer lattices. Here is part one. Here is part two.

Weary and tired, we are approaching the end of our coin-flipping, lattice-exploring adventures, but with one aching question still burning deep within our hearts: Is the random walk on the three-dimensional lattice recurrent? At this point, your intuition is starting to whisper softly and seductively in your ear, “my dear beloved, the random walk on \mathbb{Z}^3 is transient, can’t you see? While the walk on \mathbb{Z} had a relatively easy time finding its way back to the origin, we saw that just by adding an extra dimension, \mathbb{Z}^2 was already so much closer to being transient. It’s now almost obvious that the horrendous maze of edges that is the three-dimensional lattice can only be transient. Why, just look how hard it is to draw the thing on the screen! No doubt, a jet-pack wielding drunkard (both a marvelous sight and an imminent danger) who stumbles randomly in space could always find himself lost forever, drifting away towards infinity”.

That’s some intuition you got there! At least it’s got the right answer down: Not even the most entrenched anti-vaxxer can deny, the simple random walk on \mathbb{Z}^3 is transient!

We will again give two proofs. The first will use our “old-reliable” electrical networks, which so far have served us well and without fail, and will continue to serve us well and without fail until the end of time. The second will try to use multiple independent random walks in a way similar to the two-dimensional case. It will initially fail, but after a slight tweak and a cute theorem, will ultimately prevail; for all’s well that ends well.

Method #1: Electrical networks

By this time around, you are already seasoned electrical resistance warriors. “What’s the big deal”, you say, “I mean, couldn’t we just approximate the complicated structure of \mathbb{Z}^3 by some easier to control graph which we know is transient? This shouldn’t be too hard, since all we have to do is calculate its effective resistance. And you know what, I’m willing to bet my jetpack that doing this will involve some sort of operation stemming from a real, physical-network law, just like the shorting law was inspired by real-life short-circuiting.”

Indeed, the principle we are going to use this time is the cutting law. If we have two vertices x and y which are connected by a resistor, we can remove the resistor, thereby increasing to infinity the resistance between x and y , and generally increasing the effective resistance of the entire network. This amounts to deleting an edge from the original graph from which the electrical network was obtained.

Our strategy will then be to cut away lots of edges from \mathbb{Z}^3 , so that in whatever’s left, we can easily calculate the effective resistance between the origin and the boundary of a large box. The trick is to cut out the right edges and in the right places, so that the effective resistance of the resultant graph doesn’t grow too much, and in fact remains finite as the size of the boxes grows to infinity. By the cutting law, this will imply that the effective resistance of boxes in the original \mathbb{Z}^3 is also finite, which in turn means that there is a non-zero probability to escape to infinity. In fact, we calculated this probability in the first post in the series:

p_{\mathrm{esc}} = 1 / C_a R_{\mathrm{eff}},

where C_a is the total conductance of the origin. Thus, getting an upper-bound on the effective resistance also gives a lower-bound on the probability to escape.

That’s all very well and nice and all, but the real problem here is to find out which edges to cut. And unfortunately, there is no shortcut here, and no general method which always works; you just have to go to the graph, give it a good shake, and see what falls out.

There is one guideline though, which is quite well and thoroughly explained in the book Random walks and electric networks, and which at least offers some insight to the problem. While calculating resistances for general graphs usually involves clever manipulations and a good unhealthy dose of Kirchoff’s laws, there is one particularly easy case where even preschoolers have a good time calculating: Trees. In particular, symmetric trees, where the number of offspring a vertex has only depends on its distance to the root of the tree. These can always be quickly reduced to a simple line of resistors by applying the parallel law (think why!), and for a line of resistors the effective resistance is immediate. So all we have to do is find a nice symmetric tree which sits comfortably and snugly inside \mathbb{Z}^3 . We’ll then prune away all edges which are not in this tree.

In fact, if you follow our construction in the previous post for \mathbb{Z}^2 , you will notice that there too we have constructed a tree. So a good place to start the investigation for the three-dimensional lattice, is to see what sorts of trees it contains (and what sorts of trees it doesn’t).

I think Doyle and Snell do a pretty good job in their treatise on treating trees, so if you want the background, you should definitely go and read them them (see page 78 for trees in general, and page 82-92 for the specific tree we will now show). In fact, I’ll even blatantly copy some images from book.

Anyway, here is an example of a nice, easily-computable graph which sits inside \mathbb{Z}^3 . It is not exactly a tree, but is heavily inspired by one. We build it in steps. Take the origin 0 , and connect it to the three vertices which are the non-negative integer solutions to the equation

x + y + z = 1.

Thus the first three vertices are (0,0,1) , (0,1,0) and (1,0,0) . We may think of obtaining these vertices via the following method: send out rays from the origin along the positive x , y , and z direction, and check where they intersect with the plane whose equation is x + y + z = 1 . This is given by the following image:
Now we continue in this fashion again and again, slowly building up the graph one level at a time: Suppose that we have just obtained all the vertices of generation n . From each such vertex extend a ray in the positive x , y , and z direction, and add the intersection points of these rays with the plane whose equation is x + y + z = 2^{n+1}-1 . The following images demonstrate the next steps in the process:
Have we already mentioned that 3D graphs do not like being squeezed onto 2D screens?

If you follow this construction infinitely many times, you eventually (eventually) end up with an infinite tree. In order to calculate its effective resistance, it’s convenient to split apart vertices in the same generation (something we can do, since same-generation vertices are bound to have the same electric potential by the symmetry of the construction, and so we do not change the effective resistance when doing so). If you do this in the right places, you will find that the graph just described above is actually equivalent in resistance to the following nice tree fellow:

This tree, nicknamed NT_{2.5849\ldots} (for logarithmic reasons), can be constructed iteratively as follows. Start out with only the origin as both the root and the sole leaf in the tree, and at step number n grow three branches of length 2^{n-1} out of every leaf. Repeat ad infinitum, season to taste. That’s it!

Since this is a symmetric tree, we can rather straightforwardly calculate the effective resistance from the origin to infinity, by looking at what happens in between two different branchpoints. The branch segment which starts at branchopint n and ends at branchpoint n+1 is of length 2^{n-1} , and so has effective resistance of 2^{n-1} . But since there are 3^n such segments in parallel, the effective resistance between level n and level n+1 is 2^{n-1} / 3^n = \frac{1}{3}\left(\frac{2}{3}\right)^{n-1} . The total resistance of the entire tree is then

R_{eff} = \frac{1}{3}\sum_{n=0}^{\infty} \left(\frac{2}{3}\right)^{n}

=\frac{1}{3} \cdot \frac{1}{1-2/3} = 1.

The effective resistance of the tree is finite! And since the tree was obtained only by removing edges from \mathbb{Z}^3 , by the cutting law the effective resistance of \mathbb{Z}^3 is finite as well, which means that it is transient.

Method #2: The straightforward calculation, with a twist

So far we’ve had a lot of luck with trying to explicitly figure out the expected number of times that the random walk hits the origin. We did this by calculating the probability that the random walk returns to the origin after an even number 2k of steps. In the one-dimensional case, the calculation went smooth as butter, and we found that

\mathbf{Pr}[X_{2k} = 1] \approx 1/\sqrt{k}.

The expected number of returns is then given by

\sum_{k=0}^\infty 1/\sqrt{k} = \infty,

implying that the walk on \mathbb{Z} is recurrent.
In the two-dimensional case, the term was a bit more difficult, but luckily for our lazy-and-trick-loving selves, it turned out that the simple random walk on \mathbb{Z}^2 can actually be seen as the product of two simple random walks on \mathbb{Z} , so that the expected number of returns is

\approx \sum_{k=0}^\infty 1/\sqrt{k}^2 = \sum_{k=0}^\infty 1/k = \infty,

implying that the walk on \mathbb{Z}^2 is recurrent as well. If we could show that the same were true for three dimensions, i.e that the walk on \mathbb{Z}^3 is a product of three one-dimensional walks, we’d be immediately done, for then the expected number of returns would be roughly equal to

\approx \sum_{k=0}^\infty 1/\sqrt{k}^3

which converges, implying that the walk is transient.

All that we need to do then, is show that if we flip a coin which tells us where to go in the x direction, flip a coin which tells us where to go in the y direction, and flip a coin which tells us where to go in the z direction, we end following the same motions as if we flipped a six-sided coin and chose to go either forwards or backwards in one of the three directions at random.

Unfortunately, such dreams are cute but false. The simple random walk on \mathbb{Z}^3 does not decompose into three independent random walks. For example, as a quick sanity check, the simple random walk on \mathbb{Z}^3 has six options to choose from at each step, while the triple-\mathbb{Z} random walk has eight. In fact, one step in the product of walks looks like this:

This is the unit cell of the so called BCC lattice.

However, not all is lost. If you solved the riddle from the previous post, your spider-sense might get tingling again and suggest that lattices which are not-quite-the-same yet not-too-different (for example, different lattices of the same dimension) might have the same recurrence/transience properties. This is basically true, as the following definition and theorem show.

Definition: Let G be an infinite graph with bounded degree, and let k>0 be an integer. The k fuzz of G , denoted G_k , is the graph obtained by adding to G an edge xy if it is possible to go from x to y in at most k steps.
For example, here is \mathbb{Z} and its 2 -fuzz:

Theorem: For any k>0 , the simple random walk on G is transient if and only if the simple random walk on G_k is transient.

In other words, there is a specific way of adding edges to a graph – “fuzzing” it, if you will – so that the recurrence/transience of the graph does not change when we do so. As an intuition as to why this is true, let’s consider the 2 -fuzz of a graph, which is the graph obtained by connecting together all pairs of vertices which were originally at distance 2 from each other. A simple random walk on this graph is almost the same as randomly choosing between taking either one or two steps in the original graph. Sure, there are some mild differences in the transition probabilities, and it might be that after taking two steps we find ourselves in the same place where we started, but essentially, the two walks feel very much the same.

Although this feeling can be formalized, and the comparison between the k -fuzz and the k -step random walk made precise, I’d rather give an electric network proof of the above theorem.

Proof: The k -fuzz G_k is obtained from G by adding edges, i.e adding more resistors to its network. Adding a resistor is the opposite of cutting (i.e we turn an infinite “no-edge” resistor into a finite resistor), and so lowers the effective resistance. Thus the effective resistance of G_k is smaller than that of G , and so if G has finite resistance and therefore transient, then G_k has finite resistance and is also transient.

On the other hand, let’s consider two vertices x and y and compare the effective resistance between them in G and in G_k . For what follows, we can suppose without loss of generality that they are connected in G_k . In G , the effective resistance between the vertices is no more than k , since there is a path of length no more than k from x to y . What about G_k ? Well, denote the maximal degree of G by d . The smallest resistance possible between x and y is 1/d^k , since there can be no more than d^k paths from x to y in G . Thus the ratio between the effective resistance between any pair of vertices x and y differs by no more than the factor kd^k . This may be large, but it is always finite, so the effective resistance of G is always smaller than some constant times that of G_k . So if G_k has finite resistance and therefore transient, then G has finite resistance and is also transient.

This theorem is exactly the tool we have been waiting for! Look at the BCC lattice obtained by three independent coordinate motions. With a bit of mental gymnastics, you might notice that it’s possible to embed it into the k -fuzz of \mathbb{Z}^3 , for a k that is actually not that large. By cutting away extra unneeded edges, we must conclude that the k -fuzz of \mathbb{Z}^3 is transient. But then by the above theorem, so is \mathbb{Z}^3 !

So ends our three-post extravaganza about simple random walks on the integer lattices. Long as they might seem, these posts barely scratch even a millimeter-deep dent in the surface of this vast subject. Even if you weren’t completely bored by my dense writing (and especially if you were), I still highly recommend giving Random walks and electric networks a chance.

Until next time, here is a quick puzzle. Suppose that we wish to break free of our discrete binding chains, and talk about random walks in a continuous space. As a concrete example, suppose we have a walker starting at the origin, who at every time step randomly chooses a coordinate, then randomly chooses a step size uniform in [-1,1] and steps the chosen amount in that direction. Is the walker guaranteed to return arbitrarily close to the origin in one, two, or three dimensions?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s