The shortest path in first passage percolation - MathOverflow

The shortest path in first passage percolation

2009-12-22T20:12:54Z

Consider a square planar grid. (The vertices are pair of points in the plane with integer coordinates and two vertices are adjacent if they agree in one coordinate and differ by one in the other.)

Give every edge a length one with probability a half and length two with probability a half.

Consider a shortest path between the origin and the vertex $(n,0)$.

Show that with probability that tends to one as $n$ tends to infinity the shortest path will not contain the "middle edge" on the x-axis inbetween the orgin and $(n,0)$. (Namely, the edge between the vertices $(\lfloor\frac{n}{2}\rfloor,0)$ and $(\lfloor\frac{n}{2}\rfloor+1,0)$.)

This question is in the category of "a missing lemma". It is not really a full fledged open problem but rather a statement which looks correct that was needed in some paper and resisted proof. Of course, some such "lemmas" turn out to be very difficult, but sometimes maybe a simple argument was simply missed. The relevant paper is with Itai Benjamini and Oded Schramm: First Passage Percolation Has Sublinear Distance Variance

While MO have chosen to accept one answer, and there were some nice suggestions, the problem is still wide open.

Answer by Joseph Malkevitch for The shortest path in first passage percolation

2009-12-26T01:04:15Z

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.

Answer by Tom LaGatta for The shortest path in first passage percolation

2009-12-26T04:19:46Z

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!

Answer by Gjergji Zaimi for The shortest path in first passage percolation

2009-12-26T06:06:47Z

Talking about naive attempts, I thought maybe a simple solution along these lines could be found, but I couldn't:

I denote by $p_k(n,2r)$ the probability that a shortest path from the origin to $(n,2r)$ contains the segment $(\lfloor \frac{n}{2}\rfloor,k)$ to $(\lfloor \frac{n}{2}\rfloor +1,k)$. A simple observation is that $p_k(n,2k)=p_k(n,0)$ (consider reflecting the path on the line $y=k$ in the region $x > \lfloor \frac{n}{2}\rfloor$). The idea is to show that $p_k(n,2k)$ is close to $p_0(n,0)$ for small $k$. One can do this maybe by considering a new rectangular grid spanned by $(1,\frac{2k}{n})$ and $(-\frac{2k}{n},1)$ (with suitable edge weight distribution) and trying to find the new $p_0'(n,0)$ which should be a good approximation of $p_k(n,2k)$.

Now if one can find a slowly decreasing function $f$ so that $p_k(n,2k)\approx f(p_0(n,0))$ in the range, say $|k|\le \sqrt{n}$ then $$1=\sum_{k=-\infty}^{\infty}p_k(n,0)=\sum_{k=-\infty}^{\infty}p_k(n,2k)\approx \int_{-\sqrt{n}}^{\sqrt{n}}f(p)dp \geq c\sqrt{n}p_0(n,0)$$ for some constant $c$. If $\lim_{n\to \infty}p_0(n,0)>0$ then the above inequality is obviously false for large enough $n$.

ETA: I realize this approach works if we were able to prove $$\liminf_{n\to \infty} p_{0}(n,0)=\liminf_{n\to \infty} p_k(n,0)$$ for any fixed $k$.

Answer by Steve Huntsman for The shortest path in first passage percolation

2010-01-18T18:54:17Z

Here is a sketch of a germ of an idea that might work. But don't take it too seriously.

Consider the space $E_k$ of grid paths from $(0,0)$ to $(2k+1,0)$ with nonnegative $x_2$-coordinate and Euclidean length $2k+3$. Associate such paths with functions in the obvious way. Now there are $\binom{2k+2}{2}$ such paths, $2\binom{k+1}{2}$ (i.e., proportionally just less than one half) of which contain the middle edge. Now there exists an assignment of edge lengths and corresponding coefficients $\{a_j\}_{j=1}^k \in \{0,1\}^k$ s.t. the sum $\gamma = \sum_{j=1}^k a_j \gamma_j$ is a shortest path (provided we require a nonnegative $x_2$-coordinate).

If the $a_j$ and $\gamma_j$ are selected uniformly at random, then the probability that the middle edge will be contained in $\gamma$ is asymptotically $2^{-k/2}$.

Answer by daniel pehoushek for The shortest path in first passage percolation

2010-01-28T23:15:39Z

Midway Problem (a reformulation only)

This is not an Answer. Start with a 2n x2n grid graph. all edges length one, all even pairs linked.

The "both even" numbered vertices are "the original graph". Add (x odd, y even) vertices half the time. Add (x even, y odd) vertices the time. The (odd, odd) vertices are always out. Seems a decent starting point. Point Midway is now (n+1, 0), and in the graph half of the time.

The two questions may then be:

Strongest question, as n grows: Show with probability approaching one that the set of all shortest paths between (0,0) and (2n,0) almost never contains Midway.

Weaker question, as n grows: Show with probability approaching one that there is a shortest path
between (0,0) and (2n,0) that does not contain Midway.

