Theory of Probability and Mathematical Statistics
Tensorizations of Hoeffding’s Lemma
Jonathan Root and Mark Kon
Link
Abstract: Relatively simple large-deviation inequalities have been proved previously as consequences of the work of Hoeffding, using exponential moment generating functions. Lipschitz-like functions can be seen as concentrating about their mean using a tensorization of Hoeffding’s lemma in what is known as McDiarmid’s inequality. We consider the concentration of certain variables using a tensorization of Hoeffding’s lemma to address so-called oscillatory behaviors related to independence. We start with the Boolean cube itself and the concentration of the Hamming metric. The concentration of the Hamming metric is guaranteed for product distributions in high dimensions, as it is a sum of bounded random variables. In fact, in the product setting, the rate at which the metric concentrates is the order of the dimension, independent of the fixed point. This fails, however, for certain dependent distributions. We bound the exponential moment generating function of a given variable on the Boolean cube and characterize the concentration by means of a certain correlation condition. Our methods are advantageous since they are both simple and comprehensive. We extend these bounds from sums on the Boolean cube to sums on a finite, discrete sample space. We characterize the dependency structure by an oscillation term related to the nth marginal distribution, which vanishes when the variables are independent. Using Markov’s inequality, we obtain concentration inequalities for some general classes of dependent random variables.
Keywords: Concentration inequalities, sums of dependent random variables
Bibliography: Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703
Keith Ball, An elementary introduction to modern convex geometry, Flavors of geometry, Math. Sci. Res. Inst. Publ., vol. 31, Cambridge Univ. Press, Cambridge, 1997, pp. 1–58. MR 1491097, DOI 10.2977/prims/1195164788
A. Barvinok, Math 710: Measure Concentration, 2005, https://dept.math.lsa.umich.edu/~barvinok/total710.pdf.
Patrick Billingsley, Probability and measure, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, New York-Chichester-Brisbane, 1979. MR 534323
M. Gromov and V. D. Milman, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), no. 4, 843–854. MR 708367, DOI 10.2307/2374298
Allan Gut, Probability: a graduate course, 2nd ed., Springer Texts in Statistics, Springer, New York, 2013. MR 2977961, DOI 10.1007/978-1-4614-4708-5
Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363, DOI 10.1080/01621459.1963.10500830
Kumar Joag-Dev and Frank Proschan, Negative association of random variables, with applications, Ann. Statist. 11 (1983), no. 1, 286–295. MR 684886, DOI 10.1214/aos/1176346079
Leonid Kontorovich and Kavita Ramanan, Concentration inequalities for dependent random variables via the martingale method, Ann. Probab. 36 (2008), no. 6, 2126–2158. MR 2478678, DOI 10.1214/07-AOP384
Michel Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347, DOI 10.1090/surv/089
Katalin Marton, Measure concentration for Euclidean distance in the case of dependent random variables, Ann. Probab. 32 (2004), no. 3B, 2526–2544. MR 2078549, DOI 10.1214/009117904000000702
K. Marton, Measure concentration and strong mixing, Studia Sci. Math. Hungar. 40 (2003), no. 1-2, 95–113. MR 2002993, DOI 10.1556/SScMath.40.2003.1-2.8
K. Marton, A measure concentration inequality for contracting Markov chains, Geom. Funct. Anal. 6 (1996), no. 3, 556–571. MR 1392329, DOI 10.1007/BF02249263
Colin McDiarmid, Concentration, Probabilistic methods for algorithmic discrete mathematics, Algorithms Combin., vol. 16, Springer, Berlin, 1998, pp. 195–248. MR 1678578, DOI 10.1007/978-3-662-12788-9_{6}
Vitali D. Milman and Gideon Schechtman, Asymptotic theory of finite-dimensional normed spaces, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov. MR 856576
V. D. Milman, A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies, Funkcional. Anal. i Priložen. 5 (1971), no. 4, 28–37 (Russian). MR 293374
Robin Pemantle, Towards a theory of negative dependence, J. Math. Phys. 41 (2000), no. 3, 1371–1390. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. MR 1757964, DOI 10.1063/1.533200
Robin Pemantle and Yuval Peres, Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures, Combin. Probab. Comput. 23 (2014), no. 1, 140–160. MR 3197973, DOI 10.1017/S0963548313000345
Paul-Marie Samson, Concentration of measure inequalities for Markov chains and Φ-mixing processes, Ann. Probab. 28 (2000), no. 1, 416–461. MR 1756011, DOI 10.1214/aop/1019160125
Michel Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1–34. MR 1387624, DOI 10.1214/aop/1042644705
Terence Tao, Topics in random matrix theory, Graduate Studies in Mathematics, vol. 132, American Mathematical Society, Providence, RI, 2012. MR 2906465, DOI 10.1090/gsm/132
