Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation
Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 4, p. 1093-1131

We consider the standard first passage percolation model in ℤd for d≥2. We are interested in two quantities, the maximal flow τ between the lower half and the upper half of the box, and the maximal flow ϕ between the top and the bottom of the box. A standard subadditive argument yields the law of large numbers for τ in rational directions. Kesten and Zhang have proved the law of large numbers for τ and ϕ when the sides of the box are parallel to the coordinate hyperplanes: the two variables grow linearly with the surface s of the basis of the box, with the same deterministic speed. We study the probabilities that the rescaled variables τ/s and ϕ/s are abnormally small. For τ, the box can have any orientation, whereas for ϕ, we require either that the box is sufficiently flat, or that its sides are parallel to the coordinate hyperplanes. We show that these probabilities decay exponentially fast with s, when s grows to infinity. Moreover, we prove an associated large deviation principle of speed s for τ/s and ϕ/s, and we improve the conditions required to obtain the law of large numbers for these variables.

Nous considérons le modèle standard de percolation de premier passage dans ℤd pour d≥2. Nous nous intéressons à deux quantités, le flux maximal τ entre la moitié inférieure et la moitié supérieure d'une boîte, et le flux maximal ϕ entre le sommet et la base de la boîte. Un argument sous-additif standard implique une loi des grands nombres pour τ dans les directions rationnelles. Kesten et Zhang ont prouvé que τ et ϕ suivent une loi des grands nombres quand les faces de la boîte sont parallèles aux hyperplans des coordonnées: les deux variables grandissent linéairement en la surface s de la base de la boîte, avec la même vitesse déterministe. Nous étudions les probabilités que les variables renormalisées τ/s et ϕ/s soient anormalement petites. Pour τ, la boîte peut avoir n'importe quelle orientation, tandis que pour ϕ, nous imposons soit que la boîte soit suffisamment plate, soit que ses faces soient parallèles aux hyperplans des coordonnées. Nous montrons que ces probabilités décroissent exponentiellement vite avec s, quand s tend vers l'infini. De plus, nous prouvons les principes de grandes déviations de vitesse s associés pour τ/s et ϕ/s, et nous améliorons les conditions requises pour obtenir la loi des grands nombres pour ces variables.

DOI : https://doi.org/10.1214/09-AIHP346
Classification:  60K35,  60F10
Keywords: first passage percolation, maximal flow, large deviation principle, concentration inequality, law of large numbers
     author = {Rossignol, Rapha\"el and Th\'eret, Marie},
     title = {Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {46},
     number = {4},
     year = {2010},
     pages = {1093-1131},
     doi = {10.1214/09-AIHP346},
     zbl = {1221.60144},
     mrnumber = {2744888},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2010__46_4_1093_0}
Rossignol, Raphaël; Théret, Marie. Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation. Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 4, pp. 1093-1131. doi : 10.1214/09-AIHP346. http://www.numdam.org/item/AIHPB_2010__46_4_1093_0/

[1] M. A. Ackoglu and U. Krengel. Ergodic theorems for superadditive processes. Journal für die Reine und Angewandte Mathematik 323 (1981) 53-67. | MR 611442 | Zbl 0453.60039

[2] I. Benjamini, G. Kalai and O. Schramm. First passage percolation has sublinear distance variance. Ann. Probab. 31 (2003) 1970-1978. | MR 2016607 | Zbl 1087.60070

[3] D. Boivin. Ergodic theorems for surfaces with minimal random weights. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998) 567-599. | Numdam | MR 1641662 | Zbl 0910.60078

[4] B. Bollobás. Modern Graph Theory. Springer, New York, 1998. | MR 1633290 | Zbl 0902.05016

[5] S. Boucheron, G. Lugosi and P. Massart. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003) 1583-1614. | MR 1989444 | Zbl 1051.60020

[6] R. Cerf. The Wulff crystal in Ising and percolation models. In École d'Été de Probabilités de Saint Flour. Lecture Notes in Math. 1878. Springer, Berlin, 2006. | MR 2241754 | Zbl 1103.82010

[7] J. T. Chayes and L. Chayes. Bulk transport properties and exponent inequalities for random resistor and flow networks. Comm. Math. Phys. 105 (1986) 133-152. | MR 847132 | Zbl 0617.60099

[8] A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications, 2nd edition. Applications of Mathematics (New York) 38. Springer, New York, 1998. | MR 1619036 | Zbl 0896.60013

[9] G. Grimmett. Percolation, 2nd edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin, 1999. | MR 1707339

[10] A. Gut. On complete convergence in the law of large numbers for subsequences. Ann. Probab. 13 (1985) 1286-1291. | MR 806225 | Zbl 0582.60057

[11] A. Gut. Complete convergence for arrays. Period. Math. Hungar. 25 (1992) 51-75. | MR 1200841 | Zbl 0760.60029

[12] G. H. Hardy, J. E. Littlewood and G. Pólya. Inequalities, 2nd edition. Cambridge Univ. Press, 1952. | JFM 60.0169.01 | MR 46395 | Zbl 0010.10703

[13] H. Kesten. Aspects of first passage percolation. In École d'Été de Probabilités de Saint Flour XIV, Lecture Notes in Math. 1180. Springer, New York, 1984. | MR 876084 | Zbl 0602.60098

[14] H. Kesten. Surfaces with minimal random weights and maximal flows: A higher dimensional version of first-passage percolation. Illinois J. Math. 31 (1987) 99-166. | MR 869483 | Zbl 0591.60096

[15] U. Krengel and R. Pyke. Uniform pointwise ergodic theorems for classes of averaging sets and multiparameter subadditive processes. Stochastic Process. Appl. 26 (1987) 289-296. | MR 923110 | Zbl 0642.60020

[16] R. T. Smythe. Multiparameter subadditive processes. Ann. Probab. 4 (1976) 772-782. | MR 423495 | Zbl 0339.60022

[17] M. Théret. Upper large deviations for the maximal flow in first-passage percolation. Stochastic Process. Appl. 117 (2007) 1208-1233. | MR 2343936 | Zbl 1121.60102

[18] M. Théret. On the small maximal flows in first passage percolation. Ann. Fac. Sci. Toulouse 17 (2008) 207-219. | Numdam | MR 2464099 | Zbl 1152.60076

[19] M. Théret. Upper large deviations for maximal flows through a tilted cylinder. Preprint, 2009. Available at arxiv.org/abs/0907.0614.

[20] M. Wouts. Surface tension in the dilute Ising model. The Wulff construction. Comm. Math. Phys. 289 (2009) 157-204. | MR 2504848 | Zbl 1168.82007

[21] Y. Zhang. Critical behavior for maximal flows on the cubic lattice. J. Statist. Phys. 98 (2000) 799-811. | MR 1749233 | Zbl 0991.82019

[22] Y. Zhang. Limit theorems for maximum flows on a lattice. Preprint, 2007. Available at arxiv.org/abs/0710.4589.