Steve Witham wrote:

Here's a comic with an interesting random-walk problem:

http://www.xkcd.com/356/

The problem in question was

On an infinite square lattice with equal unit resistances along each edge, find the resistance between two nodes at a knight's move from one other.

Nobody's described the precise connection with random walks, so I'll bring this into the conversation: the effective resistance between (0,0) and (1,2) is equal to the reciprocal of 4p, where p is the probability that a random walker who starts at (0,0) will hit (1,2) before returning to (0,0). (With probability 1, the walker will eventually hit one or the other.) Here 4 arises as the sum of the reciprocals of the resistances on the edges incident to (0,0). If we used (1,1) in place of (1,2), the probability in question would be Pi/8. If you want to know why this equality is true, see Doyle and Snell's "Random Walks and Electric Networks", available at math.PR/0001057. By the way, what Fred Lunnon calls "admittence", namely the reciprocal of resistance, is something I always thought was called "conductance". Is this ones of those transatlantic terminological differences? I asked Google, and it gave 0 results for "electrical admittence", about 5700 results for "electrical admittance", and about 76300 results for "electrical conductance". To determine whether use of admittance vs. conductance correlates with geography, we'd need a hybrid of the Google search engine with Google Maps that instead of just counting hits would show us a map of the world with each hit represented by a red dot at the physical location hosting the site. :-) In any case, one way to estimate the effective resistance is to estimate p. How might we do this? If we do a pseudorandom simulation of n runs of random walk, and let k be the number of successes (where success is defined as the event that the walker hits (1,2) before hitting (0,0)), then k/n should be close to p, with an error on the order of 1/sqrt(n). To get our error down to 1/10^5, we'd need to do ~ 10^10 runs, which is clearly not feasible. Of course, we could exploit parallelism and do 10^10 runs in tandem. (We don't have to follow the 10^10 walkers individually; we just need to know how many are at a given node at each time-step.) The trouble is that some of the 10^10 walkers won't hit either (0,0) or (1,2) within a computationally feasible amount of time. (In fact, it'd take about exp(10^10) steps for all the walkers to get absorbed!) So our estimate will be an interval [k/n,k'/n] rather than a single number. Some of the error comes from the width of this interval; other error comes from the randomness in the procedure. A better way is to numerically simulate a discrete-time deterministic mass-flow in which 1 unit of mass enters the system at (0,0) at the start and flows through the system according to the rule that the mass at a node gets divided equally among its four neighbors at the next time-step, with mass exiting the system at (0,0) and (1,2). If you could do this for an infinite number of steps, the amount of mass leaving the system via (1,2) and via (0,0) would be p and 1-p, respectively. If you simulate the flow for n steps, then (leaving aside rounding error) your error will be bounded by the amount of mass that doesn't get absorbed in the first n steps. (Peter Doyle tells me that the real industrial-strength way to solve many problems of this sort is with something called the conjugate gradient method. I haven't had time to learn this technique, but if you want to, check out http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf ; Shewchuck's write-up looks quite friendly.) If I were applying for a job at Google, I'd probably try to get an approximation to p via the rotor-router method of deterministically estimating characteristics of random processes (on the assumption that the hiring committee is more interested in seeing originality than perfect mathematical precision). For a description of rotor- routing, see Michael Kleber's article "Goldbug Variations" in the Winter 2005 issue of The Mathematical Intelligencer (available at http://people.brandeis.edu/~kleber/Papers/rotor.pdf). If you go to http://www.cs.uml.edu/~jpropp/rotor-router-model/, click on "The Applet", set the Graph/Mode selector to "2-D Walk", and press "Paused (Press to Resume)", you'll see how rotor-routing can be used to get decent approximations to Pi/8. (When you get bored, hit "Running (Press to Pause)" and change "1 Step" to "1 Stage" or "10 Stages" or "100 Stages".) What works for (1,1) should work for (1,2), so I expect that 10^5 runs of rotor-router walk with emission at (0,0) and absorption at (0,0) and (1,2) would give an estimate of p with an error on the order of 1 part in 10^5. (The best result I can prove is that the error for n runs goes like (log n)/n or smaller, but for values of n at least up through 10^4, that log n might as well be replaced by a small constant like 2, as far as I can tell.) This sort of simulation can be parallelized, so I suspect 10^5 runs would be feasible, though the set of sites visited would be a square of size roughly 10^5 by 10^5, so keeping track of all the rotor-settings might be a problem unless one used an intelligent scheme of memory-management (making use of the fact that throughout large patches of the square, the rotor setting is locally constant). I can give more details (and maybe even try to do the simulation) if people are interested. Jim Propp