Take the 2-minute tour ×

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.

share|improve this question
Thanks Alon, I myself cannot see the latex (it leaves the formulas uncompiled) so I prefer the plain text. –  Gil Kalai Dec 23 '09 at 10:34
Nitpicking: is it "a shortest path" or "the shortest path"? Do you want to show there is a shortest path avoiding the given edge, or that all shortest paths avoid the given edge. –  Boris Bukh Dec 23 '09 at 11:26
That's really a shame, Gil. Have you tried installing jsMath along with the fonts? It's not supposed to be necessary but perhaps it'll help. –  Alon Amit Dec 23 '09 at 18:00
Boris, I suppose I just want to show that there is a shortest path avoiding this middle edge. Alon, jsMath? where –  Gil Kalai Dec 23 '09 at 18:50
Boris: That's not nitpicky, it's actually an important point. If the distribution of passage times is continuous, then with probability one, there is a unique minimizing path between any two points. Here, since the distribution has atoms, with positive probability, there are multiple shortest paths. –  Tom LaGatta Dec 26 '09 at 2:02
show 1 more comment

7 Answers

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.

share|improve this answer
To whomever gave this post a negative vote: Shame on you. This post does not answer the question Gil asked, but so what? It is exploratory and raises some interesting ideas; perhaps one of those could lead to a correct answer. Posts like this are exactly what MathOverflow needs. –  Tom LaGatta Dec 26 '09 at 1:57
Joe, it is a very good idea to consider paths from (0,0) to (n,n) and to consider also the case where you only go north and east. This restricted model is called "directed percolation". As far as I know the lemma is not known for directed percolation. There is one version where the distribution of edge length is exponential and you want the path of MAXIMUM length where this model is understood very well and is strongly connected to maximum eigenvalues of random symmetric matrices, largest monotone subsequences etc. –  Gil Kalai Dec 26 '09 at 19:27
It may be possible that for this version (directed percolation; exponential lengths, maximum path), the detailed understanding of the model may lead to a proof of the lemma; but I am not sure even about it. (There are hopes, but no proofs for universality: that various models will behave in some sense the same way.) Strangely, I dont know the answer for a) off-hand. Nice question. –  Gil Kalai Dec 26 '09 at 19:34
@Tom. I think you are wrong --- if someone read it and find it not helpful then it is right thing to vote down. (BTW, it was not me) –  Anton Petrunin Jan 27 '10 at 19:37
add comment

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!

share|improve this answer
Tom, Interseting suggestion. I dont remember so much what we tried. At the end we managed to go around this lemma. –  Gil Kalai Dec 26 '09 at 19:38
add comment

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.

share|improve this answer
That's very interesting. I did not know that there is a (provable) lower bound for xsi and this certainly looks very relevant. (In fact stronger than my question...) –  Gil Kalai Apr 28 '10 at 6:08
add comment

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}$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
Dear Pascal, it is a bit too sketchy for me to follow but it looks promising! (Also I supppose the vertical line is x=x_l+K). –  Gil Kalai Sep 25 '11 at 13:26
@Gil: Thanks for having a look at the proof and pointing out the typos. I'd be glad to write down a detailed version, if the problem still interests you. –  Pascal Maillard Sep 25 '11 at 17:22
Dear Pascal, yes definitely it is an interesting problem on its own, several people tried to prove it (including us) and it has some applications regarding geodesics in the random metric described by FPP. –  Gil Kalai Sep 25 '11 at 19:51
Dear Pascal, the conjecture is from 2002 by Benjamini, Schramm and myself in the paper cited in the question itself .front.math.ucdavis.edu/0203.5262 . It is mentioned at the bottom of page 2 and the top of page 5. Actually on page 5 a slightly stronger version that we needed is mentioned and maybe your method apply there too. –  Gil Kalai Sep 26 '11 at 12:10
OK, I'll have a look at it and see if the method can be applied to the stronger statement. –  Pascal Maillard Sep 26 '11 at 12:59
show 1 more comment

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.

share|improve this answer
That's an interesting variation of the problem that might be easier. When you say add (x odd y even) hald the time do you mean with probability 1/2? I suppose also the (x even y odd) vertices are also added half the time. that's interesting. –  Gil Kalai Jan 31 '10 at 16:52
add comment

Your Answer


