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.



self-avoidance time of random walk
[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
$$


