zbMATH — the first resource for mathematics

A Hoeffding inequality for Markov chains. (English) Zbl 1412.60049
Summary: We prove deviation bounds for the random variable \(\sum _{i=1}^{n} f_i(Y_i)\) in which \(\{Y_i\}_{i=1}^{\infty }\) is a Markov chain with stationary distribution and state space \([N]\), and \(f_i: [N] \rightarrow [-a_i, a_i]\). Our bound improves upon previously known bounds in that the dependence is on \(\sqrt{a_1^2+\cdots +a_n^2}\) rather than \(\max _{i}\{a_i\}\sqrt{n} .\) We also prove deviation bounds for certain types of sums of vector–valued random variables obtained from a Markov chain in a similar manner. One application includes bounding the expected value of the Schatten \(\infty \)-norm of a random matrix whose entries are obtained from a Markov chain.

60F10 Large deviations
Full Text: DOI Euclid arXiv
[1] Rudolf Ahlswede and Andreas Winter, Strong converse for identification via quantum channels, IEEE Trans. Inform. Theory 48 (2002), no. 3, 569-579. · Zbl 1071.94530
[2] Afonso S. Bandeira and Ramon van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries, Ann. Probab. 44 (2016), no. 4, 2479-2506. · Zbl 1372.60004
[3] Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher, Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified, STACS, 2012, arXiv:1201.0559, pp. 124-135. · Zbl 1245.68143
[4] I. H. Dinwoodie, A probability inequality for the occupation measure of a reversible Markov chain, Ann. Appl. Probab. 5 (1995), no. 1, 37-43. · Zbl 0829.60022
[5] Jianqing Fan, Bai Jiang, and Qiang Sun, Hoeffding’s lemma for Markov chains and its applications to statistical learning, 2018.
[6] Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava, A matrix expander Chernoff bound, 2017. · Zbl 1442.60007
[7] David Gillman, A Chernoff bound for random walks on expander graphs, SIAM J. Comput. 27 (1998), no. 4, 1203-1220. · Zbl 0911.60016
[8] Jan Hazła and Thomas Holenstein, Upper tail estimates with combinatorial proofs, STACS, 2015, arXiv:1405.2349, pp. 392-405. · Zbl 1356.05133
[9] Alexander D. Healy, Randomness-efficient sampling within \({\rm NC}^1\), Comput. Complexity 17 (2008), no. 1, 3-37. · Zbl 1149.68027
[10] Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. · Zbl 0127.10602
[11] Nabil Kahale, Large deviation bounds for Markov chains, Combin. Probab. Comput. 6 (1997), no. 4, 465-474. · Zbl 0892.60080
[12] Carlos A. León and François Perron, Optimal Hoeffding bounds for discrete reversible Markov chains, Ann. Appl. Probab. 14 (2004), no. 2, 958-970. · Zbl 1056.60070
[13] Pascal Lezaud, Chernoff-type bound for finite Markov chains, Ann. Appl. Probab. 8 (1998), no. 3, 849-867. · Zbl 0938.60027
[14] Assaf Naor, On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs, Combin. Probab. Comput. 21 (2012), no. 4, 623-634. · Zbl 1247.05104
[15] Assaf Naor, Shravas Rao, and Oded Regev, On the rate of convergence of the vector-valued ergodic theorem for Markov chains with a spectral gap, 2017, In preparation.
[16] Daniel Paulin, Concentration inequalities for Markov chains by Marton couplings and spectral methods, Electron. J. Probab. 20 (2015), 32 pp. · Zbl 1342.60121
[17] Shravas Rao and Oded Regev, A sharp tail bound for the expander random sampler, 2017.
[18] Walter Rudin, Functional analysis, second ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. · Zbl 0867.46001
[19] Michel Talagrand, Regularity of Gaussian processes, Acta Math. 159 (1987), no. 1-2, 99-149. · Zbl 0712.60044
[20] Michel Talagrand, Upper and lower bounds for stochastic processes, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 60, Springer, Heidelberg, 2014, Modern methods and classical problems. · Zbl 1293.60001
[21] Joel A. Tropp, An introduction to matrix concentration inequalities, Found. Trends Mach. Learn. 8 (2015), no. 1-2, 1-230. · Zbl 1391.15071
[22] Roy Wagner, Tail estimates for sums of variables sampled by a random walk, Comb. Probab. Comput. 17 (2008), no. 2, 307-316, arXiv:math/0608740. · Zbl 1144.60308
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.