Longest of random worm-like paths in $\mathbb{Z}^2$

Question

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

---

     

---

The result is collection of disjoint "worm-like" paths, whose minimum length is $3$. For example, here is an example for $n=10$:

---

     

---

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?

---

     

---

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

Answer 1

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