On the Bennett-Hoeffding inequality
Pinelis, Iosif
Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014), p. 15-27 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

La borne de Bennett-Hoeffding pour des sommes de variables aléatoires indépendantes est précisée, en prenant en compte la partie positive des troisièmes moments et sensiblement améliorée en utilisant, au lieu de la classe de toutes les fonctions exponentielles croissantes, une classe beaucoup plus important de fonctions de moment généralisées. Les limites qui en résultent ont certaines propriétés d'optimalité. Les résultats peuvent être étendus de manière standard pour (les fonctions maximales de) (sur)martingales. La preuve du résultat principal repose sur une méthode apparemment nouvelle. Des éléments de la preuve utilisent également la méthode des certificats de positivité de la géométrie algébrique réelle.

The well-known Bennett-Hoeffding bound for sums of independent random variables is refined, by taking into account positive-part third moments, and at that significantly improved by using, instead of the class of all increasing exponential functions, a much larger class of generalized moment functions. The resulting bounds have certain optimality properties. The results can be extended in a standard manner to (the maximal functions of) (super)martingales. The proof of the main result relies on an apparently new method that may be referred to as infinitesimal spin-off. Parts of the proof also use the method of certificates of positivity in real algebraic geometry.

Publié le : 2014-01-01
DOI : https://doi.org/10.1214/12-AIHP495
Classification:  60E15,  60G50,  60E07,  60E10,  60G42,  60G48,  60G51 
@article{AIHPB_2014__50_1_15_0,
     author = {Pinelis, Iosif},
     title = {On the Bennett-Hoeffding inequality},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {50},
     year = {2014},
     pages = {15-27},
     doi = {10.1214/12-AIHP495},
     mrnumber = {3161520},
     zbl = {1288.60025},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2014__50_1_15_0}
}

Pinelis, Iosif. On the Bennett-Hoeffding inequality. Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) pp. 15-27. doi : 10.1214/12-AIHP495. http://gdmltest.u-ga.fr/item/AIHPB_2014__50_1_15_0/

[1] G. Bennett. Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc. 57 (1962) 33-45. | Zbl 0104.11905

[2] V. Bentkus. A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand. Liet. Mat. Rink. 42 (2002) 332-342. | MR 1947624 | Zbl 1021.60012

[3] V. Bentkus, N. Kalosha and M. Van Zuijlen. On domination of tail probabilities of (super)martingales: Explicit bounds. Liet. Mat. Rink. 46 (2006) 3-54. | MR 2251440 | Zbl 1138.60020

[4] V. Bentkus. On Hoeffding's inequalities. Ann. Probab. 32 (2004) 1650-1673. | MR 2060313 | Zbl 1062.60011

[5] E. Berger. Majorization, exponential inequalities and almost sure behavior of vector-valued random variables. Ann. Probab. 19 (1991) 1206-1226. | MR 1112413 | Zbl 0757.60002

[6] P. Billingsley. Convergence of Probability Measures. Wiley, New York, 1968. | MR 233396 | Zbl 0944.60003

[7] E. Bolthausen and F. Götze. The rate of convergence for multivariate sampling statistics. Ann. Statist. 21 (1993) 1692-1710. | MR 1245764 | Zbl 0798.62023

[8] S. Boucheron, G. Lugosi and P. Massart. A sharp concentration inequality with applications. Random Structures Algorithms 16 (2000) 277-292. | MR 1749290 | Zbl 0954.60008

[9] O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris 334 (2002) 495-500. | MR 1890640 | Zbl 1001.60021

[10] O. Bousquet. Concentration inequalities for sub-additive functions using the entropy method. In Stochastic Inequalities and Applications 213-247. Progr. Probab. 56. Birkhäuser, Basel, 2003. | MR 2073435 | Zbl 1037.60015

[11] G. Cassier. Problème des moments sur un compact de 𝐑 n et décomposition de polynômes à plusieurs variables. J. Funct. Anal. 58 (1984) 254-266. | MR 759099 | Zbl 0556.44006

[12] L. H. Y. Chen and Q.-M. Shao. Normal approximation for nonlinear statistics using a concentration inequality approach. Bernoulli 13 (2007) 581-599. | MR 2331265 | Zbl 1146.62310

