On the Bennett-Hoeffding inequality

Pinelis, Iosif

Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) no. 1, pp. 15-27.

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.

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

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

[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 | Zbl

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

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

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

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

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

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

[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

[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 | Zbl

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

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

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