Shortest grid-graph paths with random diagonal shortcuts

Question

Suppose you have a network of edges connecting each integer lattice point in the 2D square grid $[0,n]^2$ to each of its (at most) four neighbors, {N,S,E,W}. Within each of the $n^2$ unit cells of this grid, select one of the two diagonals at random to add to the network. These diagonals serve as local "short cuts." One could ask many questions about this model, but let me start with this one:

What is the expected length of the shortest path in such a network from $(0,0)$ to $(n,n)$?

Here is an example for $n=25$:
      
Here a shortest path has length $10+20 \sqrt{2} \approx 38.3$ in comparison to the shortest possible length, $25 \sqrt{2} \approx 35.4$. For small $n$, the growth rate of the length of the shortest path appears to be linear in $n$, with a slope of about 1.52315.
      
I would appreciate learning if anyone recognizes this model and/or knows the true growth rate. Thanks!

Edit. One more figure to address a question raised by jc. This shows 10 shortest paths for $n=50$, for different random diagonal choices (not shown). But be aware that usually several shortest paths are tied as equally long, and my code selects one with a systematic bias toward the lower right corner. But the figure provides a sense of the variation.
      

Answer 1

Good question. At least, existence of a precise rate of linear growth (not just for the expectations, but also almost everywhere - presuming that a random configuration on the whole quadrant is fixed, and then you let $n$ grow) follows from the subadditive ergodic theorem - for, by the triangle inequality the length of such a minimal path in the $(n+m)\times(n+m)$ square does not exceed the sum of lengths of minimal paths in the $n\times n$ subsquare in the lower left corner and in the $m\times m$ subsquare in the upper right corner

Answer 2

This is an interesting variation of First passage percolation (see this question). There's no reason to think that in this case the answer will be nice in any way, as percolation thresholds rarely are.

I think that the speed should be strictly larger than $\sqrt{2}$, for the following reason: if we had a path using NE diagonals almost all the time with high probability, then the graph consisting of only the long (say >100) streaks of NE diagonals should percolate. But standard percolation argument should show that this isn't the case. I hope this makes sense, I don't have time to check the details right now.

ADDENDUM: regarding fluctuations we have the paper of Benjamini, Kalai and Schramm, First Passage Percolation Has Sublinear Distance Variance. There's a newer paper by Benaïm and Rossignol, Exponential concentration for First Passage Percolation through modified Poincare inequalities, which I haven't read. I guess that most of the results apply to this setting as well.

Answer 3

I also think, as already said, that this is exactly a problem of First Passage Percolation. I precise Tom's idea: take the whole lattice $\mathbb{Z}^2$ and add S0-NE diagonals (this is in fact a triangular lattice). Then put deterministic edge-weights equal to $1$ on the horizontal and vertical edges, and put independently on each diagonal edge a weight equal to $\sqrt{2}$ with probability $1/2$ and to $2$ (or anything larger than $2$) with probability one half. I think this is exactly equivalent to your model, no ?

The edge-weights are not i.i.d, but they are independent and stationnary (and thus ergodic). Kingman's result applies to show the existence of an almost sure limit.

Concerning fluctuations, Benjamini, Kalai and Schramm's argument should apply as is (it works on any lattice), but this should not be optimal as mentioned by Tom.

For the possibility to compute the value of the limit, maybe take a look at this article:

• Timo Seppäläinen, Exact limiting shape for a simplified model of first-passage percolation on the plane, Ann. Probab. 26 (3) (1998) 1232–1250, https://doi.org/10.1214/aop/1022855751

Anyway, this is a nice model !

@ Omer: You said "LPP on $\mathbb{Z}^2$ with Bernoulli weights (for which the limit shape is known)" ... are you sure the shape is known ?

Answer 4

For an $n \times n$ grid, the probability of finding a path of length $n\sqrt{2}$ is $1/2^n = 2^{-n}$.

For a grid of size $(n,0)$ or $(0,n)$, the expected path length is $n$ with probability $p=1$. Let's call the expected path length $L(x,y)$