[13] A. Cohen, Y. Rabinovich, A. Schuster and H. Shachnai. Optimal bounds on tail probabilities: A study of an approach. In Advances in Randomized Parallel Computing 1-24. Comb. Optim. 5. Kluwer Acad. Publ., Dordrecht, 1999. | MR 1782937 | Zbl 0944.60032

[14] G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Quantifier Elimination and Cylindrical Algebraic Decomposition (Linz, 1993) 85-121. Texts Monogr. Symbol. Comput. Springer, Vienna, 1998. | MR 1634190 | Zbl 0900.03055

[15] V. H. De La Peña. A general class of exponential inequalities for martingales and ratios. Ann. Probab. 27 (1999) 537-564. | MR 1681153 | Zbl 0942.60004

[16] J.-M. Dufour and M. Hallin. Improved Eaton bounds for linear combinations of bounded random variables, with statistical applications. J. Amer. Statist. Assoc. 88 (1993) 1026-1033. | MR 1242946 | Zbl 0792.62041

[17] K. Dzhaparidze and J. H. Van Zanten. On Bernstein-type inequalities for martingales. Stochastic Process. Appl. 93 (2001) 109-117. | MR 1819486 | Zbl 1051.60022

[18] M. L. Eaton. A note on symmetric Bernoulli random variables. Ann. Math. Statist. 41 (1970) 1223-1226. | MR 268930 | Zbl 0203.51805

[19] M. L. Eaton. A probability inequality for linear combinations of bounded random variables. Ann. Statist. 2 (1974) 609-613. | Zbl 0282.62012

[20] D. A. Freedman. On tail probabilities for martingales. Ann. Probability 3 (1975) 100-118. | MR 380971 | Zbl 0313.60037

[21] D. H. Fuk and S. V. Nagaev. Probabilistic inequalities for sums of independent random variables. Teor. Verojatnost. i Primenen. 16 (1971) 660-675. | MR 293695 | Zbl 0259.60024

[22] D. Handelman. Positive polynomials and product type actions of compact groups. Mem. Amer. Math. Soc. 54 (1985) xi+79. | MR 783217 | Zbl 0571.46045

[23] D. Handelman. Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132 (1988) 35-62. | MR 929582 | Zbl 0659.52002

[24] W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963) 13-30. | MR 144363 | Zbl 0127.10602

[25] S. Janson. Large deviations for sums of partly dependent random variables. Random Structures Algorithms 24 (2004) 234-248. | MR 2068873 | Zbl 1044.60021

[26] O. Kallenberg. Foundations of Modern Probability, 2nd edition. Probability and Its Applications (New York). Springer, New York, 2002. | MR 1876169 | Zbl 0892.60001

[27] T. Klein and E. Rio. Concentration around the mean for maxima of empirical processes. Ann. Probab. 33 (2005) 1060-1077. | MR 2135312 | Zbl 1066.60023

[28] T. Klein, Y. Ma and N. Privault. Convex concentration inequalities and forward-backward stochastic calculus. Electron. J. Probab. 11 (2006) 486-512 (electronic). | MR 2242653 | Zbl 1112.60034

[29] J.-L. Krivine. Anneaux préordonnés. J. Analyse Math. 12 (1964) 307-326. | MR 175937 | Zbl 0134.03902

[30] J.-L. Krivine. Quelques propriétés des préordres dans les anneaux commutatifs unitaires. C. R. Acad. Sci. Paris 258 (1964) 3417-3418. | MR 169083 | Zbl 0119.03602

[31] S. Łojasiewicz. Sur les ensembles semi-analytiques. In Actes du Congrès International des Mathématiciens (Nice, 1970) 2 237-241. Gauthier-Villars, Paris, 1971. | MR 425152 | Zbl 0241.32005

[32] P. Massart. About the constants in Talagrand's concentration inequalities for empirical processes. Ann. Probab. 28 (2000) 863-884. | MR 1782276 | Zbl 1140.60310

[33] S. V. Nagaev. Some limit theorems for large deviations. Theory Probab. Appl. 10 (1965) 214-235. | MR 185644 | Zbl 0144.18704

[34] S. V. Nagaev. Large deviations of sums of independent random variables. Ann. Probab. 7 (1979) 745-789. | MR 542129 | Zbl 0418.60033

[35] I. Pinelis. On the Bennett-Hoeffding inequality. Preprint. Available at arXiv:0902.4058v1 [math.PR]. | Numdam | Zbl 1288.60025

[36] I. Pinelis and R. Molzon. Berry-Esséen bounds for general nonlinear statistics, with applications to Pearson's and non-central Student's and Hotelling's. Preprint. Available at arXiv:0906.0177v3 [math.ST].

[37] I. F. Pinelis and A. I. Sakhanenko. Remarks on inequalities for probabilities of large deviations. Theory Probab. Appl. 30 (1985) 143-148. | MR 779438 | Zbl 0583.60023

[38] I. S. Pinelis and S. A. Utev. Sharp exponential estimates for sums of independent random variables. Theory Probab. Appl. 34 (1989) 340-346. | MR 1005745 | Zbl 0693.60036

[39] I. Pinelis. An approach to inequalities for the distributions of infinite-dimensional martingales. In Probability in Banach Spaces, 8 (Brunswick, ME, 1991) 128-134. Progr. Probab. 30. Birkhäuser Boston, Boston, MA, 1992. | MR 1227615 | Zbl 0793.60016

[40] I. Pinelis. On a majorization inequality for sums of independent random vectors. Statist. Probab. Lett. 19 (1994) 97-99. | MR 1256696 | Zbl 0801.60010

[41] I. Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. Ann. Probab. 22 (1994) 1679-1706. | MR 1331198 | Zbl 0836.60015

[42] I. Pinelis. Optimal tail comparison based on comparison of moments. In High Dimensional Probability (Oberwolfach, 1996) 297-314. Progr. Probab. 43, Birkhäuser, Basel, 1998. | MR 1652335 | Zbl 0906.60014

[43] I. Pinelis. Fractional sums and integrals of r-concave tails and applications to comparison probability inequalities. In Advances in Stochastic Inequalities (Atlanta, GA, 1997) 149-168. Contemp. Math. 234. Amer. Math. Soc., Providence, RI, 1999. | MR 1694770 | Zbl 0937.60011

[44] I. Pinelis. Dimensionality reduction in extremal problems for moments of linear combinations of vectors with random coefficients. In Stochastic Inequalities and Applications 169-185. Progr. Probab. 56. Birkhäuser, Basel, 2003. | MR 2073433 | Zbl 1037.60018

[45] I. Pinelis. Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above. In High Dimensional Probability 33-52. IMS Lecture Notes Monogr. Ser. 51. IMS, Beachwood, OH, 2006. | MR 2387759 | Zbl 1125.60017

[46] I. Pinelis. On normal domination of (super)martingales. Electron. J. Probab. 11 (2006) 1049-1070. | MR 2268536 | Zbl 1130.60019

[47] I. Pinelis. Exact inequalities for sums of asymmetric random variables, with applications. Probab. Theory Related Fields 139 (2007) 605-635. | MR 2322709 | Zbl 1122.60021

[48] I. Pinelis. Optimal two-value zero-mean disintegration of zero-mean random variables. Electron. J. Probab. 14 (2009) 663-727. | MR 2486818 | Zbl 1193.60020

[49] G. G. Roussas. Exponential probability inequalities with some applications. In Statistics, Probability and Game Theory 303-319. IMS Lecture Notes Monogr. Ser. 30. Inst. Math. Statist., Hayward, CA, 1996. | MR 1481786

[50] G. R. Shorack and J. A. Wellner. Empirical Processes with Applications to Statistics. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York, 1986. | MR 838963 | Zbl 1170.62365

[51] M. Talagrand. The missing factor in Hoeffding's inequalities. Ann. Inst. H. Poincaré Probab. Statist. 31 (1995) 689-702. | Numdam | MR 1355613 | Zbl 0837.60016

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

[53] A. Tarski. A Decision Method for Elementary Algebra and Geometry. RAND Corporation, Santa Monica, CA, 1948. | MR 28796 | Zbl 0035.00602