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

replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:56

1
2
3

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:

![SixTemplates][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](httphttps://mathematica.stackexchange.com/q/51247/194).}

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:

![SixTemplates][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

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:

![SixTemplates][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](https://mathematica.stackexchange.com/q/51247/194).}

Replaced \mod with \bmod.

Source Link

edited Jan 21, 2015 at 1:55

Joseph O'Rourke

150.8k
36
358
958

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

![SixTemplates][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

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][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

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:

![SixTemplates][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

Removed extra horiz rule.

Source Link

edited Jun 22, 2014 at 11:15

Joseph O'Rourke

150.8k
36
358
958

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][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

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][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

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][2]

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

![RandDiskPaths10][1]

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][3]

_{I gratefully acknowledge programming assistance from several users in response to
[this posting @Mathematica Stack Exchange](http://mathematica.stackexchange.com/q/51247/194).}

Source Link

asked Jun 22, 2014 at 0:05

Joseph O'Rourke

150.8k
36
358
958

Loading

Stack Exchange Network

Return to Question