# Shortest grid-graph paths with random diagonal shortcuts

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. • This is a trivial comment, but the growth rate has to be linear in $n$ as it is bounded between $n\sqrt{2}$ and $2n$. – JBL Nov 13 '10 at 14:34
• Obvious but useful observation, and I have to admit I didn't see its implication. Thanks! – Joseph O'Rourke Nov 13 '10 at 15:38
• @jc: That is one of the natural questions I did not ask. What is the expected maximum departure from the diagonal? [I assume this is what you mean?] This is of course connected to the expected length. Or do you mean: What is the variance in my plot? If the latter, the answer is: Extremely small. That I could quantify. The five runs that determine the point plotted for $n=200$ fall within 303.5$\pm$1.6. – Joseph O'Rourke Nov 13 '10 at 18:40
• This seems to me to reduce to a somewhat more natural question on strictly increasing sequences. That is, given a grid with 0-1 entries chosen from your distribution, find a maximum set of 1s that is strictly increasing in both x and y coordinates. I would guess that such a thing is well understood (and can be managed with a straightforward recurrence), but I'm no expert. – Andrew D. King Nov 13 '10 at 21:27
• Andrew: a lot of work has been done on the longest increasing subsequences of permutations, and it is closely related to last-passage percolation and random matrix models. – Tom LaGatta Nov 13 '10 at 23:07

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

• Thanks for the reference to Kingman’s subadditive ergodic theorem, which I am just now studying as a result of your citation. – Joseph O'Rourke Nov 13 '10 at 17:02

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. There's a newer paper by Benaïm and Rossignol, which I haven't read. I guess that most of the results apply to this setting as well.

• Any idea what the fluctuations might be? – j.c. Nov 13 '10 at 18:17
• "There's no reason to think that ... the answer will be nice": That is a useful warning, as I failed to find a simple explanation for the observed slope. – Joseph O'Rourke Nov 13 '10 at 18:42
• jc: see the addendum. – Ori Gurel-Gurevich Nov 13 '10 at 20:36

Hi,

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 of Seppalainen:

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.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 ?

• sorry - I had geometric weights in mind. – Omer Nov 26 '10 at 1:43
• @Raphaël: Thanks for your remarks, and especially the reference to the Seppalainen paper, which seems directly relevant. Thanks again! – Joseph O'Rourke Nov 27 '10 at 0:40

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}$,

• I like the idea of writing it as a recurrence relation. Will try when time permits. Thanks! – Joseph O'Rourke Nov 13 '10 at 16:10
• The idea seems good, but you are making a mistake. The length is m+n is no diagonals are used, but each diagonal used is a change of $\sqrt{2}-2$ (makes the total smaller). You are using $\sqrt{2}-1$. Check your formula for L(1,1). – Aaron Meyerowitz Nov 14 '10 at 6:55

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.

• I should further state that in most models, there is no way to compute the constant $\mu$. Your model is simple and geometric, however, and sleepless in beantown's recursive algorithm may give an explicit formula for $\mu$. – Tom LaGatta Nov 13 '10 at 23:20
• At least some of your conjectures are testable, perhaps within the range of my computational facilities. I will enjoy exploring these as time permits. Thanks for your expert attention! – Joseph O'Rourke Nov 13 '10 at 23:25
• It's my pleasure! I always enjoy your questions, Joseph. I'd love to chat with you in person sometime. Please drop me a line if you find yourself in New York, and I'll do the same if I find myself in western Massachusetts. – Tom LaGatta Nov 13 '10 at 23:36
• I computed $d_n$ out to $n=200$ to try to confirm the 2/3's power, but (a) the variance is large, so I need to run many simulations, and (b) it looks like I'd have to extend to $n=1000$ to see the trend clearly. So don't hold your breath waiting on confirmation. – Joseph O'Rourke Nov 14 '10 at 23:14

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]

• I actually use your nice observation that only {N,E,NE} steps are employed in the computations. Another way to phrase it is that a shortest path is both x-monotone and y-monotone. I think you meant that each diagonal reduces the distance by $2−\sqrt{2}$; but your point remains. Thanks for the remarks! – Joseph O'Rourke Nov 14 '10 at 12:25
• LLP = Limited Path Percolation? – Joseph O'Rourke Nov 14 '10 at 12:25
• LPP = last passage percolation. Also, I assumed path length was in measures in steps and not Euclidean, but this does not change anything of the above. – Omer Nov 14 '10 at 18:43
• Thanks for the clarifications; I should have realized you meant steps. – Joseph O'Rourke Nov 14 '10 at 19:45
• @Omer, isn't the shortest length given by First Passage Percolation? – sleepless in beantown Nov 26 '10 at 0:34