The shortest path in first passage percolation

Gil: This is a type of problem that I know little about so here I am thinking out loud about problems that seem natural to ask about this situation. It is hard to believe that people have not already thought about these questions and perhaps answered them. Where would I look to find out more?

You write you are interested in a "square planar grid." So I took this to mean that you were thinking about the points of a "square grid graph" with lx1 squares as the cells that goes from (0,0) to (n,n) and where weights were going to be assigned to the edges of size 1 or 2.

The paths that you are talking about need not be constrained to move up and to the right but it might be interesting to contrast the behavior of general shortest paths with those that move up and to the right. It would also seem to be of interest to see what happens if one selects half of the edges at random and makes them all length 1 edges and makes all the others of length 2. Since there are 4n edges this means 2n are 1's and 2n are 2's. Furthermore, If we insist that paths move up and to the right, such paths all have length 2n, so "very shortest" paths would consist only on 1's.

In both settings:

a. What is the probability there is a shortest path to (n,n) consisting of all 1's?

b. What can be said about the expected value of the length of a shortest path to (n, n)? What can be said about the expected number of paths of this value?

c. When one insists that each of the two lengths appear equally often how many different ways can this happen? (One can also ask how many of these are different up to symmetry of the "colored" graph, treating the lengths as two colors.) One could count in the general case too but the up and to the right case seems more interesting here.

Gil, as you said, this is one of those typical FPP problems which seems obvious but is hard to prove. What have you tried already? It'd be helpful to know of some naïve attempts which didn't work.

Here are my thoughts:

Claim: There exists non-random $\lambda$ such that, with probability one, for large n, all shortest paths between $0$ and $(n,0)$ meet $\lambda n + o(n)$ edges. (this is a LLN-type theorem so it shouldn't be hard to prove; e.g., via energy-entropy methods, since your passage time distributions are bounded)

Thus one can consider the probability space $\Omega_n$ consisting of all paths between $0$ and $(n,0)$ which meet $\lambda n + o(n)$ edges. A shortest path is a random variable $X_n$ on this space with a certain probability distribution.

Claim: There exists $\sigma$ such that $|\Omega_n| \approx \sigma^n$. (should be easy: $\log|\Omega_n|$ is probably subadditive)

Let $\Omega_n'$ be the subspace of paths which meet the middle edge, so that $|\Omega_n'| \approx \sigma^{n/2} + \sigma^{n/2}$.

Suppose that there exists $p > 0$ such that the shortest path between $0$ and $(n,0)$ meets the middle edge with probability at least $p$. (*)

Here is the part which I'm struggling to quantify. Intuitively, the distribution of $X_n$ should be smeared smoothly over $\Omega_n$. Certainly the mean is a horizontal line segment, but even paths which veer quite far away aren't unreasonable. However, if (*) holds, with probability at least $p$, $X_n$ concentrates on the much smaller subspace $\Omega_n'$. This seems wrong.

Perhaps all I've done is to translate one "obvious" statement into another. Hopefully this helps a bit. Good luck!

It seems that this problem was recently solved by Ahlberg and Hoffman. https://arxiv.org/abs/1609.02447