Please see PDF version
Paper: NondifferentiabilitY of the time constants of first passage percolation
Authors: J. Michael Steele and Yu Zhang
Journal: Annals of Probability
The authors prove a nice result about standard two dimensional first passage percolation where the edge weights 7 (e) are independent Bernoulli random variables with P[ r(e) = 0] = p. For t E R, let F ED t denote the distribution of the shifted Bernoullis, i.e., of 7 (e) + t, and let M(F G) t) denote the time constant when the edge weights are distributed according to F ED t. The authors' main result is that for p < 1/2 but sufficiently close to 1/2 the function 0(t) = M(F E) t) is not differentiable at t = 0.
While this result is technical, it is of interest because of its connection to another long standing problem in FPR Specifically, let N,, denote the length of the shortest minimizing path from the origin to the vertex (n, 0). While the behavior of Nn/n as n ~ oo is not well understood for subcritical p, it has long been known that Nn/n converges almost surely if p(F E) t) is differentiable at t = 0. The authors' result therefore shuts the door on this strategy of proving convergence of Nn/n at least for an important class of edge distributions.
Along the way, the authors obtain an exponential bound on the tail probability of the ratio of the lengths of the longest and shortest miminizing paths. This result and the techniques in the proof are independently interesting.
The exposition is refreshingly clear. Below 1 point out some typos and suggest a few minor changes:
Page 6. In the "To mop up" paragraph, why not simply observe that m >
N
and avoid the detailed computations? (This works for large n because of the mc > 4 condition then just increase Co to get it for all n.) In the definition of Hn (k), "y is a vertex" should be "(x, y) is a vertex". Lemma 3 is slightly misstated: 6 plays no role. In the proof of Lemma 3, why not just replace c with p(p)/2? Also, b' ', and b'
0,2 0, 2n are not defined.
Page 9. In the statement of Lemma 5, the first { does not belong. Also, r(w) should be r( V).
Page 10. In the statement of Lemma 6, "as seC should be "a set".
Page 11. In the statement of Theorem 2, 1 think it should be S(O,n,2n). The statement of Lemma 7 is missing a T(e) at the end.
Page 12. In line 14, "may be" should be "will be"; delete the subsequent unnecessary "that may be". In the second sentence of Case 1, should "three" be "exceeding two"?
Page 14. For the second possibility of Case 6, the vertex p is not labelled on the figure. Also, p is a bad choice of label given its other predominant use.
Page 15. In (17), i should be k. Also, Vn is defined by the first three conditions, not the first two. In (18) the right hand side should be vn( y)/2. In the next paragraph, "bounded" should be "stochastically bounded". In (19), shouldn't ce 2 be ao? A
0
reference should be given for the large deviation estimate. Page 16. Lemma 8 holds only for small c. Page 17. References should be given for the inequality (1'Y1) < exp(l y1H(k/l yl)) and k
for the statement that p ~ 4 p(p) is continuous with p.(1/2) = 0.
Page 18. Two display lines down from (24), F E) t should be F E) r.