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.
Best Answer
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