They may even have different answers, unless the shortest path has "uniqueness" properties. So again, this is not an answer.

But, the fractions are gone, and the edge lengths are all one!

Apologies for the initial typo. Is this variation more accessible?
The Far Corner variant of Midway, with an exclusion somewhere, may be easier for purists; but again, I do not know the answer (Nor even close). Propertys of shortest path sets from (0,0) to (2n,2n) may shed light on the axial case. Some small variety of forbidden minor, behaving as Midway, may be worthy of considering. I would try constant sized cycles.

Answer by Tom LaGatta for The shortest path in first passage percolation

2010-04-27T21:43:07Z

Gil, thanks for bumping this post. I think I've got a new idea for you, but it's not a proof yet. Let $\gamma_n$ be a minimizing geodesic between $(-n,0)$ and $(n,0)$, and let $\gamma^{\pm}_n$ be a minimizing geodesic betwen $(\pm n, 0)$ and the origin.

Denote by $d(\gamma_n)$ the maximal Euclidean distance from the geodesic $\gamma_n$ to the straight line path between $(-n,0)$ and $(n,0)$, and define $d(\gamma^\pm_n)$ similarly for $\gamma^\pm_n$. By the definition of the transversal fluctuation exponent $\xi$, $d(\gamma^\pm_n)$ scales like $n^\xi$ and $d(\gamma_n)$ scales like $(2n)^\xi$.

Since $\tfrac 1 2$ is less than the critical probability for oriented bond percolation in two dimensions $\approx .633$, a theorem of Licea-Newman-Piza applies and there is a rigorous lower bound $$\xi \ge 1/3$$ for your model. (cf. Theorem 4.3 in Howard - Models of First-Passage Percolation)

Suppose that $\gamma_n = \gamma^-_n \cup \gamma^+_n$ (i.e. the geodesic $\gamma_n$ meets the origin), so that $$2^\xi n^\xi \approx d(\gamma_n) = \max\{d(\gamma^-_n), d(\gamma^+_n)\} \approx n^\xi, $$ which suggests a contradiction since $2^\xi > 1$ by the lower bound $\xi \ge 1/3$.

Here's why it doesn't work. The exponent $\xi$ is precisely defined as the minimal power of $n$ such that the following hold: $$\lim_{n\to\infty} \mathbb P\left[d(\gamma^\pm_n) \le n^\xi \right] = 1 \qquad \mathrm{and} \qquad \lim_{n\to\infty} \mathbb P\left[d(\gamma_n) \le (2n)^\xi \right] = 1.$$ Since the $\approx$ signs above are really inequalities, there is no contradiction above.

Answer by Pascal Maillard for The shortest path in first passage percolation

2011-09-24T10:07:37Z

UPDATE: Fixed typing error in 2nd paragraph (greater than -> less than or equal to)

UPDATE2: Fixed typing errors pointed out by Gil Kalai

UPDATE3: I put off the detailed version from my webpage

UPDATE4: The solution is wrong, as pointed out to me by Nathanaël Berestycki. It is of course not enough to consider only the path that goes directly from the origin to (n,0). I didn't read the problem properly. Sorry.

I don't know whether this problem is still open, but I think I have found an elementary proof for the original question. It is almost too simple to be true, but I don't see any mistake. Here's the sketch:

All numbers here are natural numbers between $0$ and $n$, and $n$ is sufficiently large. Fix a (large) $K$. Let $x_l$ be the smallest $x < n/3$, such that for all $1\le j \le K$, the length of the path $(x,0)\rightarrow (x,j) \rightarrow (x+K,j)$ is less than or equal to the length of the path $(x,0)\rightarrow (x+K,0)$. The arrow indicates that we take the direct path. For definiteness, set $x_l = \lfloor n/3 \rfloor + 1$ if such a number does not exist, but note that it exists with probability going to one as $n\rightarrow \infty$. Note further that since we took the smallest $x$ with the above property, conditioned on $x_l$, the lengths of the edges to the right of the vertical line $x=x_l+K$ are still independent, of the same law as before, and independent of the configuration to the left of this vertical line.

Now define $x_r$ by mirroring the above definition at the line $x=n/2$ (the largest $x>2n/3$, such that ....)

Then, the paths $(x_l+K,j)\rightarrow(x_r-K,j)$ are independent for $0\le j\le K$, hence, with probability going to $K/(K+1)$, there exists $1\le j \le K$, such that the path $(x_l+K,j)\rightarrow(x_r-K,j)$ is shorter than $(x_l+K,0)\rightarrow(x_r-K,0)$.

Combining the above observations, with probability $K/(K+1) + o(1)$, there exist $x_l < n/3$, $x_r>2n/3$ and $1\le j \le K$ such that the path $(0,0) \rightarrow (x_l,0)\rightarrow (x_l,j)\rightarrow (x_r,j) \rightarrow (x_r,0) \rightarrow (n,0)$ is shorter than the path $(0,0) \rightarrow (n,0)$. Letting first $n\rightarrow \infty$, then $K\rightarrow\infty$ finishes the proof.