A few days ago I saw this comic reposted, and I thought: wait! Unlike every prior time I have seen this comic, I actually know how to solve this now!

One thing which I often find really cool, and which I don’t think comes up a lot in most people’s mathematical education, is when you can learn something about some thing non-random by analysing a random process. So, let me show you a way to find out the resistance between two points in a circuit by instead finding out the number of times someone randomly walking around that circuit will step on those points.

Equivalent Resistance

Here’s a closeup of the problem:

You may be familiar with the rules for series and parallel resistors from high school: if there are some resistors in series (one after another), this is “equivalent to” having a single resistor in the circuit which has a resistanceequal to the sum of their resistances. That is, if you replace the resistors with just one of resistance , the behaviour of the rest of the circuit will be the same.

If there are some resistors in parallel, this is “equivalent to” having a single resistor in the circuit which has a conductance (the reciprocal of the resistance, ) equal to the sum of their conductances.

This question is asking us for a similar thing: some single resistance, so that our entire infinite circuit is like having just a single resistor with that resistance between the two marked nodes. Unfortunately, the series and parallel resistor rules are totally useless to us; none of the resistors in the problem are in series or parallel! So our first challenge is moving beyond the domain of grade ten physics and into the domain of grade twelve physics.

Circuit Laws

You’ve probably encountered Ohm’s law, which relates the electrical current between two points in a circuit to the difference in their electrical potential (the voltage) and the resistance between them:

Here means the current from to , is the potential at point (I don’t want to use because we’re going to use that later, sorry), and is the resistance of the edge between and . This law already is a very good start, because if we can set up some situation where electricity is flowing in our circuit and we know the current and potential difference between the two marked nodes, then we can directly calculate what single resistance is equivalent to the entire circuit: we just divide the potential difference by the current.

However, with only this law, though, there are lots of possible electrical flows in our circuit. For example, if we attach the leads of a one volt battery to our two nodes, maybe the electrical potentials look like this:

Where all the points in the green zone have potential 1V, all the points in the pink zone have potential 0V, and the only current is on the cyan arrows — there’s no current at all to or from the marked nodes. This diagram satisfies Ohm’s law; there’s zero potential difference in within the region, so no current, and the current across the border matches the voltage divided by the resistance. But this picture doesn’t make any physical sense. We know that electrons can’t endlessly be taken from the nodes on the right side of the border and given to the nodes on the left side of the border without any electricity actually being drained from the battery. The issue is that this violates Kirchoff’s current law, which says that the net current to and from any particular point is zero; that is, the outgoing current and the incoming current are the same amount.

If there’s a current from to , then that’s the same as a negative current from to , so this says: the sum of all the currents (i.e., to each node ) away from minus the sum of the currents (from each node ) towards is equal to zero. With both of these equations together, we have all the pieces we need. If we attach our battery, there’ll only be one way we can assign currents and voltages so that both equations are satisfied.

There are two different ways we can solve for the equivalent resistance. We can attach a battery with a specific voltage to the two nodes, find the current, and then use Ohm’s law to calculate the resistance:

A 1V battery attached to the marked nodes

Or, we can force current through the two nodes, adding charge to one node and taking it out of the other node, and find the voltage that this induces:

A 1A current source attached to the marked nodes

Both ways work, but I’ll be doing the latter here. There’s no strong reason to, other than convention; it makes some later stuff slightly easier, but you can do it the other way if you like. Our plan is thus: force one unit of current into one of the red nodes and take one unit of current out from the other. There will be some way to assign a potential to each node such that the current into and out of each node will be net zero. Find a valid way to do that, read out the difference in potentials, use Ohm’s law (since we know the current; it’s what we forced it to be), and finally get the equivalent resistance.

So we need to figure out a valid way of assigning potentials.

A System of Equations

First, let’s assign each point on the grid a coordinate:

The same circuit but with each node marked with coordinates.

Instead of “the marked nodes”, from now on we’ll talk about the nodes and .

Now, from Kirchoff’s current law, we know that a valid assignment of currents has to satisfy an infinite set of equations like this (one for every set of coordinates ):

We can use Ohm’s law to expand out these terms:

Which, since every resistance is one, is…

Expanding out each of the four terms, we get:

With the exception of the two nodes (where the right side is , because we’re forcing one unit of current into node ) and (where the right side is , because we’re forcing one unit of current out of node ).

(Note that there will be an infinite number of solutions to this system of equations — if we have a solution, and we add the same amount of potential to every node, each equation will still be satisfied. However, if we pick two nodes, the difference in their potentials will be the same no matter which solution we’ve found. This makes sense, physically; we can assign any arbitrary number as the potential of each node, but the voltage, the difference between nodes, is what determines the current.)

This system of equations comes up in graph theory, and there’s a standard way of solving it, which I’ll go over briefly. First, we set up a matrix . Each column and each row of corresponds to a node of the graph, and if in the graph there is an edge between the nodes and , then we set . Then, for each node we set equal to the number of edges coming out of node (in this case, always ). Next we try to solve the equation:

(The and wouldn’t have to be next to each other or at the end of the vector, just wherever the relevant nodes are). The idea here is that is our vector of potentials — is the potential at node — and by multiplying the vector by the relevant row of the matrix and setting it to the element on the right side, we force each equation to be satisfied. This matrix is called the Laplacian, and it’s useful for all sorts of things.

The issue in our case is that our grid is infinite! We can imagine if we like an infinitely large matrix, but it won’t help us, because none of the methods we use to solve matrix equations will work. We could try to find the answer as a limit of increasingly large matrices, but then we get all these awkward boundary points which would make it way harder to calculate our potential vector. So that’s no good. However, there’s another area of mathematics which often involves solving infinite systems of linear equations…

Random Walks

Let’s talk about the simple random walk on the 2D grid. We start at the point . Each step, we move either one unit up, one unit down, one unit right, or one unit left, each with equal probability — so we have a chance of moving in any particular direction. The direction we move on a particular second is totally independent of the directions we’ve moved before (this independence makes a random walk a Markov process; the defining feature of a Markov process is that what happens in the future only depends on what state you’re currently in). Here’s an example walk which is seven steps long:

Now imagine we have a function which outputs something about what we should expect to happen in the future given that we’re currently at grid position . As long as we don’t reference any past moves, such a function will be well-defined (that is, it will take exactly one value per assignment to its arguments) — the history doesn’t change our future behaviour except through what node we’re currently on. Lots of such functions will, for almost all points, satisfy an equation that looks like this:

For example, consider the function which equals the expected number of steps that we’ll take to hit the node , given that we’re currently on the node. , since we’re already there. For every other node, the expected number of steps to hit will be one plus the expected number of steps once we’ve taken a step. Since there are four directions and we have a chance of stepping in each of them, and is the expected number of steps if we land on the node ,

This kind of equation looks a lot like the equation we need to solve to find out our electrical potentials! Our system of equations above, if we rearrange it, is:

For , and:

So if we can figure out what that function is in the context of the random walk, and we can figure out what it represents, we can solve the original problem by solving that.

Note that our example function gains one on every step, and our function here gains one quarter on the node and loses one quarter on the node . Another way to phrase the behaviour of is that it’s the number of times we visit any node; we can extend this to talk only about visits to some nodes. Specifically: if we count up by every time we visit , and down by every time we visit , then what we’ll get is exactly the formula above.

The Potential Function

Say we start on node and we walk for steps. We’ll define as the probability that, after we do our steps, we’re on the node . For example, , since if we take zero steps we don’t move from the node we started on, and , since from in one step we have a chance of moving to each of the adjacent nodes. Then, in terms of this function , the function we want is something like:

We go through steps, starting at node , and at each step we add the probability that we’re on point and subtract the probability we’re on point . Since the expectation is linear, this is the expected number of times we’ll be on after steps minus the expected number of times we’ll be on .

There’s only one issue. With our example , we may have needed to take arbitrarily many steps to get to ; we were adding up all the possibilites, including ones where we reach arbitrarily far in the future. So to get the proper we want, we need to take the limit as the number of steps we’re considering goes to infinity:^[1]

Now, since the situation is symmetric, the expected number of times we’ll visit starting on is the same as the expected number of times we’ll visit starting on , and the expected number of times we’ll visit starting on is the same as the expected number of times we’ll visit starting on . That is,

Since that’s the case, if we want to find the potential difference between the marked nodes in the original problem, all we need to do is calculate ; we can double it to get the difference.

So now we’ve reduced our electrical problem to a purely probabilistic one: if we start on and we do a simple random walk for infinite steps, on average, how many more times will we have visited than ? If we can solve this problem, we can directly determine the effective resistance between and on an infinite grid of resistors! I find this kind of thing really cool; we had a pure object with no randomness at all, and somehow, if we can answer a question about the behaviour of a related random process, we can answer questions about the original object.

(If you remember that we could have attached either a battery or a current source, you might be wondering what we would do if we had attached a battery. The question we would have had to answer then is “what’s the probability that we visit for the first time before we revisit ”? This question would have an answer equal to the reciprocal of the question we’re answering in the current source case, since the number of amps induced by one volt is the reciprocal of the number of volts induced by one amp. Incidentally, if you start with a random walk, this is a pretty cool proof that these quantities are the reciprocal of one another — convert the random walk to a circuit and you can show that the two have to be reciprocals because of Ohm’s law! It’s pretty crazy to be able to say “in a random walk, the probability of visiting a point before revisiting your starting point is the reciprocal of the number of extra times you visit the first point in an infinite walk, because of Ohm’s law”.)

Fourier Analysis^[2]

(This is the part where I lose the last of the non-mathematicians. If you don’t know what’s going on, just skip to the end.)

First, let’s simplify our notation a little. We only care about , which is:

We don’t actually need that first argument of , since it’s always . Let’s simplify things and cut it out; we’ll just say that is the probability we’ll be on node after steps of a random walk which starts on .

Now we have to solve the problem:

Unfortunately, this seems pretty hard to do. In fact, it looks like our situation is even worse than it was before; before, we had only one infinity to deal with (the number of nodes) and now we have two (the number of nodes AND the number of steps). It would be really nice if we could get rid of some of these infinities. There’s an obvious (?) way to resolve one of the infinities: if we could somehow turn this into a geometric series, we could use the identity . This isn’t as crazy as it sounds. A natural way to express Markov processes is in terms of their transition matrix , where is the probability of going to state in the next step if you’re currently in state . Then the probability of being in state at step , given that you started in state is just , where is the vector with s everywhere except for a in position . So maybe we could phrase our function as something like: ? Unfortunately, we can’t use our geometric series identity on matrices, and anyway, dealing with infinitely large matrices was what we were doing all this work to avoid! But this sort of indicates that maybe this is a productive direction to go in, and it turns out^[3] that we can express in terms of something that looks like , using a Fourier series. If we define the characteristic function of the function as:

(that is, just the standard Fourier series of ), then we get that our exponentiation works exactly as we like:

To see this, note that is just the expectation , where and are the random variables representing the current position after steps. Then if is the random variable representing the change in the coordinate on step , and is likewise but for the coordinate, then:

Basically, each step is drawn from the same set of possibilities and with the same probabilities, so the only thing that matters is what the first step looks like. This is the essential property of a random walk which distinguishes it from other Markov processes; a random walk has to be the same no matter where you start from. Anyway, now we have the convenient exponentiation that we want. Extra conveniently, this also gets rid of the infinite node problem! Since all the transition probabilities are the same no matter where in the grid we are, we only need to sum up the bit right next to the starting node: we solve both our infinities at once. In the end, we have that:^[4]

There’s only one remaining problem: we have a problem phrased in terms of , not in terms of . How do we go from the former to the latter? Well, it turns out that:

…Listen. I don’t know why this works either. You’ll just have to take this one on faith. Or read the Wikipedia article on Fourier series. Anyway, if we take this as given, we now have all the pieces we need — all that’s left is to solve some integrals.

(Where the unmarked symbols are integration over the square). Now we can expand out the :

And throw the whole thing in Wolfram Alpha (I refuse to solve an integral by hand):

So then since the potential difference between and is double that in volts, and the current is one amp, the equivalent resistance is ohms. And we’re done!

Recap

So our solution went like:

We want to solve for the equivalent resistance between two points of a circuit;
to do that, we have to figure out how much voltage is induced when we impose a current;
to do that, we have to solve an infinite system of linear equations;
we can consider that same system of linear equations as representing something else, in particular a random walk;
so we can use the tools we have for analysing random walks to solve our system of equations;^[5]
thus we can solve our system of equations by answering how many extra times we expect to visit the starting point in a random walk, over the point we’re calculating the resistance to;
…and then turn that solution back to into a solution for our original problem.

And now you are immune to being paralysed in front of a truck. :)

^
This limit does exist, but I won’t prove it because it would take a while. The book “Two-Dimensional Random Walk” by Serguei Popov includes a nice coupling argument on page 46, if you want to check it out.
^
A lot of this final section is adapted from the book “Principles of the Random Walk” by Frank Spitzer. Also, for various parts (e.g. the battery/current source connection) I used “Random Walks and Electrical Networks” by Doyle and Snell, and the book mentioned in the footnote above, “Two Dimensional Random Walk” by Serguei Popov. If you want a fuller treatment of this topic, I’d recommend skimming the relevant sections of these books.
^
I always hate it when people say “it turns out” in mathematics, because I want to know how you would figure it out, not just what the answer is! But since I know basically no analysis I have no idea how you would figure this out. So I can’t tell you, and “it turns out” it is.
^
I’m cheating here by pretending that you can actually treat this as a geometric series without any justification. If we wanted to be rigorous, we would show that the partial sums converge as , and furthermore that this is actually integrable; we’ll skip over all of that because it’s complicated. It all works out, trust me.
^
Unfortunately, we didn’t end up using any actual probability theory, which would have been nice. Maybe I will write a post about the probabilistic method…

The Problem in the “Nerd Sniping” xkcd Comic