Longest of random worm-like paths in $\mathbb{Z}^2$ 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.
 A: 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$.
