callahan@cs.jhu.edu (Paul Callahan) (02/24/91)
Is there a closed form solution for the effective resistance between two points on an infinite 2-D mesh whose edges are unit resistors? Ideally, I would like a formula in terms of x and y, the coordinates of one point, assuming the other is the origin. I can see how to approximate the answer by considering the effective resistance between two points on a continuous infinite resistive sheet, so the resistance should grow roughly logarithmically with the Euclidean distance between the points. A related question (which might have a nicer closed form) would be the branch current for each resistor in the mesh assuming two points are put at some fixed potential. Again, it would be useful to have a formula in terms of the coordinates. A problem that turns out to be related (which is what I'm really interested in) is the following. Consider a random walk on an infinite mesh in which each step consists of choosing one of the four incident horizontal and vertical edges with equal probability. Suppose the walk starts at the origin. What is the expected number of times that such a walk will return to the origin before arriving at the point (x,y)? Can this be expressed as a simple formula in terms of x and y? I've browsed through Doyle and Snell, _Random Walks and Electrical Networks_, which deals with this sort of thing, but I don't have access to a copy right now. Pointers to any other appropriate references would be appreciated. -- Paul Callahan callahan@cs.jhu.edu
delliott@cec2.wustl.edu (Dave Elliott) (02/24/91)
In article <callahan.667353668@newton.cs.jhu.edu> callahan@cs.jhu.edu (Paul Callahan) writes: >Is there a closed form solution for the effective resistance between two >points on an infinite 2-D mesh whose edges are unit resistors? Ideally, I >would like a formula in terms of x and y, the coordinates of one point, >assuming the other is the origin. I can see how to approximate the answer >by considering the effective resistance between two points on a continuous >infinite resistive sheet, so the resistance should grow roughly logarithmically >with the Euclidean distance between the points. A related question (which >might have a nicer closed form) would be the branch current for each resistor >in the mesh assuming two points are put at some fixed potential. Again, >it would be useful to have a formula in terms of the coordinates. > >A problem that turns out to be related (which is what I'm really interested in) >is the following. Consider a random walk on an infinite mesh in which each step >consists of choosing one of the four incident horizontal and vertical edges with >equal probability. Suppose the walk starts at the origin. What is the expected >number of times that such a walk will return to the origin before arriving >at the point (x,y)? Can this be expressed as a simple formula in terms of >x and y? > >I've browsed through Doyle and Snell, _Random Walks and Electrical Networks_, >which deals with this sort of thing, but I don't have access to a copy right >now. Pointers to any other appropriate references would be appreciated. > >-- >Paul Callahan >callahan@cs.jhu.edu One case of this problem is a famous EE problem... the case in which the two nodes are neighbors on the grid. The solution in that case is easily obtained by a method which is also good (but not easy) for the posted problem. The method is simply to put a ground "at infinity" and note that it cannot affect the answer. Then use the superposition principle (Ohm's law, here). First consider a 1 ampere source at the first node (with sink at infinity) (origin) *only* and note that each of the 4 outgoing resistors must carry 1/4 ampere by symmetry. Now consider a 1 ampere sink at the neighboring (second) node *only*, with again 1/4 amp flowing *in* on each incoming resistor from the source at infinity. Now you can superpose, and remove the ground at infinity because it draws no current, to get a 1/2 amp current in the resistor joining the two nodes. The general problem posted requires that the currents for the symmetric problem be solved for all branches; but that is still easier than a direct attempt without using the above trick. The problem has also been posed and solved in the neighboring-vertex case for the graphs of the regular polyhedra ... all this goes back to 1953, and wasted an immense amount of time for EE students who could not accept the above mathematical argument and tried approximations of the grid (which converge unbelievably slowly). David L. Elliott Dept. of Systems Science and Mathematics Washington University, St. Louis, MO 63130 delliott@CEC2.WUSTL.EDU
greg@garnet.berkeley.edu (Greg Kuperberg) (03/01/91)
In article <callahan.667353668@newton.cs.jhu.edu> callahan@cs.jhu.edu (Paul Callahan) writes: >Is there a closed form solution for the effective resistance between two >points on an infinite 2-D mesh whose edges are unit resistors? Both this problem and the related problems that you are interested in boil down to the following: Given an infinite mesh with unit resistors at the edges and a 1 amp current sink at the origin, what is the voltage at each point (assuming the voltage at the origin is 0)? Let v(i,j) be the voltage at (i,j). The problem boils down to finding the unique solution to the equations: v(i+1,j)+v(i-1,j)+v(i,j+1)+v(i,j-1)-4*v(i,j) = 0 for (i,j)!=(0,0), v(1,0)+v(-1,0)+v(0,1)+v(0,-1)-4*v(0,0) = 1 with the property that v(i,j)-v(i,j+1) and v(i,j)-v(i+1,j) go to 0 as you go out to infinity (i.e. the currents asymptote to 0). As Brendan McKay pointed out, the voltages for the solution are unbounded as you go to infinity. But it's a well-posed mathematical problem anyway. To find the effective resistance between two vertices, you have to find the voltages when there is a current source and a current sink at the two vertices. To do that, all you have to do is subtract the above solution from a translate of itself. The upshot is that the effective resistance from (0,0) to (i,j) is simply v(i,j)+v(-i,-j) = 2*v(i,j). Among other things, this lets us immediately conclude that the e.r. between two *adjacent* vertices is 1/2, because by symmetry v(1,0) = 1/4. There is no such trick for the general problem. Nevertheless Noam Elkies discovered independently that it has a tractable solution and he posed the problem to me as a puzzle a few years ago. Here is the solution as I remember it. We start by rotating the mesh by 45 degrees. Specifically, we let v(x,y) = v((x+y)/2,(x-y)/2) when x+y is even. Next, we attempt to guess solutions of the form v(x,y) = f(y)*exp(i*theta*x) with no current source or sinks anywhere (for the moment we'll have to drop the vanishing-at-infinity condition). From the equation v(x+1,y+1)+v(x+1,y-1)+v(x-1,y+1)+v(x-1,y-1)-4*v(x,y)=0, we get f(y+1)*2*cos(theta)-4*f(y)+f(y-1)*2*cos(theta) = 0, or f(y+1)-2*sec(theta)*f(y)+f(y-1) = 0. This is a recurrence relation very similar to that for Fibonacci numbers. In the spirit of the Fibonacci sequence, we further guess an answer of the form f(y) = r^y. We get a quadratic equation for r which miraculously factors into r=sec(theta)+tan(theta) and r=sec(theta)-tan(theta). So we get two solutions (sec(theta)+tan(theta))^y*exp(i*theta*x) and (sec(theta)-tan(theta))^y*exp(i*theta*x). Any linear combination of solutions is of course another solution. The next step is to piece together these solutions to get a set of voltages which doesn't blow up at infinity and which also has current sources. If we let 0<theta<pi/2, then we see that sec(theta)-tan(theta)<1, and sec(theta)+tan(theta) is just the reciprocal. Thus, the solution v_theta(x,y) = (sec(theta)-tan(theta))^|y|*exp(i*theta*x) has good behavior at infinity and no current sources in the upper or lower half plane. However, we can check that it has a current source of 4*sin(theta)*exp(i*theta*x) amps at the vertex (x,0) (with x even, of course). The voltage function 1-Re(v_theta(x,y)) is equally nice, actually, and it has the extra advantage of being real everywhere and equal to 0 at (0,0). It has a current sink of 4*sin(theta)*cos(theta*x) at (x,0). In the last step, we integrate 1-Re(v_theta(x,y)) to get the pattern of current sources we want. Specifically, if we let v(x,y) = integral_0^pi/2 (1-(sec(theta)-tan(theta))^|y|*cos(theta*x))/2/pi/sin(theta) dtheta, the current sinks cancel out everywhere except at the origin, and in fact v(x,y) is the solution to the original set of equations. So, for example, the e.r. between two diagonally separated vertices is simply 2*v(2,0) = 2/pi. ---- Greg Kuperberg Reply only to postings you like. greg@math.berkeley.edu Ignore postings you dislike.