Exponential concentration for first passage percolation through modified Poincaré inequalities
Benaïm, Michel ; Rossignol, Raphaël
Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008), p. 544-573 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

On obtient une nouvelle inégalité de concentration exponentielle pour la percolation de premier passage, valable pour une large classe de distributions des temps d'arêtes. Ceci améliore et étend un résultat de Benjamini, Kalai et Schramm (Ann. Probab. 31 (2003)) qui donnait une borne sur la variance pour des temps d'arêtes suivant une loi de Bernoulli. Notre approche se fonde sur des inégalités fonctionnelles étendant les travaux de Rossignol (Ann. Probab. 35 (2006)), Falik et Samorodnitsky (Combin. Probab. Comput. 16 (2007)).

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

Publié le : 2008-01-01
DOI : https://doi.org/10.1214/07-AIHP124
Classification:  60E15,  60K35 
@article{AIHPB_2008__44_3_544_0,
     author = {Bena\"\i m, Michel and Rossignol, Rapha\"el},
     title = {Exponential concentration for first passage percolation through modified Poincar\'e inequalities},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {44},
     year = {2008},
     pages = {544-573},
     doi = {10.1214/07-AIHP124},
     mrnumber = {2451057},
     zbl = {1186.60102},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2008__44_3_544_0}
}

Benaïm, Michel; Rossignol, Raphaël. Exponential concentration for first passage percolation through modified Poincaré inequalities. Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008) pp. 544-573. doi : 10.1214/07-AIHP124. http://gdmltest.u-ga.fr/item/AIHPB_2008__44_3_544_0/

[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. | MR 1845806 | Zbl 0982.46026

[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. | MR 1682248 | Zbl 0932.05001

[3] D. Bakry. Functional inequalities for Markov semigroups. In Probability Measures on Groups: Recent Directions and Trends. Tota Inst. Fund Res., Mumbai, 91-147. | MR 2213477 | Zbl 1148.60057

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

[5] 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

[6] S. Boucheron, O. Bousquet, G. Lugosi and P. Massart. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005) 514-560. | MR 2123200 | Zbl 1074.60018

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

[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. | Numdam | MR 941981 | Zbl 0616.46023

[9] D. Falik and A. Samorodnitsky. Edge-isoperimetric inequalities and influences. Combin. Probab. Comput. 16 (2007) 693-712. | MR 2346808 | Zbl 1134.05309

[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. | MR 198576 | Zbl 0143.40402

[11] G. H. Hardy, J. E. Littlewood and G. Pólya. Inequalities. Cambridge University Press, 1934. | JFM 60.0169.01 | Zbl 0010.10703

[12] C. D. Howard. Models of first-passage percolation. In Encyclopaedia Math. Sci. 125-173. Springer, Berlin, 2004. | MR 2023652 | Zbl pre02042288

[13] K. Johansson. Shape fluctuations and random matrices. Comm. Math. Phys. 209 (2000) 437-476. | MR 1737991 | Zbl 0969.15008

[14] K. Johansson. Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445-456. | MR 1757595 | Zbl 0960.60097

[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. | MR 876084 | Zbl 0602.60098

[16] H. Kesten. On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993) 296-338. | MR 1221154 | Zbl 0783.60103

[17] M. Ledoux. On Talagrand's deviation inequalities for product measures. ESAIM P&S 1 (1996) 63-87. | Numdam | MR 1399224 | Zbl 0869.60013

[18] M. Ledoux. The Concentration of Measure Phenomenon. Amer. Math. Soc., Providence, RI, 2001. | MR 1849347 | Zbl 0995.60002

[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. | MR 2349607 | Zbl 1130.15012

[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. | Numdam | MR 1971588 | Zbl 1053.60014

[21] R. Rossignol. Threshold for monotone symmetric properties through a logarithmic Sobolev inequality. Ann. Probab. 35 (2006) 1707-1725. | MR 2271478 | Zbl 1115.60021

[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. | MR 1490046 | Zbl 0885.60061

[23] M. Talagrand. On Russo's approximate zero-one law. Ann. Probab. 22 (1994) 1576-1587. | MR 1303654 | Zbl 0819.28002

[24] M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 (1995) 73-205. | Numdam | MR 1361756 | Zbl 0864.60013

[25] M. Talagrand. New concentration inequalities in product spaces. Invent. Math. 126 (1996) 505-563. | MR 1419006 | Zbl 0893.60001

[26] M. Talagrand. A new look at independence. Ann. Probab. 24 (1996) 1-34. | MR 1387624 | Zbl 0858.60019

[27] K. Yosida. Functional Analysis, 6th edition. Springer-Verlag, Berlin, 1980. | MR 617913