Exponential concentration for first passage percolation through modified Poincaré inequalities

Michel Benaïm; Raphaël Rossignol

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

  • Volume: 44, Issue: 3, page 544-573
  • ISSN: 0246-0203

Abstract

top
We provide a new exponential concentration inequality for first passage percolation valid for a wide class of edge times distributions. This improves and extends a result by Benjamini, Kalai and Schramm (Ann. Probab.31 (2003)) which gave a variance bound for Bernoulli edge times. Our approach is based on some functional inequalities extending the work of Rossignol (Ann. Probab.35 (2006)), Falik and Samorodnitsky (Combin. Probab. Comput.16 (2007)).

How to cite

top

Benaïm, Michel, and Rossignol, Raphaël. "Exponential concentration for first passage percolation through modified Poincaré inequalities." Annales de l'I.H.P. Probabilités et statistiques 44.3 (2008): 544-573. <http://eudml.org/doc/77982>.

@article{Benaïm2008,
abstract = {We provide a new exponential concentration inequality for first passage percolation valid for a wide class of edge times distributions. This improves and extends a result by Benjamini, Kalai and Schramm (Ann. Probab.31 (2003)) which gave a variance bound for Bernoulli edge times. Our approach is based on some functional inequalities extending the work of Rossignol (Ann. Probab.35 (2006)), Falik and Samorodnitsky (Combin. Probab. Comput.16 (2007)).},
author = {Benaïm, Michel, Rossignol, Raphaël},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {modified Poincaré inequality; concentration inequality; hypercontractivity; first passage percolation; modified Poincare inequality},
language = {eng},
number = {3},
pages = {544-573},
publisher = {Gauthier-Villars},
title = {Exponential concentration for first passage percolation through modified Poincaré inequalities},
url = {http://eudml.org/doc/77982},
volume = {44},
year = {2008},
}

TY - JOUR
AU - Benaïm, Michel
AU - Rossignol, Raphaël
TI - Exponential concentration for first passage percolation through modified Poincaré inequalities
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2008
PB - Gauthier-Villars
VL - 44
IS - 3
SP - 544
EP - 573
AB - We provide a new exponential concentration inequality for first passage percolation valid for a wide class of edge times distributions. This improves and extends a result by Benjamini, Kalai and Schramm (Ann. Probab.31 (2003)) which gave a variance bound for Bernoulli edge times. Our approach is based on some functional inequalities extending the work of Rossignol (Ann. Probab.35 (2006)), Falik and Samorodnitsky (Combin. Probab. Comput.16 (2007)).
LA - eng
KW - modified Poincaré inequality; concentration inequality; hypercontractivity; first passage percolation; modified Poincare inequality
UR - http://eudml.org/doc/77982
ER -

References

top
  1. [1] C. Ané, S. Blachère, D. Chafaï, P. Fougères, I. Gentil, F. Malrieu, C. Roberto and G. Scheffer. Sur les inégalités de Sobolev logarithmiques. Société Mathématique de France, Paris, 2000. Zbl0982.46026MR1845806
  2. [2] J. Baik, P. Deift and K. Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 (1999) 1119–1178. Zbl0932.05001MR1682248
  3. [3] D. Bakry. Functional inequalities for Markov semigroups. In Probability Measures on Groups: Recent Directions and Trends. Tota Inst. Fund Res., Mumbai, 91–147. Zbl1148.60057MR2213477
  4. [4] M. Benaim and R. Rossignol. A modified Poincaré inequality and its application to first passage percolation, 2006. Available at http://arxiv.org/abs/math.PR/0602496. Zbl1186.60102
  5. [5] I. Benjamini, G. Kalai and O. Schramm. First passage percolation has sublinear distance variance. Ann. Probab. 31 (2003) 1970–1978. Zbl1087.60070MR2016607
  6. [6] S. Boucheron, O. Bousquet, G. Lugosi and P. Massart. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005) 514–560. Zbl1074.60018MR2123200
  7. [7] S. Boucheron, G. Lugosi and P. Massart. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003) 1583–1614. Zbl1051.60020MR1989444
  8. [8] M. Émery and J. Yukich. A simple proof of the logarithmic Sobolev inequality on the circle. Séminaire de probabilités de Strasbourg 21 (1987) 173–175. Zbl0616.46023MR941981
  9. [9] D. Falik and A. Samorodnitsky. Edge-isoperimetric inequalities and influences. Combin. Probab. Comput. 16 (2007) 693–712. Zbl1134.05309MR2346808
  10. [10] J. M. Hammersley and D. J. A. Welsh. First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Proc. Internat Res. Semin., Statist. Lab., Univ. California, Berkeley, Calif. 61–110. Springer, New York, 1965. Zbl0143.40402MR198576
  11. [11] G. H. Hardy, J. E. Littlewood and G. Pólya. Inequalities. Cambridge University Press, 1934. Zbl0010.10703JFM60.0169.01
  12. [12] C. D. Howard. Models of first-passage percolation. In Encyclopaedia Math. Sci. 125–173. Springer, Berlin, 2004. Zbl1206.82048MR2023652
  13. [13] K. Johansson. Shape fluctuations and random matrices. Comm. Math. Phys. 209 (2000) 437–476. Zbl0969.15008MR1737991
  14. [14] K. Johansson. Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445–456. Zbl0960.60097MR1757595
  15. [15] H. Kesten. Aspects of first passage percolation. In Ecole d’été de probabilité de Saint-Flour XIV—1984 125–264. Lecture Notes in Math. 1180. Springer, Berlin, 1986. Zbl0602.60098MR876084
  16. [16] H. Kesten. On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993) 296–338. Zbl0783.60103MR1221154
  17. [17] M. Ledoux. On Talagrand’s deviation inequalities for product measures. ESAIM P&S 1 (1996) 63–87. Zbl0869.60013MR1399224
  18. [18] M. Ledoux. The Concentration of Measure Phenomenon. Amer. Math. Soc., Providence, RI, 2001. Zbl0995.60002MR1849347
  19. [19] M. Ledoux. Deviation inequalities on largest eigenvalues. In Summer School on the Connections between Probability and Geometric Functional Analysis, 14–19 June 2005. To appear, 2005. Available at http://www.lsp.ups-tlse.fr/Ledoux/Jerusalem.pdf. Zbl1130.15012MR2349607
  20. [20] L. Miclo. Sur l’inégalité de Sobolev logarithmique des opérateurs de Laguerre à petit paramètre. In Séminaire de Probabilités de Strasbourg, 36 (2002) 222–229. Zbl1053.60014MR1971588
  21. [21] R. Rossignol. Threshold for monotone symmetric properties through a logarithmic Sobolev inequality. Ann. Probab. 35 (2006) 1707–1725. Zbl1115.60021MR2271478
  22. [22] L. Saloff-Coste. Lectures on finite Markov chains. In Ecole d’été de probabilité de Saint-Flour XXVI 301–413. P. Bernard (Ed.). Springer, New York, 1997. Zbl0885.60061MR1490046
  23. [23] M. Talagrand. On Russo’s approximate zero–one law. Ann. Probab. 22 (1994) 1576–1587. Zbl0819.28002MR1303654
  24. [24] M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 (1995) 73–205. Zbl0864.60013MR1361756
  25. [25] M. Talagrand. New concentration inequalities in product spaces. Invent. Math. 126 (1996) 505–563. Zbl0893.60001MR1419006
  26. [26] M. Talagrand. A new look at independence. Ann. Probab. 24 (1996) 1–34. Zbl0858.60019MR1387624
  27. [27] K. Yosida. Functional Analysis, 6th edition. Springer-Verlag, Berlin, 1980. MR617913

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.