From: David Bernier <bernier@my-deja.com>
Subject: Re: moles tunneling in an n-dimensional grid
Date: Wed, 19 Jan 2000 13:41:46 GMT
Newsgroups: sci.math
Summary: [missing]

In article <861l2g$p2$1@mail.pl.unisys.com>,
  "Clive Tooth" <clive@pisquaredoversix.force9.co.uk> wrote:
[...]
> >Let's say we have a mole going from point to point on the
> >ZxZ grid.  Suppose P(t) is the position of the mole at discrete
> >time t=>0.  We suppose the mole starts at the origin, so
> >P(0)=(0,0).
> >
> >Suppose the mole is at (m,n) at time t (i.e. P(t)=(m,n)).
> >Let's represent the mole at (m,n) by a @ sign, and draw the
> >four points A,B,C,D either +/-1 up or +/-1 down from (m,n):
> >
> >           A
> >           |
> >           |
> >     B---- @---- C
> >           |
> >           |
> >           D
> >
> >The basic rule is that the mole never visits the same grid point
> >more than once.  Among A,B,C,D  the mole may have 0 to 4 non-visited
> >points.  If it has zero unvisited points, then it stays where it
> >it is (at (m,n) )forever after.  If there are 4=>k>0 unvisited adjacent
> >unvisited points, then it moves to one of the k points at random
> >in the obvious way: each of the k points has a probability of 1/k
> >of being the position at time=t+1.

I now realize that these are known as "self-avoiding random walks".
[...]

> The re-visiting problem is discussed at, for instance:
> http://mathworld.wolfram.com/PolyasRandomWalkConstants.html

Following this link, I was led to the page:
http://mathworld.wolfram.com/Self-AvoidingRandomWalk.html

which gives bounds on what is defined there as the "connectivity
constant" \mu_{d} in dimension d.  Bounds are given for small values
of d.  In all cases studied, \mu_{d} < 2*d.  This might help with
the problem of the average number of steps before the mole gets
stuck, though the fact that the mole has from 1 to 2*d choices
of direction to take at each step [before it stops] may complicate
things.

David Bernier


Sent via Deja.com http://www.deja.com/
Before you buy.
==============================================================================

From: israel@math.ubc.ca (Robert Israel)
Subject: Re: moles tunneling in an n-dimensional grid
Date: 18 Jan 2000 21:53:40 GMT
Newsgroups: sci.math

In article <8617ce$nfj$1@nnrp1.deja.com>,
 David Bernier <bernier@my-deja.com> writes:

> In the 2-D case, it's clear that the mole has a positive probability
> of eventually getting stuck with all 4 adjacent vertices already
> visited.  So one question is whether the probability of getting
> stuck might be one;  I don't know.  Another is the average number
> of visited points and the probability distribution of n=>1
> points visited supposing the mole lives forever.  Generalizing
> to an n-D grid with n=>3 can be done following the same ideas
> about mole behavior.

It's easy to show that for any d > 1 the probability of eventually 
getting stuck is 1.  There is a possible path which starts at 0, 
stays in the half-space {x: x_1 >= 0}, visits all the neighbours 
of [1,0,...,0] and then goes to [1,0,...,0] itself where it is trapped.
The probability that this will be the path taken is bounded below by
some positive number epsilon.  Thus if F(n) is the first point on the
cubical surface {x: max |x_i| = n} that the mole reaches, 
the mole has probability at least epsilon of getting trapped at the
grid point one unit away from F(n) in the direction of the outward
normal to the cubical surface at F(n).  These events are all disjoint,
so their probabilities must go to 0 as n -> infinity.  Therefore the 
probability that F(n) exists, i.e. that the mole reaches {x: max |x_i| = n},
must go to 0 as n -> infinity.  Thus with probability 1 the path is bounded,
i.e. the mole is eventually stuck.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2