On the Bennett–Hoeffding inequality

Iosif Pinelis

Annales de l'I.H.P. Probabilités et statistiques (2014)

  • Volume: 50, Issue: 1, page 15-27
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Pinelis, Iosif. "On the Bennett–Hoeffding inequality." Annales de l'I.H.P. Probabilités et statistiques 50.1 (2014): 15-27. <http://eudml.org/doc/271996>.

@article{Pinelis2014,
abstract = {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.},
author = {Pinelis, Iosif},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {probability inequalities; sums of independent random variables; martingales; supermartingales; upper bounds; generalized moments; Lévy processes; certificates of positivity; real algebraic geometry},
language = {eng},
number = {1},
pages = {15-27},
publisher = {Gauthier-Villars},
title = {On the Bennett–Hoeffding inequality},
url = {http://eudml.org/doc/271996},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Pinelis, Iosif
TI - On the Bennett–Hoeffding inequality
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2014
PB - Gauthier-Villars
VL - 50
IS - 1
SP - 15
EP - 27
AB - 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 - eng
KW - probability inequalities; sums of independent random variables; martingales; supermartingales; upper bounds; generalized moments; Lévy processes; certificates of positivity; real algebraic geometry
UR - http://eudml.org/doc/271996
ER -

References

top
  1. [1] G. Bennett. Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc.57 (1962) 33–45. Zbl0104.11905
  2. [2] V. Bentkus. A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand. Liet. Mat. Rink. 42 (2002) 332–342. Zbl1021.60012MR1947624
  3. [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. Zbl1138.60020MR2251440
  4. [4] V. Bentkus. On Hoeffding’s inequalities. Ann. Probab.32 (2004) 1650–1673. Zbl1062.60011MR2060313
  5. [5] E. Berger. Majorization, exponential inequalities and almost sure behavior of vector-valued random variables. Ann. Probab.19 (1991) 1206–1226. Zbl0757.60002MR1112413
  6. [6] P. Billingsley. Convergence of Probability Measures. Wiley, New York, 1968. Zbl0944.60003MR233396
  7. [7] E. Bolthausen and F. Götze. The rate of convergence for multivariate sampling statistics. Ann. Statist.21 (1993) 1692–1710. Zbl0798.62023MR1245764
  8. [8] S. Boucheron, G. Lugosi and P. Massart. A sharp concentration inequality with applications. Random Structures Algorithms16 (2000) 277–292. Zbl0954.60008MR1749290
  9. [9] O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris334 (2002) 495–500. Zbl1001.60021MR1890640
  10. [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. Zbl1037.60015MR2073435
  11. [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. Zbl0556.44006MR759099
  12. [12] L. H. Y. Chen and Q.-M. Shao. Normal approximation for nonlinear statistics using a concentration inequality approach. Bernoulli13 (2007) 581–599. Zbl1146.62310MR2331265
  13. [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. Zbl0944.60032MR1782937
  14. [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. Zbl0900.03055MR1634190
  15. [15] V. H. de la Peña. A general class of exponential inequalities for martingales and ratios. Ann. Probab.27 (1999) 537–564. Zbl0942.60004MR1681153
  16. [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. Zbl0792.62041MR1242946
  17. [17] K. Dzhaparidze and J. H. van Zanten. On Bernstein-type inequalities for martingales. Stochastic Process. Appl.93 (2001) 109–117. Zbl1051.60022MR1819486
  18. [18] M. L. Eaton. A note on symmetric Bernoulli random variables. Ann. Math. Statist.41 (1970) 1223–1226. Zbl0203.51805MR268930
  19. [19] M. L. Eaton. A probability inequality for linear combinations of bounded random variables. Ann. Statist.2 (1974) 609–613. Zbl0282.62012
  20. [20] D. A. Freedman. On tail probabilities for martingales. Ann. Probability3 (1975) 100–118. Zbl0313.60037MR380971
  21. [21] D. H. Fuk and S. V. Nagaev. Probabilistic inequalities for sums of independent random variables. Teor. Verojatnost. i Primenen.16 (1971) 660–675. Zbl0259.60024MR293695
  22. [22] D. Handelman. Positive polynomials and product type actions of compact groups. Mem. Amer. Math. Soc. 54 (1985) xi+79. Zbl0571.46045MR783217
  23. [23] D. Handelman. Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math.132 (1988) 35–62. Zbl0659.52002MR929582
  24. [24] W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc.58 (1963) 13–30. Zbl0127.10602MR144363
  25. [25] S. Janson. Large deviations for sums of partly dependent random variables. Random Structures Algorithms24 (2004) 234–248. Zbl1044.60021MR2068873
  26. [26] O. Kallenberg. Foundations of Modern Probability, 2nd edition. Probability and Its Applications (New York). Springer, New York, 2002. Zbl0892.60001MR1876169
  27. [27] T. Klein and E. Rio. Concentration around the mean for maxima of empirical processes. Ann. Probab.33 (2005) 1060–1077. Zbl1066.60023MR2135312
  28. [28] T. Klein, Y. Ma and N. Privault. Convex concentration inequalities and forward-backward stochastic calculus. Electron. J. Probab. 11 (2006) 486–512 (electronic). Zbl1112.60034MR2242653
  29. [29] J.-L. Krivine. Anneaux préordonnés. J. Analyse Math.12 (1964) 307–326. Zbl0134.03902MR175937
  30. [30] J.-L. Krivine. Quelques propriétés des préordres dans les anneaux commutatifs unitaires. C. R. Acad. Sci. Paris258 (1964) 3417–3418. Zbl0119.03602MR169083
  31. [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. Zbl0241.32005MR425152
  32. [32] P. Massart. About the constants in Talagrand’s concentration inequalities for empirical processes. Ann. Probab.28 (2000) 863–884. Zbl1140.60310MR1782276
  33. [33] S. V. Nagaev. Some limit theorems for large deviations. Theory Probab. Appl.10 (1965) 214–235. Zbl0144.18704MR185644
  34. [34] S. V. Nagaev. Large deviations of sums of independent random variables. Ann. Probab.7 (1979) 745–789. Zbl0418.60033MR542129
  35. [35] I. Pinelis. On the Bennett–Hoeffding inequality. Preprint. Available at arXiv:0902.4058v1 [math.PR]. Zbl1288.60025
  36. [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. [37] I. F. Pinelis and A. I. Sakhanenko. Remarks on inequalities for probabilities of large deviations. Theory Probab. Appl.30 (1985) 143–148. Zbl0583.60023MR779438
  38. [38] I. S. Pinelis and S. A. Utev. Sharp exponential estimates for sums of independent random variables. Theory Probab. Appl.34 (1989) 340–346. Zbl0693.60036MR1005745
  39. [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. Zbl0793.60016MR1227615
  40. [40] I. Pinelis. On a majorization inequality for sums of independent random vectors. Statist. Probab. Lett.19 (1994) 97–99. Zbl0801.60010MR1256696
  41. [41] I. Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. Ann. Probab.22 (1994) 1679–1706. Zbl0836.60015MR1331198
  42. [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. Zbl0906.60014MR1652335
  43. [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. Zbl0937.60011MR1694770
  44. [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. Zbl1037.60018MR2073433
  45. [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. Zbl1125.60017MR2387759
  46. [46] I. Pinelis. On normal domination of (super)martingales. Electron. J. Probab.11 (2006) 1049–1070. Zbl1130.60019MR2268536
  47. [47] I. Pinelis. Exact inequalities for sums of asymmetric random variables, with applications. Probab. Theory Related Fields139 (2007) 605–635. Zbl1122.60021MR2322709
  48. [48] I. Pinelis. Optimal two-value zero-mean disintegration of zero-mean random variables. Electron. J. Probab.14 (2009) 663–727. Zbl1193.60020MR2486818
  49. [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. MR1481786
  50. [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. Zbl1170.62365MR838963
  51. [51] M. Talagrand. The missing factor in Hoeffding’s inequalities. Ann. Inst. H. Poincaré Probab. Statist.31 (1995) 689–702. Zbl0837.60016MR1355613
  52. [52] M. Talagrand. New concentration inequalities in product spaces. Invent. Math.126 (1996) 505–563. Zbl0893.60001MR1419006
  53. [53] A. Tarski. A Decision Method for Elementary Algebra and Geometry. RAND Corporation, Santa Monica, CA, 1948. Zbl0035.00602MR28796

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.