Exponential concentration for first passage percolation through modified Poincaré inequalities. (English) Zbl 1186.60102
The authors provide a new exponential concentration inequality for first passage percolation valid for a wide class of edge times distributions. This improves a result by I. Benjamini, G. Kalai and O. Schramm [Ann. Probab. 31, No. 4, 1970–1978 (2003; Zbl 1087.60070)] which gave a variance bound for Bernoulli edge times. The authors of the paper use approach which is based on some functional inequalities extending the work of Rassignol, Falik and Samorodnitsky.
Reviewer: Anatoliy Pogorui (Zhytomyr)
MSC:
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 60E15 | Inequalities; stochastic orderings |
Keywords:
modified Poincare inequality; concentration inequality; hypercontractivity; first passage percolationCitations:
Zbl 1087.60070References:
| [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. · 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. JSTOR: · Zbl 0932.05001 · doi:10.1090/S0894-0347-99-00307-0 |
| [3] | D. Bakry. Functional inequalities for Markov semigroups. In Probability Measures on Groups : Recent Directions and Trends. Tota Inst. Fund Res. , Mumbai, 91-147. · 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. · Zbl 1087.60070 · doi:10.1214/aop/1068646373 |
| [6] | S. Boucheron, O. Bousquet, G. Lugosi and P. Massart. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005) 514-560. · Zbl 1074.60018 · doi:10.1214/009117904000000856 |
| [7] | S. Boucheron, G. Lugosi and P. Massart. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003) 1583-1614. · Zbl 1051.60020 · doi:10.1214/aop/1055425791 |
| [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. · Zbl 0616.46023 |
| [9] | D. Falik and A. Samorodnitsky. Edge-isoperimetric inequalities and influences. Combin. Probab. Comput. 16 (2007) 693-712. · Zbl 1134.05309 · doi:10.1017/S0963548306008340 |
| [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. · Zbl 0143.40402 |
| [11] | G. H. Hardy, J. E. Littlewood and G. Pólya. Inequalities . Cambridge University Press, 1934. |
| [12] | C. D. Howard. Models of first-passage percolation. In Encyclopaedia Math. Sci. 125-173. Springer, Berlin, 2004. · Zbl 1206.82048 |
| [13] | K. Johansson. Shape fluctuations and random matrices. Comm. Math. Phys. 209 (2000) 437-476. · Zbl 0969.15008 · doi:10.1007/s002200050027 |
| [14] | K. Johansson. Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445-456. · Zbl 0960.60097 · doi:10.1007/s004409900039 |
| [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. · Zbl 0602.60098 · doi:10.1007/BFb0074919 |
| [16] | H. Kesten. On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993) 296-338. · Zbl 0783.60103 · doi:10.1214/aoap/1177005426 |
| [17] | M. Ledoux. On Talagrand’s deviation inequalities for product measures. ESAIM P&S 1 (1996) 63-87. · Zbl 0869.60013 · doi:10.1051/ps:1997103 |
| [18] | M. Ledoux. The Concentration of Measure Phenomenon . Amer. Math. Soc., Providence, RI, 2001. · 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. · Zbl 1130.15012 · doi:10.1007/978-3-540-72053-9_10 |
| [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. · Zbl 1053.60014 |
| [21] | R. Rossignol. Threshold for monotone symmetric properties through a logarithmic Sobolev inequality. Ann. Probab. 35 (2006) 1707-1725. · Zbl 1115.60021 · doi:10.1214/009117906000000287 |
| [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. · Zbl 0885.60061 · doi:10.1007/BFb0092621 |
| [23] | M. Talagrand. On Russo’s approximate zero-one law. Ann. Probab. 22 (1994) 1576-1587. · Zbl 0819.28002 · doi:10.1214/aop/1176988612 |
| [24] | M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 (1995) 73-205. · Zbl 0864.60013 · doi:10.1007/BF02699376 |
| [25] | M. Talagrand. New concentration inequalities in product spaces. Invent. Math. 126 (1996) 505-563. · Zbl 0893.60001 · doi:10.1007/s002220050108 |
| [26] | M. Talagrand. A new look at independence. Ann. Probab. 24 (1996) 1-34. · Zbl 0858.60019 · doi:10.1214/aop/1042644705 |
| [27] | K. Yosida. Functional Analysis , 6th edition. Springer-Verlag, Berlin, 1980. · Zbl 0435.46002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
