15
$\begingroup$

How many steps on average does a simple random walk in the plane take before it visits a vertex it's visited before?

If an exact formula does not exist (as seems likely), then I'm interested in good approximations.

I'd also like to know the standard nomenclature associated with the question, if any exists.

Improve this question
$\endgroup$
10
  • $\begingroup$ I'm unfamiliar with this subject, but a quick wiki on random walks gave me enough to write a simple program. Assuming that the walk can simply go back on itself (which would cause it to intersect itself), and that, say, {0,0}, {0,1}, {0,0} would constitute 2 steps, then assuming a normal distribution for the number of steps, there is about a 95% chance that the average number of steps is between 4.5652 and 4.59948, using a sample size of 100,000 random walks. Sorry it's not an analytic approach, though; I have a class in a few minutes and I didn't want to miss it working on this neat problem. $\endgroup$
    – Gabriel Benamy
    Commented May 5, 2010 at 14:40
  • 1
    $\begingroup$ I am missing something dumb here. It seems to me the number of self-avoiding walks of length $k$ is $\leq 4 \cdot 3^{k-1}$, since we must never backtrack. But this gives me an upper bound of $1+(3/4) +(3/4)^2 + \cdots = 4$. This is contrary to the numerical value of about 4.59 that Gabriel and Yvan are getting. What's going on? $\endgroup$
    – David E Speyer
    Commented May 5, 2010 at 15:57
  • 1
    $\begingroup$ Ah ha! I just tried adding up the numbers for Yvan's link and I get 3.58608. It looks like we are just off by 1, so this is probably a question of whether the length of a walk is the number of vertices visited, or the number of edges traversed $\endgroup$
    – David E Speyer
    Commented May 5, 2010 at 16:11
  • 1
    $\begingroup$ I think I sowed the seeds for this off-by-one error in my original post, since "self-avoidance time" suggests the smaller number while "how many steps ... before it visits a vertex it's visited before?" suggests the larger number. $\endgroup$
    – James Propp
    Commented May 6, 2010 at 3:43
  • 1
    $\begingroup$ Could you give more detail on how you got this value? $\endgroup$
    – JRN
    Commented Dec 19, 2014 at 1:55

2 Answers 2

Reset to default
12
$\begingroup$

[I've corrected a stupid mistake below and added an upper bound... Please check the numerical values!]

Well, I doubt that an explicit expression exists. However, it should be possible to get good bounds. The lower bound is easy: observe that $$ E(T) = \sum_{k\geq 1} P(T> k-1) = 1+\sum_{k\geq 1} c_k 4^{-k}, $$ where $c_k$ is the number of self-avoiding paths of length $k$ (and, of course, $4^k$ is the number of all paths of length $k$), so that we get a lower bound by truncating this series. Using the (known) values for $c_k$, $k=1,\ldots,71$, we get $$ E(T) > 4.58607909 $$ Now, you can get an upper bound by bounding the neglected part of the series using $c_k\leq 4 \cdot 3^{k-1}$. This gives you a very narrow interval containing the right value: if I have made no mistake ;) , we get $$ 4.58607909 < E(T) < 4.58607911 $$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Because it took me a few minutes to find on google, let me post a link to the $c_k$ up to 71, ms.unimelb.edu.au/~iwan/saw/SAW_ser.html by Iwan Jensen $\endgroup$
    – j.c.
    Commented May 5, 2010 at 15:47
  • 4
    $\begingroup$ The easiest method for finding this sort of information is The On-Line Encyclopedia of Integer Sequences! maintained by Sloane. The above sequence corresponds to A1411 (see research.att.com/~njas/sequences/…). The OEIS contains the first 27 terms and a link to Jensen's page. $\endgroup$
    – Roland Bacher
    Commented May 5, 2010 at 17:27
1
$\begingroup$

An earlier version of this answer was ridiculous; in comments, David Speyer did what I was trying to do, and I've adjusted this accordingly.

An easy upper bound: the expected number of steps until you visit the position you just left is $1 + \sum_{n \geq 0} \left(\frac{3}{4}\right)^n = 5$. I think a modestly more sophisticated approach (e.g., keep track of the last few steps so that we know if we're going around four sides of a square, for example) can improve this slightly, but I'm not sure it's worth the effort.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .