Take the 2-minute tour ×

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.

share|improve this question
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. –  Gabriel Benamy May 5 '10 at 14:40
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? –  David Speyer May 5 '10 at 15:57
Thanks, but I don't think that's the error. I am using the formula $\sum c_k 4^{-k}$ as in Yvan's post, and claiming that $c_k \leq 4 \cdot 3^{k-1}$. Think about the one dimensional case. The expected number of steps before backtracking is the sum, over $k$, of the probability that you get to take the $k$-th step, namely $1/2^{k-1}$. It is not $\sum k/2^{k-1}$. –  David Speyer May 5 '10 at 16:04
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 –  David Speyer May 5 '10 at 16:11
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. –  James Propp May 6 '10 at 3:43

2 Answers 2

up vote 7 down vote accepted

[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 $$

share|improve this answer
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 –  j.c. May 5 '10 at 15:47
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. –  Roland Bacher May 5 '10 at 17:27
Another probably useful site: oldweb.cecm.sfu.ca/projects/ISC/ISCmain.html . Checking with the known digits of the above number (4.586079, if I haven't made a mistake), one sees that there does not seems to be a "simple" expression yielding this number (and staying between the above bounds). This strengthen somewhat the claim that an explicit formula should not be expected... –  Yvan Velenik May 6 '10 at 13:01

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.

share|improve this answer

Your Answer


