I have a random walk on $\mathbb{Z}^2$ that takes a step with equal probability in the three directions that avoid retracing the previous step. The walk proceeds until it returns to a lattice point previously visited, at which time it pinches off a simple, closed loop or polygon:
Random Walk
I'd like to know the distribution of the perimeters of these polygons. (In the example above, the perimeter is 10.) Simulations show that the average perimeter is about 5.6, with perimeter 4 the overwhelming favorite, as one would expect:
Perimeter Plot
I feel this distribution must be known to the experts and not difficult to explicitly detail, but after looking at hitting times, first-passage times, self-avoidance times, and various other frequently studied random walk quanities, I am not finding a close-enough analog to help. Thanks for any pointers you might provide!

Addendum. Here is log-plot of the probability of a perimeter of length $L$, based on a simulation of $10^6$ walks. The first point represents 642,225 perimeters for $L=4$, the second point 176,043 perimeters for $L=6$, etc. The last point plotted is 135 instances of $L=38$. (There is one polygon of length $L=74$ in these million trials.) The average perimeter length is 5.62, which occurs after an average of 8.46 steps.

  • $\begingroup$ I think it is easy to derive the exact answer. $\endgroup$ – Anixx Jan 17 '11 at 13:14
  • $\begingroup$ Does this paper help: jmp.aip.org/resource/1/jmapaq/v6/i2/p167_s1 $\endgroup$ – Suvrit Jan 17 '11 at 13:21
  • $\begingroup$ @Suvrit: Thanks for the reference. Perhaps its techniques can be mimicked for my situation. I will study it. Thanks! $\endgroup$ – Joseph O'Rourke Jan 17 '11 at 13:26
  • 3
    $\begingroup$ @Anixx: I fear you are wrong. Have you tried to derive the exact answer? $\endgroup$ – TonyK Jan 18 '11 at 18:02
  • 1
    $\begingroup$ Joseph, here is a comment which won't answer your question but might be a nice lead for you to follow. As you mentioned below, you're not very familiar with LERW. The paper that Igor Rivin posted is from '97, which predates the development of Schramm-Loewner Evolution (SLE) by two years or so. SLE is a very modern theory which has been used to solve in a closed form many questions raised about lattice probability models. For example, Lawler, Schramm and Werner were able to prove Mandelbrot's conjecture that the dimension of the boundary of Brownian motion is 4/3. $\endgroup$ – Tom LaGatta Jan 18 '11 at 20:04

I believe the paper below is on this exact question:


  • $\begingroup$ Ah, "loop-erased random walk" (LERW) may be the key phrase I was missing. Thanks, Igor, I will read this paper. $\endgroup$ – Joseph O'Rourke Jan 17 '11 at 19:36
  • $\begingroup$ Their model is just slightly different, in that they allow step reversal, and so "polygons" of perimeter 2. But I can adjust for that. The probability of generating a loop of perimeter $L$ (in their model) varies as $L^{-13/5}$. Thanks, Igor! $\endgroup$ – Joseph O'Rourke Jan 17 '11 at 20:10
  • 1
    $\begingroup$ There is now way that the probability of a loop of size $L$ varies as a power of $L$. It's much smaller. The events that you make a square between times $4(n-1)$ and $4n$ are independent and each have probability 1/32 (1 * 1/2 * 1/4 * 1/4 - any direction; any perp direction; the right direction; the right direction). Accordingly the probability of still being going after $4N$ steps is less than (actually much less than) $(31/32)^{4N}$ $\endgroup$ – Anthony Quas Jan 17 '11 at 20:17
  • 2
    $\begingroup$ There are so many differences between the model in Dhar and Dhar's paper and the model Joseph is interested in that it seems dangerous (to me) to draw some conclusions about one of them from the behaviour of the other. D&D define $P(\ell, N, L)$ as the probability, starting from a LERW of length $N$ on the torus of size $L^2$, that one step of an ordinary random walk, grafted on the endpoint of the LERW, closes a loop of length $\ell$. D&D then consider the limit $P(\ell)$ when the size of the torus $L\to\infty$ of the limit when the number of steps of the LERW $N\to\infty$ of $P(\ell,N,L)$. $\endgroup$ – Did Jan 18 '11 at 8:00
  • 1
    $\begingroup$ Re the tail of the size $\ell$ of the first completed loop, $1/32$ in Anthony's argument should read $2/27$ because immediate bactracking is forbidden. Let $\tau$ denote the time of first completion of an elementary square. Then $\tau\le\ell$ and Anthony's modified argument yields $P(\tau\ge n)\le a^{n+o(n)}$ with $a=(25/27)^{1/4}=0.981$. One can refine this by considering the most complete portion of an elementary square achieved at time $n$. This is a Markov chain on the states "Nothing" (used at time $0$ only), "One edge", "Two edges", "Three edges" and "Four edges". (to be cont'd) $\endgroup$ – Did Jan 18 '11 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.