There and back again, part 1

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

It is a truth universally acknowledged, that a single man in possession of a coin, who repeatedly flips it, taking one step forwards if it comes up heads, and one step backwards if it comes up tails, will eventually return to the place where he started.

Mathematicians like to call the process of using coins in order to decide what to do in life a “random walk”, and it is often performed on graphs. A walker (whom we’ll call Alice) sits at one of the vertices, and at each time step, she chooses a one of the vertex’s neighbors with some probability and moves there. The simplest case of a random walk, the aptly named “simple random walk”, is where Alice chooses each neighbor with equal probability. In the particular case of the single man in possession of a coin described above, that graph was the integer number line \mathbb{Z} , also known as the one-dimensional integer lattice.

At each step, Alice takes a step to the right with probability 1/2 , and a step to the left with probability 1/2 . We could have asked a similar question, about \mathbb{Z}^2 , also known as the two-dimensional integer lattice:

Here, at each step, Alice moves up with probability 1/4 , down with probability 1/4 , left with probability 1/4 , and right with probability 1/4 . The adventurous (and jetpack wielding) among us may even consider performing a random walk on the three-dimensional lattice, where the probability of going in each direction is 1/6 .

Fun fact: 3D objects don’t like it when you squash them onto a 2D screen.

These three lattices will be the main players in this series of posts. Specifically, we will investigate their recurrence and transience: If Alice starts at the origin, that is, the vertex labeled 0 , will she always, with 100% certainty, return back there, after some finite number of steps? If so, we call the graph that Alice walks on “recurrent”. Otherwise, if there is some probability (no matter how tiny) that Alice will be forever lost in wanderland, we call the graph “transient”.

If this is the first time that you encounter this notion, it is actually not at all obvious which of these graphs are transient and which recurrent. I remember the first time I ran into it, I was quite dazzled, and certainly hadn’t the faintest clue concerning the transience of even a single one of them. The only initial guideline is that it seems intuitive that graphs in higher dimension are somehow more complex than those in lower dimensions: The walk on \mathbb{Z} smells much simpler than the walk on \mathbb{Z}^2 , since on the former Alice basically walks up and down on a single path, while on the latter she has many different paths she can take. Similarly, the walk on \mathbb{Z}^3 can be expected to be more complicated than that of \mathbb{Z}^2 . But this really doesn’t say anything concrete about any of them.

So what’s in store for us today? As alluded to in the opening paragraph, the walk on \mathbb{Z} is… recurrent! With probability 1 , if you flip a coin and go forwards or backwards based on the result, you will eventually find yourself right where you started, 100% guarantee, or your money back! (not your time, though, and it might take you quite a long while to return). This post, which is mostly based on the wonderful book Random walks and electric networks by Doyle and Snell, will prove this fact. The upcoming Post #2 and Post #3 will talk about \mathbb{Z}^2 and \mathbb{Z}^3 respectively; I won’t spoil here which (if any) is recurrent.

We will show that \mathbb{Z} is recurrent in three different ways, in increasing order of elegance: straightforward counting, limits of finite boxes, and resistor networks.

Method #1: The straightforward calculation
This proof relies on the following nice observation: If the random walk returns to the origin with probability 1 , then with probability 1 it will actually return to the origin infinitely many times. You can think of it this way: Once we hit 0 , the entire game essentially “resets”, and we find ourselves in exactly the same position as we started in. On the other hand, if there is a finite probability of escaping to infinity, then we expect to visit the origin only a finite number of times: Every time we return to the origin, we have a constant non-zero probability to never come back. If we return to 0 too many times, then eventually we’ll run out of luck and escape.

