Summary
We show that the first-passage times of first-passage percolation on ℤ2 are such that P(θ 0n<n(μ−ɛ)) and P(θ 0n>n(μ+ɛ)) decay geometrically as n→∞, where θ may represent any of the four usual first-passage-time processes. The former estimate requires no moment condition on the time coordinates, but there exists a geometrically-decaying estimate for the latter quantity if and only if the time coordinate distribution has finite moment generating function near the origin. Here, μ is the time constant and ɛ>0. We study the line-to-line first-passage times and describe applications to the maximum network flow through a randomly-capacitated subsection of ℤ2, and to the asymptotic behaviour of the electrical resistance of a subsection of ℤ2 when the edges of the subsection are wires in an electrical network with random resistances. In the latter case we show, for example, that if each edge-resistance equals 1 or ∞ ohms with probabilities p and 1−p respectively, then the effective resistance R n across opposite faces of an n by n box satisfies the following:
-
(a)
if p<1/2 then P(R n=∞)→1 as n→∞,
-
(b)
if p>1/2 then there exists ν(p)<∞ such that
$$P(p^{ - 1} \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \leqslant } \mathop {\lim \inf R_n }\limits_{n \to \infty } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \leqslant } \mathop {\lim \sup R_n }\limits_{n \to \infty } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \leqslant } v(p)) = 1$$.
There are some corresponding results for certain other two-dimensional lattices, and for higher dimensions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bollobás, B.: Graph theory, an introductory course. Berlin-Heidelberg-New York: Springer 1979
Cox, J.T., Durrett, R.: Some limit theorems for percolation processes with necessary and sufficient conditions. Ann. Probability 9, 583–603 (1981)
Cox, J.T., Kesten, H.: On the continuity of the time constant of first-passage percolation. J. App. Probab. 18, 809–819 (1981)
Doyle, P., Snell, J.L.: Random walk and electric networks. Preprint Dartmouth College (1982)
Gnedenko, B.V., Kolmogorov, A.N.: Limit distribution for sums of independent random variables. Reading, Mass.: Addison-Wesley 1954
Golden, K., Papanicolaou, G.: Bounds for effective parameters of heterogeneous media by analytic continuation. Comm. Math. Phys. 90, 473–491 (1983)
Grimmett, G.R.: Critical sponge dimensions in percolation theory. Adv. Appl. Probab. 13, 314–324 (1981)
Grimmett, G.R., Welsh, D.J.A.: Flow in networks with random capacities. Stochastics 7, 205–229 (1982)
Hammersley, J.M., Welsh, D.J.A.: First-passage percolation, subadditive processes, stochastic networks and generalized renewal theory, in Bernoulli-Bayes-Laplace Anniversary Volume, ed. J. Neyman and L. LeCam, 61–110. Berlin-Heidelberg-New York: Springer 1965
Kesten, H.: On the time constant and path length of first-passage percolation. Adv. Appl. Probability 12, 848–863 (1980a)
Kesten, H.: The critical probability of bond percolation on the square lattice equals 1/2. Comm. Math. Phys. 74, 41–59 (1980b)
Kesten, H.: Percolation theory for mathematicians. Boston: Birkhäuser 1982
Kingman, J.F.C.: Subadditive processes, Ecole d'été de probabilités de Saint-Flour V. Lecture Notes in Mathematics No. 539, 167–223. Berlin-Heidelberg-New York: Springer 1976
Kirkpatrick, S.: Models of disordered materials, Course 5 in La matière mal condensée/Ill condensed matter. Les Houches Session XXXI, eds. R. Balian et al. Amsterdam: North Holland 1978
Künnemann, R.: The diffusion limit for reversible jump processes on ℤd with ergodic random bond conductivities. Comm. Math. Phys. 90, 27–68 (1983) and Effective conductivity an a lattice as a limit of box conductivities, preprint
Papanicolaou, G.C., Varadhan, S.R.S.: Boundary value problems with rapidly oscillating random coefficients, in Random fields. Coll. Math. Soc. János Bolyai 27, Esztergom (Hungary), 835–873. Amsterdam: North Holland 1979
Smythe, R.T., Wierman, J.: First-passage percolation on the square lattice. Lecture Notes in Mathematics No. 671. Berlin-Heidelberg-New York: Springer 1978
Stauffer, D.: Scaling theory of percolation clusters, Phys. Reports 54, 1, 1–79 (1979)
Straley, J.P.: Critical exponents for the conductivity of random resistor lattices. Phys. Rev. B15, 5733–5737 (1977)
Author information
Authors and Affiliations
Additional information
Work done partly while visiting Cornell University
Rights and permissions
About this article
Cite this article
Grimmett, G., Kesten, H. First-passage percolation, network flows and electrical resistances. Z. Wahrscheinlichkeitstheorie verw Gebiete 66, 335–366 (1984). https://doi.org/10.1007/BF00533701
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF00533701