13
$\begingroup$

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.
LogPlot

$\endgroup$
6
  • $\begingroup$ I think it is easy to derive the exact answer. $\endgroup$
    – Anixx
    Jan 17, 2011 at 13:14
  • $\begingroup$ Does this paper help: jmp.aip.org/resource/1/jmapaq/v6/i2/p167_s1 $\endgroup$
    – Suvrit
    Jan 17, 2011 at 13:21
  • $\begingroup$ @Suvrit: Thanks for the reference. Perhaps its techniques can be mimicked for my situation. I will study it. Thanks! $\endgroup$ Jan 17, 2011 at 13:26
  • 3
    $\begingroup$ @Anixx: I fear you are wrong. Have you tried to derive the exact answer? $\endgroup$
    – TonyK
    Jan 18, 2011 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$ Jan 18, 2011 at 20:04

1 Answer 1

3
$\begingroup$

I believe the paper below is on this exact question:

http://pre.aps.org/abstract/PRE/v55/i3/pR2093_1

$\endgroup$
13
  • $\begingroup$ Ah, "loop-erased random walk" (LERW) may be the key phrase I was missing. Thanks, Igor, I will read this paper. $\endgroup$ Jan 17, 2011 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$ Jan 17, 2011 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$ Jan 17, 2011 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, 2011 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, 2011 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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