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<a$ 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…

About these ads

December 14, 2007 - Posted by John Armstrong | Uncategorized

4 Comments »

I don’t think it’s quite so complicated; I seem to recall seeing a solution to a very similar problem (the locations on the grid were different, but everything else was the same) that was only a couple lines. Unfortunately I have no idea where I saw it.

Comment by Isabel | December 14, 2007 | Reply
I’ve also seen simple solutions, but usually they’re for only one choice of terminal point, and I’m not quite sure I buy them. It doesn’t help that I’ve seen multiple “simple” solutions.

One in particular for the resistance across a single resistor claims to get 1/2 an ohm in two different ways. The first involves some hand-waving about impedance that I’m not sure I trust, and the second seems to completely neglect all the other closed paths that get back around from one point to the other. And this is among the clearest expositions I could find.

Basically, to whatever extent one or another special case I’ve seen turns out to be right, there seems to be almost no concept of “what’s really” going on here, which leads to a true understanding of not only the special case, but of the problem as a whole. My solution, on the other hand, recognizes the basic idea as thinking of the whole grid as a massively parallel circuit, and the calculation to actually be a discretized path-integral. At each step (modulo an error I’m about to fix) it’s clear what we’re counting or adding up, and what relation that part has to the whole. The only problem is that I don’t yet know how to extract an answer from the framework.

Comment by John Armstrong | December 14, 2007 | Reply
See http://aps.arxiv.org/abs/cond-mat/9909120 for solutions in terms of lattice Green functions for various lattices. For this particular problem the answer would be 4/pi-1/2.

Comment by Curioso | December 15, 2007 | Reply
This isn’t particularly useful for the problem, but it’s a nice little thing I found while I was working on it.

When a+b has the same parity as n, G_{a,b,n} is just (n choose (a+b+n)/2) (n choose (a-b+n)/2). (Otherwise, it’s zero, of course.)

This is because you need to choose exactly (a+b+n)/2 steps in the path to go either up or right, and exactly (a-b+n)/2 steps to go either down or right.

Comment by Anton Malyshev | December 18, 2007 | Reply

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects
Archives

December 2007

M T W T F S S

« Nov Jan »

1 2

3 4 5 6 7 8 9

10 11 12 13 14 15 16

17 18 19 20 21 22 23

24 25 26 27 28 29 30

31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider