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.
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.
Keywords: probability inequalities, sums of independent random variables, martingales, supermartingales, upper bounds, generalized moments, Lévy processes, certificates of positivity, real algebraic geometry
@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}, pages = {15--27}, publisher = {Gauthier-Villars}, volume = {50}, number = {1}, year = {2014}, doi = {10.1214/12-AIHP495}, mrnumber = {3161520}, zbl = {1288.60025}, language = {en}, url = {http://archive.numdam.org/articles/10.1214/12-AIHP495/} }
TY - JOUR AU - Pinelis, Iosif TI - On the Bennett-Hoeffding inequality JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2014 SP - 15 EP - 27 VL - 50 IS - 1 PB - Gauthier-Villars UR - http://archive.numdam.org/articles/10.1214/12-AIHP495/ DO - 10.1214/12-AIHP495 LA - en ID - AIHPB_2014__50_1_15_0 ER -
Pinelis, Iosif. On the Bennett-Hoeffding inequality. Annales de l'I.H.P. Probabilités et statistiques, Volume 50 (2014) no. 1, pp. 15-27. doi : 10.1214/12-AIHP495. http://archive.numdam.org/articles/10.1214/12-AIHP495/
[1] Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc. 57 (1962) 33-45. | Zbl
.[2] A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand. Liet. Mat. Rink. 42 (2002) 332-342. | MR | Zbl
.[3] On domination of tail probabilities of (super)martingales: Explicit bounds. Liet. Mat. Rink. 46 (2006) 3-54. | MR | Zbl
, and .[4] On Hoeffding's inequalities. Ann. Probab. 32 (2004) 1650-1673. | MR | Zbl
.[5] Majorization, exponential inequalities and almost sure behavior of vector-valued random variables. Ann. Probab. 19 (1991) 1206-1226. | MR | Zbl
.[6] Convergence of Probability Measures. Wiley, New York, 1968. | MR | Zbl
.[7] The rate of convergence for multivariate sampling statistics. Ann. Statist. 21 (1993) 1692-1710. | MR | Zbl
and .[8] A sharp concentration inequality with applications. Random Structures Algorithms 16 (2000) 277-292. | MR | Zbl
, and .[9] A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris 334 (2002) 495-500. | MR | Zbl
.[10] 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 | Zbl
.[11] Problème des moments sur un compact de et décomposition de polynômes à plusieurs variables. J. Funct. Anal. 58 (1984) 254-266. | MR | Zbl
.[12] Normal approximation for nonlinear statistics using a concentration inequality approach. Bernoulli 13 (2007) 581-599. | MR | Zbl
and .[13] 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 | Zbl
, , and .[14] 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 | Zbl
.[15] A general class of exponential inequalities for martingales and ratios. Ann. Probab. 27 (1999) 537-564. | MR | Zbl
.[16] Improved Eaton bounds for linear combinations of bounded random variables, with statistical applications. J. Amer. Statist. Assoc. 88 (1993) 1026-1033. | MR | Zbl
and .[17] On Bernstein-type inequalities for martingales. Stochastic Process. Appl. 93 (2001) 109-117. | MR | Zbl
and .[18] A note on symmetric Bernoulli random variables. Ann. Math. Statist. 41 (1970) 1223-1226. | MR | Zbl
.[19] A probability inequality for linear combinations of bounded random variables. Ann. Statist. 2 (1974) 609-613. | Zbl
.[20] On tail probabilities for martingales. Ann. Probability 3 (1975) 100-118. | MR | Zbl
.[21] Probabilistic inequalities for sums of independent random variables. Teor. Verojatnost. i Primenen. 16 (1971) 660-675. | MR | Zbl
and .[22] Positive polynomials and product type actions of compact groups. Mem. Amer. Math. Soc. 54 (1985) xi+79. | MR | Zbl
.[23] Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132 (1988) 35-62. | MR | Zbl
.[24] Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963) 13-30. | MR | Zbl
.[25] Large deviations for sums of partly dependent random variables. Random Structures Algorithms 24 (2004) 234-248. | MR | Zbl
.[26] Foundations of Modern Probability, 2nd edition. Probability and Its Applications (New York). Springer, New York, 2002. | MR | Zbl
.[27] Concentration around the mean for maxima of empirical processes. Ann. Probab. 33 (2005) 1060-1077. | MR | Zbl
and .[28] Convex concentration inequalities and forward-backward stochastic calculus. Electron. J. Probab. 11 (2006) 486-512 (electronic). | MR | Zbl
, and .[29] Anneaux préordonnés. J. Analyse Math. 12 (1964) 307-326. | MR | Zbl
.[30] Quelques propriétés des préordres dans les anneaux commutatifs unitaires. C. R. Acad. Sci. Paris 258 (1964) 3417-3418. | MR | Zbl
.[31] Sur les ensembles semi-analytiques. In Actes du Congrès International des Mathématiciens (Nice, 1970) 2 237-241. Gauthier-Villars, Paris, 1971. | MR | Zbl
.[32] About the constants in Talagrand's concentration inequalities for empirical processes. Ann. Probab. 28 (2000) 863-884. | MR | Zbl
.[33] Some limit theorems for large deviations. Theory Probab. Appl. 10 (1965) 214-235. | MR | Zbl
.[34] Large deviations of sums of independent random variables. Ann. Probab. 7 (1979) 745-789. | MR | Zbl
.[35] On the Bennett-Hoeffding inequality. Preprint. Available at arXiv:0902.4058v1 [math.PR]. | Numdam | Zbl
.[36] 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].
and .[37] Remarks on inequalities for probabilities of large deviations. Theory Probab. Appl. 30 (1985) 143-148. | MR | Zbl
and .[38] Sharp exponential estimates for sums of independent random variables. Theory Probab. Appl. 34 (1989) 340-346. | MR | Zbl
and .[39] 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 | Zbl
.[40] On a majorization inequality for sums of independent random vectors. Statist. Probab. Lett. 19 (1994) 97-99. | MR | Zbl
.[41] Optimum bounds for the distributions of martingales in Banach spaces. Ann. Probab. 22 (1994) 1679-1706. | MR | Zbl
.[42] Optimal tail comparison based on comparison of moments. In High Dimensional Probability (Oberwolfach, 1996) 297-314. Progr. Probab. 43, Birkhäuser, Basel, 1998. | MR | Zbl
.[43] Fractional sums and integrals of -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 | Zbl
.[44] 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 | Zbl
.[45] 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 | Zbl
.[46] On normal domination of (super)martingales. Electron. J. Probab. 11 (2006) 1049-1070. | MR | Zbl
.[47] Exact inequalities for sums of asymmetric random variables, with applications. Probab. Theory Related Fields 139 (2007) 605-635. | MR | Zbl
.[48] Optimal two-value zero-mean disintegration of zero-mean random variables. Electron. J. Probab. 14 (2009) 663-727. | MR | Zbl
.[49] 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
.[50] Empirical Processes with Applications to Statistics. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York, 1986. | MR | Zbl
and .[51] The missing factor in Hoeffding's inequalities. Ann. Inst. H. Poincaré Probab. Statist. 31 (1995) 689-702. | Numdam | MR | Zbl
.[52] New concentration inequalities in product spaces. Invent. Math. 126 (1996) 505-563. | MR | Zbl
.[53] A Decision Method for Elementary Algebra and Geometry. RAND Corporation, Santa Monica, CA, 1948. | MR | Zbl
.Cited by Sources: