My solution to the XKCD Puzzle
Basically, we consider each possible path from the source — which we’ll assume is at the origin of our lattice — to the target — which will be at lattice coordinates — as a series circuit, and the collection of all possible paths is a giant parallel circuit. If a given path has length it passes through resistors, and so its total resistance is . Thus we need to form the sum over all paths
and take the reciprocal of this sum. So we’ve got a combinatorial problem: how many lattice paths have length and go from the origin to ? Let’s call this number and build the “exponential generating function”
We choose the exponential generating function here rather than the ordinary generating function because of a manipulation we want to do later that looks nicer for exponential generating functions. We’ll go from to our desired sum a little later.
For now, let’s consider a simpler generating function. Consider the number of paths on a one-dimensional lattice with length that start at and end at . First off, if we have no paths that work. Similarly, if is not divisible by we won’t have any good paths. But when , there are generally many different paths. How do we get our hands on one? Choose steps to take left and the other to take right, and we’ll end up steps to the right. So we set to get the exponential generating function
where is a Bessel function of the first kind.
Now a path in the two-dimensional lattice is really a mixture of two one-dimensional paths. That is, we break our steps up into chunks of and steps, respectively, put a one-dimensional path on the chunk ending at , and put a one-dimensional path on the chunk ending at . And it turns out that generating functions are perfect for handling this!
This tells us how to find the number of paths of length that end at — it’s just the th derivative of this power series, evaluated at . That is
Now let’s consider the ordinary generating function for :
Here the coefficient of is the number of paths of length (and thus with resistance ) from the origin to . What we want to calculate is the sum . To get at this, we’ll divide our power series by and then integrate with respect to . This will give the series , which we can then evaluate at . Notice that we never have any paths of length zero unless we’re counting up the reciprocal resistance from the origin to itself, which should definitely be infinite anyway, so dividing by isn’t really a problem.
Now I admit there’s one glaring problem here: I don’t know offhand how to go from an exponential generating function to an ordinary generating function, much less how to integrate what we get from doing that to this product of Bessel functions.
[UPDATE]: I was just working on some numerics and there’s a problem here somewhere. The coefficients are off, but by a (sort of) predictable amount. I don’t really have time to fix this now, so I’ll come back with more later.
[UPDATE]: Okay, I see what’s wrong now. I’m adjusting what I said above.
[UPDATE]: Someone pointed out to me that after all of this I need to do a renormalization just like for the path integrals in quantum field theory. That is, in the above I need to restrict to paths that never hit the same edge twice, which is a harder combinatorial problem than I expected.
Still, it’s nifty to see the Bessel functions…