In fact, in the latter case we can find out an expression for the expected number of times we return to the origin. Let p_{\mathrm{ret}} < 1 be the probability that the walker, starting at 0 , returns to 0 . The probability of escaping to infinity then is just (1-p_{\mathrm{ret}}) ; in this case, throughout the entire walk, the walker was at 0 only once, at time 0 . The probability of returning exactly once to the origin is p(1-p_{\mathrm{ret}}) : The first p_{\mathrm{ret}} is to return once, and the (1-p_{\mathrm{ret}}) is to never return after that; in this case the walker visited 0 exactly twice. In general, the probability to return k times and thus visit the origin k+1 times is p_{\mathrm{ret}}^k (1-p_{\mathrm{ret}}) . Since we never return an infinite number of times to the origin, the expected number of visits to 0 is then just a sum over every finite number of returns:

\mathbb{E}[\text{\#visits}] = \sum_{k=1}^{\infty} k \cdot p_{\mathrm{ret}}^{k-1}(1-p_{\mathrm{ret}}).

Since p_{\mathrm{ret}} < 1 , we can write this sum as

\sum_{k=1}^{\infty} k \cdot p_{\mathrm{ret}}^{k-1}(1-p_{\mathrm{ret}}) =  (1-p_{\mathrm{ret}}) \sum_{k=1}^{\infty} k \cdot p_{\mathrm{ret}}^{k-1}

= (1-p_{\mathrm{ret}}) \frac{d}{dp_{\mathrm{ret}}}\sum_{k=0}^{\infty} p_{\mathrm{ret}}^k

= (1-p_{\mathrm{ret}})  \frac{d}{dp_{\mathrm{ret}}}\left(\frac{1}{1-p_{\mathrm{ret}}}\right)

= \frac{1}{1-p_{\mathrm{ret}}}.

Thus, if p_{\mathrm{ret}}<1 , that is, we have a non-zero probability of escaping to infinity every time we hit 0 , then the expected number of times we return to the origin is finite. (Incidentally, if we treat p_{\mathrm{ret}} as a variable and let p_{\mathrm{ret}} \to 1 , we get an infinite number of returns to the origin, although of course p_{\mathrm{ret}} is a constant that only depends on the lattice).

Now, here is another way to calculate the expected number of times we land at the origin, one which does not involve assuming beforehand whether or not we return an infinite number of times. Let X_n be the random variable that is 1 if the walker is at 0 at time n , and 0 otherwise. Then the total number of times we are at 0 is

T = \sum_{n=0}^{\infty} X_n.

The variables X_n are very heavily dependent on each other: For example, if we know that we visited the origin at time n , that is, X_n=1 , it really increases the likelihood that we visited the origin at times close to n . But luckily, thankfully, and blissfully, the expectation of a sum is always the sum of expectations, and so

\mathbb{E}[T] = \sum_{n=0}^{\infty} \mathbb{E}[X_n]

= \sum_{n=0}^{\infty} \mathbf{Pr}[X_n = 1].

By the argument we gave in the beginning, this sum will be infinite if the random walk is recurrent, and finite if the random walk is transient. So to check if the random walk (on any graph, actually) is transient or recurrent, we only have to sum up the individual probabilities to return to the origin at time n .

How do you calculate these probabilities? Well, first note that for all odd n , X_n = 0 : Every step we take to the right has to be counterbalanced at some point by a step to the left. In fact, this is the exact condition we need: For even n , say n = 2k , we need to take exactly k steps to the right and exactly k steps to the left. The probability \mathbf{Pr}[X_n = 1] is then just the total number of paths which take k steps to the left and k to the right (in any order), divided by the total number of paths there are of length 2k . Thus

\mathbf{Pr}[X_{2k} = 1] = {2k \choose k} / 2^{2k}.

For large enough k , the numerator can be approximated by (cf. good ol’ Stirling)

{2k \choose k} \approx 2^{2k} / \sqrt{\pi k},

and so

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

We can allow ourselves to use this approximation since eventually we only care about whether or not the expectation \mathbb{E}[T] is finite or not. So even if the approximation is bad for small k , or even if the calculations are off by some constant factors, this will not change the convergence or divergence of the above sum. Anyway, plugging this into our expression for the expected number of visits to 0 , we get

\mathbb{E}[T] \approx \sum_{k=0}^{\infty} \frac{1}{\sqrt{\pi k}} = \infty.

We expect to return infinitely many times to the origin, and thus the walk is recurrent – p_{\mathrm{ret}} = 1 .

Method #2: Escaping from finite boxes
This is a very neat method, because it explicitly shows us how hard it is for the random walk to travel long distances while avoiding returning to the origin.

Instead of looking at the infinite, rather harder-to-deal-with random walk, we can ask how a random walk behaves on finite intervals. That is, our walker will now be positioned at some point x inside a corridor of length n , and will randomly step either left or right until she exits the corridors through one of the sides:

We can think of this corridor as lying on the interval 1,2\ldots,n  , so when the walker exits from the left, she returns to the origin 0 , and when she exits from the right, she escapes to “infinity” (albeit for a very small value of infinity).

In this case we can do some exact calculations. For x \in \{0,\ldots,n+1\} , let’s denote by p_{n}(x) the probability that the random walker, starting at x , will exit through the right (i.e reaches “infinity”) before she exits through the left (i.e reaches 0 ). If we already happen to start at x = 0 , that probability is 0 , so p_{n}(0) = 0 always. Similarly, if we already start at n+1 , that probability is 1 , so p_{n}(n+1) = 1 . And for intermediate points, at each step we go either left or right with equal probability, so

p_{n}(x) = \frac{1}{2}p_{n}(x-1) + \frac{1}{2}p_{n}(x+1).

This is a second order linear recurrence relation, with p_{n}(0) = 0 and p_{n}(n+1) = 1 as boundary conditions. The general way to solve these recurrences is to first try a p_{n}(x) that is proportional to \alpha ^ x for some unknown \alpha . This reduces the recurrence relation to a polynomial equation:

\alpha ^ x = \frac{1}{2} \alpha ^{x-1} + \frac{1}{2} \alpha ^{x+1}.

Dividing by \alpha^{x-1} , this gives

(\alpha -1) ^2 = 0.

Since there is degeneracy in the solution, our next guess is to try p_{n}(x) proportional to x \cdot \alpha^x ; but for us \alpha = 1 , and indeed, plugging in p_{n}(x) = x solves the recurrence relation exactly! Taking care of the boundary conditions, the escape probability becomes

p_{n}(x) = \frac{x}{n+1}.

I suppose we could have guessed that from the onset, couldn’t we? Silly us.

Anyway, let’s see how this finite case helps us prove the infinite case. Towards contradiction, suppose that the random walk on \mathbb{Z} is transient, and let p_{\mathrm{ret}} < 1 be the probability that the walker, starting at 1 , returns to 0 (i.e the probability of escaping to infinity is 1-p_{\mathrm{ret}} ). In particular, for every n , the probability of hitting n before returning to 0 is greater than 1-p_{\mathrm{ret}} : At the very worst, when the walker escapes to infinity, she will reach every such n ; but there can also be cases where she does return to the origin, but just happens to first pay a visit to n along the way. But the probability of hitting n before hitting 0 is exactly p_{n}(1) , and we seen above that it goes like 1/n . This decays to 0 as n \to \infty , which contradicts the assumption that it is greater than 1-p_{\mathrm{ret}} .

Method #3: Electrical networks
This method is cool, because it freakin’ uses resistors.

This one will take a little bit more explaining than the other methods, because (a) we have to build an entire framework which converts “escape probabilities in random walks on graphs” to “voltages on networks of resistors”, and (b) I’ll show a bit more than we formally require for the proof. But it will be worth it, since afterwards we’ll be able to use this framework to prove all sorts of other things. Also, after we build this framework, the proof that \mathbb{Z} is recurrent will be like one line.

A “network of resistors” is basically exactly what you think it is: First, take your favorite graph and replace each edge between vertices x and y with a resistor of resistance R_{xy} . Second, attach electrodes to various vertices, so that you can control their potential. This can be used, for example, to set a fixed voltage between two given nodes (or between a node and infinity). In the simplest case, the resistance of each resistor is 1\Omega . Here is an example of a resistor network:

That’s it! With a resistor network in your possession, you can now ask all your favorite question from electronics 101, like “what is the voltage between node x and node y ”, “how much current flows through an edge xy ”, and “what is the effective resistance between node x and node y ”. Of course, depending on the graph, these might not always be easy questions.

There is a neat and simple way to connect resistor networks and random walks on graphs. The “conductance” of a resistor is defined as the inverse of its resistance: C_{xy} = 1 / R_{xy} . Given a resistor network, we can define a random walk with the following transition rule: Denote by C_x the sum of conductances of all edges incident to vertex x ,

C_x = \sum_{y \sim x} C_{xy}.

The probability to move from one vertex x to another y is 0 if they are disconnected, and

\mathbf{Pr}[x \to y] = \frac{C_{xy}}{C_x}

if they are connected. In a way, this rule makes the random walker mimic electricity: the walker has a higher probability of moving along edges with higher conductances, that is, paths of low resistance, just like how there is a stronger electrical current along paths of low resistance. In the simple random walk, the probability of going along each edge is equal, so simple random walks correspond to electric networks where all the resistors have the same resistance. That’s why we like unit resistors so much!

The correspondence between resistor networks and random walks might seem superficially simple, but it is actually surprisingly deep; in fact, the whole point of the theory is to prove interesting properties of random walks by proving analogous results on electric networks instead. A major player in this game is the concept of a “harmonic function”.

Definition: Let G(V,E) be a finite*, connected, positive weighted graph, i.e every edge xy \in E has some positive number C_{xy} attached to it. Let U \neq V be a nonempty subset of its vertices. A function f: V \to \mathbb{R} is called “harmonic on U ” if the value that it gives to a vertex x \in U is equal to the weighted average value of its neighbors. Formally,

f(x) = \frac{1}{\sum_{y\sim x} C_{xy}} \sum_{y\sim x} C_{xy} f(y).

Often U is called the “interior”, and the remaining vertices B := V \backslash U are called the “boundary”.

* Harmonic functions can just as well be defined for infinite graphs, but matters become more complicated in proving and stating some of the theorems. In any case, we will easily be able to take limits of finite graphs to show interesting results on infinite ones.

The averaging property of harmonic functions might appear docile at first, but actually it imposes some strong conditions on the function, from which many properties can be derived. But before we do that, let’s see two nice examples of harmonic functions.

Example 1: Let G be a finite resistor network, and consider the random walk on G defined by the network, where the probability of moving from one vertex to another along some edge is proportional to the conductance of the resistor along that edge. Let X,Y \subseteq V be two disjoint subsets of vertices. Think of X as a “good” set which we want to land in during the random walk, and Y as a “bad” set which we want to avoid during the random walk. Now let f_{XY} : V \to \mathbb{R} be the following function: for a vertex x \in V , f_{XY}(x) is the probability that if a random walker starts at x , she will hit the good set X before she hits the bad set Y . This is a purely probabilistic / combinatorial function, which only depends on the probabilities of moving from one vertex to the other.

Here are three of the nicer qualities of f_{XY} :

  • For every x \in X , we have f_{XY}(x) = 1 . This is because if we already started inside X , then of course the walk hits X before it hits Y ; it already has!
  • For every y \in Y , we have f_{XY}(y) = 0 . This is because if we already started inside Y , then there is no chance to hit X before hitting Y .
  • f_{XY} is harmonic in V \backslash (X \cup Y) . This is because if the walker is not in X or Y , then her next step will take her to one of neighbors, and we can ask the same question “what is the probability to get to X before getting to Y ” from that neighbor instead.

In this example, X \cup Y serves as the boundary of the harmonic function f_{XY} .

Example 2: Let G(V,E) be a finite resistor network. For each edge xy \in E , let C_{xy} = 1 /R_{xy} be its conductance. Let X,Y \subseteq V be two disjoint subsets of vertices. Connect all the vertices of X and Y to a voltage supply, so that the potential of all x \in X is 1 volt, and the potential of all y \in Y is 0 volts. Define a potential function \varphi_{XY} : V \to \mathbb{R} by setting \varphi_{XY}(x) to be the potential of the vertex x in volts. We can think of this as a purely physical function, which only depends on the resistances of the resistors in the network. If we wanted to, we could build the network out of real-life resistors and actually measure the potential differences! Anyway, here are three of the nicer qualities \varphi_{XY} :

  • For every x \in X , we have \varphi_{XY}(x) = 1 . This is by definition.
  • For every y \in Y , we have \varphi_{XY}(y) = 0 . This is also by definition.
  • \varphi_{XY} is harmonic in V \backslash (X \cup Y) (where the edge weights are given by the conductances C_{xy} ).

The harmonicity is a consequence of two well-known physical laws from electronics: Kirchoff’s circuit law for currents, and Ohm’s law. Kirchoff’s law states that the total amount of current entering and leaving a vertex must be equal. In other words, if I_{xy} is the current flowing from vertex x to vertex y , then

\sum_{y \sim x} I_{xy} = 0.

Meanwhile, Ohm’s law states that the current flowing through a resistor is the ratio between its potential difference and its resistance (also known as “Uri’s law”, since it can be symbolically written as U=RI ). Plugging this into the equation above, we get

\sum_{y \sim x} \frac{\varphi_{XY}(y) - \varphi_{XY}(x)}{R_{xy}} = 0.

Extracting all instances of \varphi_{XY}(x) to one side and using the notation C_{xy} = 1 / R_{xy} , we finally get

\varphi_{XY}(x) = \frac{1}{\sum_{y\sim x} C_{xy}} \sum_{y\sim x} C_{xy} \varphi_{XY}(y).

The two functions we built above, f_{XY} and \varphi_{XY} are quite similar. “Too similar, in fact…”, you might be thinking. And you’d be right, and this can be shown in a straightforward way if you inspect the calculations we did closely enough. But rather than do that, I’d like to show the power of the averaging property of harmonic functions instead. One of the more famous / notorious / useful properties of harmonic functions is called the maximum principle, and reads as follows:

Theorem (the maximum principle): A harmonic function f attains its maximum value and minimum values on the boundary B .

I always picture the proof of this as a “wave of maximality” which erupts in the interior of the graph and spreads outwards. It goes like this. Suppose that f attains the maximum somewhere in the interior, on some vertex x\in U . By the averaging property, f must attain the maximum value on all of x ‘s neighbors as well. Now carry on with this process, showing that all the neighbors of neighbors of x , then the neighbors of neighbors of neighbors of x , and so on, all attain the maximum, until you hit a vertex in the boundary. The maximum must then occur on the boundary!

Here, M denotes the maximum value of the function. The initial vertex is colored purple, and the maximum wave moves to the left.

With the maximum principle, a wonderful uniqueness theorem is almost immediate.

Theorem (the uniqueness theorem): Let f_1 and f_2 be harmonic on U \neq V . If they are equal to each other on the (nonempty) boundary B , then they are equal everywhere.

To see this, observe that the function g = f_1 - f_2 is also harmonic on U . Since f_1 and f_2 agree with each other on B , then g takes only the value 0 on B . By the maximum principle, the value 0 is then both the maximum and the minimum of g , so it must be 0 everywhere, and hence f_1 = f_2 .

This is a fantastic theorem. It allows us to show that two seemingly different functions are actually the same, provided we can show that they are both harmonic and agree on a possibly-very-small boundary set.

Hey, now wait a minute! This is exactly what we did in the two examples of f_{XY} and \varphi_{XY} . Both functions are harmonic in U = V \backslash (X \cup Y) , and both agree completely on the sets X and Y . Thus the two are exactly equal! For random walks on finite graphs, the probability to reach a set X before reaching a set Y when starting the walk from a given vertex x , is exactly equal to the electric potential of that vertex in a network of resistors, when X is held at constant potential 1 and Y is held at constant potential 0 .

As cool as this result is on its own, it also gives us a way to check whether a graph is recurrent or not. The basic technique is actually the same as the previous method, that of escaping from finite boxes, but the language of resistors grants us easier calculation and easier modification, as we will see in the next post in the series.

But for now we’ll stick to basics. Let G(V,E) be a finite graph, and let a \in V . Let Y be a set that does not contain a . We consider a to be the “origin” of the graph, and Y to be a set of bad vertices which we want to avoid (our “finite version” of infinity, as before). Given this, we want to find the following: What is the probability that a simple random walk which starts in a returns back to a before reaching Y ? To calculate this, turn G into a resistor network by replacing all its edges with 1\Omega resistors. As noted above, this choice of resistor values corresponds to the simple random walk on G . Now fix the vertex a to have a potential of 1 volt, and all of Y to have a potential of 0 volts. What is the current I_a flowing between a and Y ? Well, by Ohm’s law,

I_a = \sum_{y \sim a} (\varphi(a) - \varphi(y)) C_{ay}

= \sum_{y \sim a} (\varphi(a) - \varphi(y)) \frac{C_{ay}}{C_a} C_a.

Now, recall that the walk defined by a resistor network has the transition probabilities \mathbf{Pr}[x \to y] = \frac{C_{xy}}{C_x} . Thus that last equation can be written as

= (1 - \sum_{y \sim a} \mathbf{Pr}[a \to y]\varphi(y) ) C_a.

But look at the summands in this sum: By the equivalence between voltages and return probabilities that we just established, \varphi(y) is equal to the probability that the walk, starting at y , will return to a before hitting Y . Since we sum over all neighbors y of a and multiply this by the probability of transitioning from a to y , the entire term

(1 - \sum_{y \sim a} \mathbf{Pr}[a \to y]\varphi(y) )

is just equal to the escape probability, that is the probability that if we start at a , the random walk will hit Y before it gets back to a ! Symbolically, may then write this as

I_a = C_a \cdot p_{\mathrm{esc}}.

All that is left is to take care of the current I_a . What is it? Well, by definition, it is the current flowing form a to Y , and since there is a unit voltage difference between them, by definition / Ohm’s law, it is just equal to the effective resistance between them! We get that for finite graphs

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

We can now finally (and easily) prove that \mathbb{Z} is recurrent. Let’s look at the boxes [-n,n] . Let X = {0} and Y = \{-n,n\} ; a random walker has to pass through Y at some point if she wishes to run off to infinity. The probability that a simple random walk which starts at 0 will return to 0 before hitting either of the boundaries of the box is then just proportional to the effective resistance between 0 and the boundaries. The electric circuit looks like this (after “folding” the circuit in two):

The circuit consists of two parallel sets of n unit resistors in series. By simple resistance laws, we can replace each series of n resistors with one large resistor of resistance n , and then replace the two resultant parallel resistors by a single resistor of resistance n/2 . Thus, as n \to \infty , the effective resistance goes to 0, and the escape probability goes to 0. \mathbb{Z} is recurrent!

We have seen three methods which show that the simple random walk on Z is recurrent. The first was a direct counting argument, the second considered the escape probabilities from finite boxes, and the third generalized the second, showing how the escape probabilities relate to the effective resistance of electric networks. True, given that the second method already gave us the desired result, the electric network method is a bit of an overkill in this case. But in the upcoming posts, we will see how it can be used in \mathbb{Z}^2 and \mathbb{Z}^3 , where the second method is a lot harder to apply directly.

Until next time, here is a quick puzzle. Below are two different infinite trees. Can you tell whether they are recurrent or transient?

The binary tree. Each vertex has two offspring.

The 3-1 tree. If a vertex is on the right half side of the tree, it has only one offspring. If it is on the left half side of the tree, it has three.

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