Xref: utzoo sci.physics:16970 sci.math:15353 sci.electronics:18003
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!cec2!news
From: delliott@cec2.wustl.edu (Dave Elliott)
Newsgroups: sci.physics,sci.math,sci.electronics
Subject: Re: Effective Resistance on an Infinite Mesh (Random Walk Question)
Message-ID: <1991Feb24.021311.14176@cec1.wustl.edu>
Date: 24 Feb 91 02:13:11 GMT
References: <callahan.667353668@newton.cs.jhu.edu>
Organization: Washington University, St. Louis MO
Lines: 56

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


Brought to you by Super Global Mega Corp .com