Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$, with coordinates $\equiv 2 \mod 3$, we place, with equal probability, one of these six patterns:


      SixTemplates
The result is collection of disjoint "worm-like" paths, whose minimum length is $3$. For example, here is an example for $n=10$:
      RandDiskPaths10
The longest path here starts at $(1,14)$, and has length $27$. My question is:

Q. What is the growth rate of the longest path, with respect to $n$?

With $10$ random trials each, the average longest path for $n=10$ is actually considerably smaller than $27$; it is in fact $18.3$. Here is a graph up to $n=50$; it appears to grow (with considerable variability) roughly proportional to $\sqrt{n}$. Is there some relatively straightforward way to see what is the expected growth rate of the longest path?


      LongestPaths


I gratefully acknowledge programming assistance from several users in response to this posting @Mathematica Stack Exchange.

share|improve this question
6  
Each partial path extends in each direction with probability at most $1/2$ per step, so the length of the path through a tile is dominated by a sum of two geometric random variables. So, the longest path is $O(\log n)$ with high probability. A lower bound of the same form follows from choosing the path ahead of time. –  Douglas Zare Jun 22 at 1:25
1  
@DouglasZare: I see the $\frac{1}{2}$ probability per step, but not its consequences. Could you expand upon your observations? Thanks! –  Joseph O'Rourke Jun 22 at 11:16

1 Answer 1

up vote 8 down vote accepted

I'll expand a bit on my comment. There are $n^2$ $3 \times 3$ tiles. From each, there are two directions you can follow the path. As you move along the path in one direction, you hit a new tile, a previously visited tile, or the edge of the region. The path only gets longer if it encounters a new tile and the tile has one of the patterns connecting it to that side, which happens with conditional probability $1/2$ since $3$ of $6$ tiles have paths connecting with any particular side. So, the number of steps you can take in each direction is dominated by a geometric random variable which has probability $1/2^n$ of being at least $n$. If there is a worm of length $L+1$ tiles, then at least one of the $n^2$ tiles has at least one direction where this geometric random variable is at least $L$. The expected count of these is $2n^2/2^L$. (Expectation is linear regardless of dependencies.) When $L=\log_2 (2n^2) = 1+2\log_2 n,$ the expected count is at most $1$. The expected number of worms of length at least $2 \log_2 n +2 + c$ is at most $1/2^c$, so the probability that there is at least one such worm has probability at most $1/2^c$. For any constant $k \gt 2$, the probability that there is a worm of length $k \log_2 n$ goes to $0$ as $n\to \infty$.

share|improve this answer
    
You make it look easy :-). Thanks for the explanation! –  Joseph O'Rourke Jun 23 at 10:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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