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$:
Shortest path between corners http://cs.smith.edu/%7Eorourke/MathOverflow/RandShortCuts25.jpg
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.
Length vs. n http://cs.smith.edu/%7Eorourke/MathOverflow/RandShortCutsPlot.jpg
I would appreciate learning if anyone recognizes
this model and/or knows the true growth rate. Thanks!