Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation

Raphaël Rossignol; Marie Théret

Annales de l'I.H.P. Probabilités et statistiques (2010)

  • Volume: 46, Issue: 4, page 1093-1131
  • ISSN: 0246-0203

Abstract

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

How to cite

top

Rossignol, Raphaël, and 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 46.4 (2010): 1093-1131. <http://eudml.org/doc/240905>.

@article{Rossignol2010,
abstract = {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.},
author = {Rossignol, Raphaël, Théret, Marie},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {first passage percolation; maximal flow; large deviation principle; concentration inequality; law of large numbers},
language = {eng},
number = {4},
pages = {1093-1131},
publisher = {Gauthier-Villars},
title = {Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation},
url = {http://eudml.org/doc/240905},
volume = {46},
year = {2010},
}

TY - JOUR
AU - Rossignol, Raphaël
AU - Théret, Marie
TI - Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2010
PB - Gauthier-Villars
VL - 46
IS - 4
SP - 1093
EP - 1131
AB - 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.
LA - eng
KW - first passage percolation; maximal flow; large deviation principle; concentration inequality; law of large numbers
UR - http://eudml.org/doc/240905
ER -

References

top
  1. [1] M. A. Ackoglu and U. Krengel. Ergodic theorems for superadditive processes. Journal für die Reine und Angewandte Mathematik 323 (1981) 53–67. Zbl0453.60039MR611442
  2. [2] I. Benjamini, G. Kalai and O. Schramm. First passage percolation has sublinear distance variance. Ann. Probab. 31 (2003) 1970–1978. Zbl1087.60070MR2016607
  3. [3] D. Boivin. Ergodic theorems for surfaces with minimal random weights. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998) 567–599. Zbl0910.60078MR1641662
  4. [4] B. Bollobás. Modern Graph Theory. Springer, New York, 1998. Zbl0902.05016MR1633290
  5. [5] S. Boucheron, G. Lugosi and P. Massart. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003) 1583–1614. Zbl1051.60020MR1989444
  6. [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. Zbl1103.82010MR2241754
  7. [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. Zbl0617.60099MR847132
  8. [8] A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications, 2nd edition. Applications of Mathematics (New York) 38. Springer, New York, 1998. Zbl0896.60013MR1619036
  9. [9] G. Grimmett. Percolation, 2nd edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin, 1999. Zbl0926.60004MR1707339
  10. [10] A. Gut. On complete convergence in the law of large numbers for subsequences. Ann. Probab. 13 (1985) 1286–1291. Zbl0582.60057MR806225
  11. [11] A. Gut. Complete convergence for arrays. Period. Math. Hungar. 25 (1992) 51–75. Zbl0760.60029MR1200841
  12. [12] G. H. Hardy, J. E. Littlewood and G. Pólya. Inequalities, 2nd edition. Cambridge Univ. Press, 1952. Zbl0010.10703MR46395JFM60.0169.01
  13. [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. Zbl0602.60098MR876084
  14. [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. Zbl0591.60096MR869483
  15. [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. Zbl0642.60020MR923110
  16. [16] R. T. Smythe. Multiparameter subadditive processes. Ann. Probab. 4 (1976) 772–782. Zbl0339.60022MR423495
  17. [17] M. Théret. Upper large deviations for the maximal flow in first-passage percolation. Stochastic Process. Appl. 117 (2007) 1208–1233. Zbl1121.60102MR2343936
  18. [18] M. Théret. On the small maximal flows in first passage percolation. Ann. Fac. Sci. Toulouse 17 (2008) 207–219. Zbl1152.60076MR2464099
  19. [19] M. Théret. Upper large deviations for maximal flows through a tilted cylinder. Preprint, 2009. Available at arxiv.org/abs/0907.0614. Zbl1308.60111
  20. [20] M. Wouts. Surface tension in the dilute Ising model. The Wulff construction. Comm. Math. Phys. 289 (2009) 157–204. Zbl1168.82007MR2504848
  21. [21] Y. Zhang. Critical behavior for maximal flows on the cubic lattice. J. Statist. Phys. 98 (2000) 799–811. Zbl0991.82019MR1749233
  22. [22] Y. Zhang. Limit theorems for maximum flows on a lattice. Preprint, 2007. Available at arxiv.org/abs/0710.4589. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.