×

Concentration inequalities for dependent random variables via the martingale method. (English) Zbl 1154.60310

Summary: The martingale method is used to establish concentration inequalities for a class of dependent random sequences on a countable state space, with the constants in the inequalities expressed in terms of certain mixing coefficients. Along the way, bounds are obtained on martingale differences associated with the random sequences, which may be of independent interest. As applications of the main result, concentration inequalities are also derived for inhomogeneous Markov chains and hidden Markov chains, and an extremal property associated with their martingale difference bounds is established. This work complements and generalizes certain concentration inequalities obtained by Marton and Samson, while also providing different proofs of some known results.

MSC:

60E15 Inequalities; stochastic orderings
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G42 Martingales with discrete parameter
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahlswede, R., Gács, P. and Körner, J. (1976). Bounds on conditional probabilities with applications in multi-user communication. Z. Wahrsch. Verw. Gebiete 34 157-177. · Zbl 0349.94038 · doi:10.1007/BF00535682
[2] Azuma, K. (1967). Weighted sums of certain dependent random variables. Tôhoku Math. J. (2) 19 357-367. · Zbl 0178.21103 · doi:10.2748/tmj/1178243286
[3] Behrends, E. (2000). Introduction to Markov Chains. Advanced Lectures in Mathematics . Friedr. Vieweg & Sohn, Braunschweig. With special emphasis on rapid mixing. · Zbl 0953.60063
[4] Bobkov, S. G. and Götze, F. (1999). Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 1-28. · Zbl 0924.46027 · doi:10.1006/jfan.1998.3326
[5] Bobkov, S. G. and Ledoux, M. (1998). On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures. J. Funct. Anal. 156 347-365. · Zbl 0920.60002 · doi:10.1006/jfan.1997.3187
[6] Boucheron, S., Lugosi, G. and Massart, P. (2003). Concentration inequalities using the entropy method. Ann. Probab. 31 1583-1614. · Zbl 1051.60020 · doi:10.1214/aop/1055425791
[7] Chatterjee, S. (2005). Concentration inequalities with exchangeable pairs. Ph.D. dissertation, Stanford Univ.
[8] Chazottes, J.-R., Collet, P., Külske, C. and Redig, F. (2007). Concentration inequalities for random fields via coupling. Probab. Theory Related Fields 137 201-225. · Zbl 1111.60070 · doi:10.1007/s00440-006-0026-1
[9] Dembo, A. (1997). Information inequalities and concentration of measure. Ann. Probab. 25 927-939. · Zbl 0880.60018 · doi:10.1214/aop/1024404424
[10] Dembo, A. and Zeitouni, O. (1996). Transportation approach to some concentration inequalities in product spaces. Electron. Comm. Probab. 1 83-90 (electronic). · Zbl 0916.28003
[11] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. JSTOR: · Zbl 0127.10602 · doi:10.2307/2282952
[12] Kontoyiannis, I., Lastras-Montano, L. A. and Meyn, S. (2005). Relative entropy and exponential deviation bounds for general Markov chains. In Proc. of Int. Symp. Inf. Theor. (ISIT), Adelaide, Australia .
[13] Kontorovich, L. (2006). Measure concentration of hidden Markov processes. Available at http://arxiv.org/abs/math.PR/0608064.
[14] Kontorovich, L. (2006). Measure concentration of Markov tree processes. Available at http://arxiv.org/abs/math.PR/0608511.
[15] Kontorovich, L. (2007). Measure concentration of strongly mixing processes with applications Ph.D. dissertation, Carnegie Mellon Univ.
[16] Ledoux, M. (1995/97). On Talagrand’s deviation inequalities for product measures. ESAIM Probab. Statist. 1 63-87 (electronic). · Zbl 0869.60013 · doi:10.1051/ps:1997103
[17] Ledoux, M. (2001). The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89 . American Mathematical Society, Providence, RI. · Zbl 0995.60002
[18] Markov, A. A. (1906). Extension of the law of large numbers to dependent quantities. Izvestiia Fiz.-Matem. Obsch. Kazan Univ. 15 135-156.
[19] Marton, K. (1995). A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 556-571. · Zbl 0856.60072 · doi:10.1007/BF02249263
[20] Marton, K. (1996). Bounding d\? -distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24 857-866. · Zbl 0865.60017 · doi:10.1214/aop/1039639365
[21] Marton, K. (1998). Measure concentration for a class of random processes. Probab. Theory Related Fields 110 427-439. · Zbl 0927.60050 · doi:10.1007/s004400050154
[22] Marton, K. (2003). Measure concentration and strong mixing. Studia Sci. Math. Hungar. 40 95-113. · Zbl 1027.60011 · doi:10.1556/SScMath.40.2003.1-2.8
[23] Marton, K. (2004). Measure concentration for Euclidean distance in the case of dependent random variables. Ann. Probab. 32 2526-2544. · Zbl 1071.60012 · doi:10.1214/009117904000000702
[24] McDiarmid, C. (1989). On the method of bounded differences. In Surveys in Combinatorics , 1989 ( Norwich , 1989). London Math. Soc. Lecture Note Ser. 141 148-188. Cambridge Univ. Press, Cambridge. · Zbl 0712.05012
[25] McDiarmid, C. (1998). Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin. 16 195-248. Springer, Berlin. · Zbl 0927.60027
[26] Otto, F. and Villani, C. (2000). Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. J. Funct. Anal. 173 361-400. · Zbl 0985.58019 · doi:10.1006/jfan.2000.3557
[27] Samson, P.-M. (2000). Concentration of measure inequalities for Markov chains and \Phi -mixing processes. Ann. Probab. 28 416-461. · Zbl 1044.60061 · doi:10.1214/aop/1019160125
[28] Schechtman, G. (2001). Concentration, Results and Applications. The Handbook in the Geometry of Banach Spaces . North-Holland, Amsterdam. · Zbl 1057.46011 · doi:10.1016/S1874-5849(03)80044-X
[29] Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73-205. · Zbl 0864.60013 · doi:10.1007/BF02699376
[30] Talagrand, M. (1996). New concentration inequalities in product spaces. Invent. Math. 126 505-563. · Zbl 0893.60001 · doi:10.1007/s002220050108
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.