$$L(n,0)=L(0,n)=1 \cdot n = n$$

For a grid of size $(n,1)$ or $(1,n)$, the expected path length is $n+1$ if all possible diagonals face the incorrect way, and $n+\sqrt{2}$ if there exists at least one-diagonal facing the correct way to create a short-cut:

$$L(n,1)=L(1,n)=\binom{n}{1} \cdot \frac{1}{2^n} \cdot n + (1 - \binom{n}{1} \cdot \frac{1}{2^n}) \cdot (n+\sqrt{2} )$$

$$L(n,1)=L(1,n)= n + (1 - \binom{n}{1} \cdot \frac{1}{2^n}) \cdot \sqrt{2}$$

$$L(n,1)=L(1,n)= n + (\frac{2^n -1}{2^n}) \cdot \sqrt{2}$$

For a grid size $(n,2)$ or $(2,n)$, the expected shortest path length is $n+2$ if in all of the locations, there are no correct facing diagonals; $n+1+\sqrt{2}$ if the short-cut diagonal only occurs in the last square (top-most); or length $n+2\sqrt{2}$, if there is a short-cut diagonal in one of the first column's $n-1$ lower squares, and a short-cut diagonal in one of the second column's upper squares after the lower square.

This could probably be written as a recursive formula to see what the limit yields, as $L(0,0)=0$, $L(1,0)=L(0,1)=1$, $L(1,1)=\sqrt(2)\cdot\frac{1}{2}+2\cdot\frac{1}{2}=1+\frac{\sqrt{2}}{2}$,

Answer 5

I think this should be equivalent to a directed, site first-passage percolation (FPP) model where each site takes a passage time of $1$ or $\sqrt{2}$, each with probability $1/2$. I'm not convinced of this one (and haven't given it enough thought) but I'm pretty sure you can come up with a correspondence between some FPP model and this one.

As R W says in another answer, Kingman's subadditive ergodic theorem implies that the passage time $a_n$ between the origin and the point $(n,n)$ should be of the order $\mu n$ for some constant $\mu > 0$. As Ori Gurel-Gurevich says, the Benjamini-Kalai-Schramm estimate should apply so that the variance of the passage times is sublinear:
$$a_n = \mu n + O(n/\log n).$$

Let me now state some conjectures:

• The variance of the passage time should be $O(n^{2\chi})$, where $\chi = 1/3$.

• Let $\gamma_n$ denote the minimizing path from the origin to $(n,n)$. Let $d_n$ be the maximum Euclidean distance that $\gamma_n$ reaches away from the straight line path from the origin to $(n,n)$. Then $d_n$ should be $O(n^\xi)$, for $\xi = 2/3$.

• Similar statements should hold in arbitrary dimension, for different values of the constants $\chi$ and $\xi$. Nonetheless, the constants should always obey the Kardar-Parisi-Zhang (KPZ) equation $$\chi = 2\xi - 1.$$

There has been much work on getting some precise bounds for these constants for FPP, but we are still far from rigorously proving that $\chi = 1/3$ and $\xi = 2/3$. See the excellent survey Models of First-Passage Percolation by Howard (2004) for more on this topic.

Answer 6

Not quite what Tom suggested, but this model is a form of last passage percolation (LPP).

There is always a minimal path that makes only N,E or NE steps. To see this, suppose a minimal path moves from $(i,j)$ to $(i-1,j+1)$, and that the next visit to column $i$ is at $(i,k)$. Using instead a straight segment from $(i,j)$ to $(i,k)$ cannot increase the path length. The other cases are similar.

It follows that to find the speed (or limit shape), we need to find the maximal number of NE shortcuts that can be used in a path to $(n,m)$, as each reduces the distance by $1$ (compared to the grid distance).

This is similar to LPP (Last Passage Percolation) on $\mathbb{Z}^2$ with Bernoulli weights (for which the limit shape is known), but is not the same since only one shortcut may be used in each row or column.

[edit: I had geometric weights in mind]