The Unapologetic Mathematician

My solution to the XKCD Puzzle

So here’s how I’ve been thinking about that XKCD puzzle. My approach is essentially an exercise in the techniques covered in John Baez’ Quantum Gravity seminar for 2003-2004.

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 $(a,b)$ — as a series circuit, and the collection of all possible paths is a giant parallel circuit. If a given path has length $n$ it passes through $n$ resistors, and so its total resistance is $n$. Thus we need to form the sum over all paths

$\displaystyle\sum\limits_{\gamma}\frac{1}{\mathrm{length}(\gamma)}=\sum\limits_{n=0}^\infty\frac{\#\{\mathrm{length}(\gamma)=n\}}{n}$

and take the reciprocal of this sum. So we’ve got a combinatorial problem: how many lattice paths $\gamma$ have length $n$ and go from the origin to $(a,b)$? Let’s call this number $G_{a,b,n}$ and build the “exponential generating function”

$\displaystyle\Gamma_{a,b}(t)=\sum\limits_{n=0}^\infty\frac{G_{a,b,n}}{n!}t^n$

We choose the exponential generating function here rather than the ordinary generating function $\sum G_{a,b,n}t^n$ because of a manipulation we want to do later that looks nicer for exponential generating functions. We’ll go from $\Gamma_{a,b}$ to our desired sum a little later.

For now, let’s consider a simpler generating function. Consider the number $U_{a,n}$ of paths on a one-dimensional lattice with length $n$ that start at ${0}$ and end at $a$. First off, if $n we have no paths that work. Similarly, if $n-a$ is not divisible by $2$ we won’t have any good paths. But when $n=2k+a$, there are generally many different paths. How do we get our hands on one? Choose $k$ steps to take left and the other $k+a$ to take right, and we’ll end up $a$ steps to the right. So we set $U_{a,2k+a}=\binom{2k+a}{k}$ to get the exponential generating function

$\displaystyle\Upsilon_a(t)=\sum\limits_{k=0}^\infty\frac{U_{a,2k+a}}{(2k+a)!}t^{2k+a}=\sum\limits_{k=0}^\infty\binom{2k+a}{k}\frac{1}{(2k+a)!}t^{2k+a}=i^{-a}J_a(2it)$

where $J_a(x)$ 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 $n$ steps up into chunks of $n_1$ and $n_2$ steps, respectively, put a one-dimensional path on the $n_1$ chunk ending at $a$, and put a one-dimensional path on the $n_2$ chunk ending at $b$. And it turns out that generating functions are perfect for handling this!

$\displaystyle\Gamma_{a,b}(t)=\sum\limits_{n=0}^\infty \frac{G_{a,b,n}}{n!}t^n=\sum\limits_{n=0}^\infty \left(\sum\limits_{n_1+n_2=n}\binom{n}{n_1}U_{a,n_1}U_{b,n_2}\right)\frac{t^n}{n!}=$
$\displaystyle\sum\limits_{n=0}^\infty\sum\limits_{n_1+n_2=n}\frac{U_{a,n_1}}{n_1!}\frac{U_{b,n_2}}{n_2!}t^{n_1+n_2}=\sum\limits_{n_1=0}^\infty\frac{U_{a,n_1}}{n_1!}t^{n_1}\sum\limits_{n_2=0}^\infty\frac{U_{b,n_2}}{n_2!}t^{n_2}=$
$\displaystyle\Upsilon_a(t)\Upsilon_b(t)=i^{-a-b}J_a(2it)J_b(2it)$

This tells us how to find the number $G_{a,b,n}$ of paths of length $n$ that end at $(a,b)$ — it’s just the $n$th derivative of this power series, evaluated at $t=0$. That is

$\displaystyle G_{a,b,n}=\frac{d^n}{dt^n}\left(i^{-a-b}J_a(2it)J_b(2it)\right)$

Now let’s consider the ordinary generating function for $G_{a,b,n}$:

$\displaystyle\sum\limits_{n=0}^\infty G_{a,b,n}t^n$

Here the coefficient of $t^n$ is the number of paths of length $n$ (and thus with resistance $n$) from the origin to $(a,b)$. What we want to calculate is the sum $\sum\frac{G_{a,b,n}}{n}$. To get at this, we’ll divide our power series by $t$ and then integrate with respect to $t$. This will give the series $\sum\frac{G_{a,b,n}}{n}t^n$, which we can then evaluate at $t=1$. 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 $t$ 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.

Any thoughts?

[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…

December 14, 2007 Posted by | Uncategorized | 4 Comments