Shortest grid-graph paths with random diagonal shortcuts - MathOverflow

Shortest grid-graph paths with random diagonal shortcuts

2010-11-13T14:01:13Z

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 by sleepless in beantown for Shortest grid-graph paths with random diagonal shortcuts

2010-11-13T15:40:24Z

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 by R W for Shortest grid-graph paths with random diagonal shortcuts

2010-11-13T16:50:56Z

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 by Ori Gurel-Gurevich for Shortest grid-graph paths with random diagonal shortcuts

2010-11-13T18:15:38Z

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.

Answer by Tom LaGatta for Shortest grid-graph paths with random diagonal shortcuts

2010-11-13T23:06:27Z

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 by Omer for Shortest grid-graph paths with random diagonal shortcuts

2010-11-14T02:23:25Z

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

Answer by Raphaël Rossignol for Shortest grid-graph paths with random diagonal shortcuts

2010-11-25T17:54:26Z

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 ?