Nondifferentiability of the time constants of first-passage percolation. (English) Zbl 1029.82017

This paper studies the time constant in the first-passage percolation (FPP) problem on \(\mathbb{Z}^2\), introduced in 1965 by Hammersley and Welsh, and answer negatively to an open conjecture of this field. The model studied here on \(\mathbb{Z}^2\) is this of the general FPP problem but the main result concerns the Bernoulli case.
On the lattice \(\mathbb{Z}^2\), one considers a random field \(x=(x(e))_{e \in\mathbb{Z}^2}\) of i.i.d. random variables, with a marginal distribution \(F\) of finite mean. When \(e=(u,v)\), this random variable \(x(e)\) can be viewed as the amount of time needed to go from \(u\) to \(v\). In the simplest Bernoulli case, this amount is either \(0\) or \(1\) with probability \(p\) and \(1-p\). To study the stream along the lattice, one also considers paths along edges \(\gamma = \{v_0,e_1,v_1,\dots,e_n,v_n\}\) and defines the passage time of \(\gamma\) to be \(\tau(\gamma)=\sum_{e \in \gamma} x(e)\).
Hammersley and Welsh had first studied the first passage time (FPT) \(a_{0,n}\) from the origin and the point \(u(n,0)\) of the horizontal axis, and proved by subbadditivity that there exists a finite constant \(\mu(F)\) such that the ratio \(a_{0,n}/n\) converges (a.s. and in \(L^1\)) to \(F\) when \(n\) goes to infinity. This so-called time constant \(\mu(F)\) has been studied intensively and is a central object of this paper. Depending on the configuration, different paths can lead to the FPT \(a_{0,n}\) (these paths are then called routes.
Another object of interest, because it provides information on the FPT, is the length \(N_n\) of the shortest route. This length behaves differently depending on the percolation regime of the model. In the supercritical case, Zhang and Zhang (1984) proved that \(N_n/n\) converges a.s. and in \(L^1\) to another finite time constant \(\lambda(F)\), but this problem is still open in other regimes. Hammersley and Welsh had already studied this question and transformed it into a problem of smoothness of the first time constant \(\mu(F \otimes t)\) of the shifted distribution \(F \otimes t\) as a function of the shift parameter \(t\) (For the Bernoulli case, the shifted Bernoulli r.v.’s \(x'(e)=x(e)+t\) take values \(t\) and \(t+1\) with probability \(p\) and \(1-p\)). This approach has later on been carried on by Smythe and Wierman (1978) and Kesten (1980) who obtained a new criterion for this convergence in the subcritical case : the ratio \(N_n/n\) must converge with probability one if the time constant \(\mu(F \otimes t)\) is differentiable at \(t=0\).
The main result of this paper closes the door of this approach : Theorem 1 proves that this differentiability condition does not hold for the basic Bernoulli percolation problem in the subcritical case (\(F(0)=p<1/2\)). According to the authors, it is likely that the convergence still holds for subcritical percolation but the proof must be more subtle : a conjecture of Kesten about the divergence in the critical case suggests that the analysis of the sub- and super critical case may be different.
The proof of the main theorem (Theorem 1) is achieved after a careful preparation relying on combinatorial, topological and geometrical techniques. The FPP \(a_{0,n}\) is first related to the length \(N_n\) of the shortest route and graph theory is used to restrict the attention on finite volume analysis of the dual lattice. The non-differentiability of the time constant is proved after some probabilistic comparaisons between the longest and the shortest route at \(t=0\). The authors also indicate in their conclusion alternative routes to prove the convergence of \(N_n /n \) in the subcritical case.


82B43 Percolation
60K35 Interacting random processes; statistical mechanics type models; percolation theory
Full Text: DOI


[1] AIGNER, M. (1995). Turán’s graph theorem. Amer. Math. Monthly 102 808-816. JSTOR: · Zbl 0843.05053
[2] BENNETT, G. (1962). Probability inequalities for sums of independent random variables. J. Amer. Statist. Assoc. 57 33-45. · Zbl 0104.11905
[3] ENGLE, E. (1997). Sperner Theory. Cambridge Univ. Press.
[4] GRIMMETT, G. and KESTEN, H. (1984). First-passage percolation, network flows, and electrical resistances. Z. Wahrsch. Verw. Gebiete 66 335-366. · Zbl 0525.60098
[5] HAMMERSLEY, J. M. and WELSH, D. J. A. (1965). First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Bernoulli, Bay se, Laplace Anniversary Volume (J. Ney man and L. Le Cam, eds.) 61-110. Springer, Berlin. · Zbl 0143.40402
[6] HOEFFING, W. (1963). Probability inqualities for sums of bounded random variables. J. Amer. Statist. Assoc. 26 13-30. JSTOR: · Zbl 0127.10602
[7] KESTEN, H. (1980). On the time constant and path length of first-passage percolation. Adv. in Appl. Probab. 12 848-863. JSTOR: · Zbl 0436.60077
[8] KESTEN, H. (1982). Percolation for Mathematicians. Birkhäuser, Boston. · Zbl 0522.60097
[9] KESTEN, H. (1986). Aspects of First Passage Percolation. Lecture Notes in Math. 1180. Springer, New York. · Zbl 0602.60098
[10] SMy THE, R. T. and WIERMAN, J. C. (1977). First passage percolation on the square lattice. I. Adv. in Appl. Probab. 9 38-54. JSTOR: · Zbl 0381.60101
[11] SMy THE, R. T. and WIERMAN, J. C. (1978). First Passage Percolation on the Square Lattice. Lecture Notes in Math. 671. Springer, New York. · Zbl 0379.60001
[12] WIERMAN, J. and REH, W. (1978). On conjectures in first-passage percolation theory. Ann. Probab. 6 388-397. · Zbl 0394.60084
[13] ZHANG, Y. and ZHANG, Y. C. (1984). A limit theorem for N0n/n in first-passage percolation. Ann. Probab. 12 1068-1076. · Zbl 0568.60098
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.