Exponential concentration for first passage percolation through modified Poincaré inequalities
Annales de l'I.H.P. Probabilités et statistiques, Volume 44 (2008) no. 3, pp. 544-573.

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

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

DOI: 10.1214/07-AIHP124
Classification: 60E15,  60K35
Keywords: modified Poincaré inequality, concentration inequality, hypercontractivity, first passage percolation
@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},
     pages = {544--573},
     publisher = {Gauthier-Villars},
     volume = {44},
     number = {3},
     year = {2008},
     doi = {10.1214/07-AIHP124},
     zbl = {1186.60102},
     mrnumber = {2451057},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1214/07-AIHP124/}
}
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
DA  - 2008///
SP  - 544
EP  - 573
VL  - 44
IS  - 3
PB  - Gauthier-Villars
UR  - http://archive.numdam.org/articles/10.1214/07-AIHP124/
UR  - https://zbmath.org/?q=an%3A1186.60102
UR  - https://www.ams.org/mathscinet-getitem?mr=2451057
UR  - https://doi.org/10.1214/07-AIHP124
DO  - 10.1214/07-AIHP124
LA  - en
ID  - AIHPB_2008__44_3_544_0
ER  - 
%0 Journal Article
%A Benaïm, Michel
%A Rossignol, Raphaël
%T Exponential concentration for first passage percolation through modified Poincaré inequalities
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2008
%P 544-573
%V 44
%N 3
%I Gauthier-Villars
%U https://doi.org/10.1214/07-AIHP124
%R 10.1214/07-AIHP124
%G en
%F 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, Volume 44 (2008) no. 3, pp. 544-573. doi : 10.1214/07-AIHP124. http://archive.numdam.org/articles/10.1214/07-AIHP124/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by Sources: