Skip to main content

Advertisement

SpringerLink
Log in

An extension of the Hoeffding inequality to unbounded random variables

  • Published:
Lithuanian Mathematical Journal Aims and scope Submit manuscript

Abstract

Let S = X 1 + ⋯ + X n be a sum of independent random variables such that 0 ⩽ X k ⩽ 1 for all k. Write p = E S/n and q = 1 − p. Let 0 < t < q. In this paper, we extend the Hoeffding inequality [16, Theorem 1]

$$ \mathbb{P}\left\{ {S \geqslant nt + np} \right\} \leqslant H^n \left( {t,p} \right), {\rm H}\left( {t,p} \right) = \left( {\frac{p} {{p + t}}} \right)^{p + t} \left( {\frac{q} {{q - t}}} \right)^{q - t} , $$

, to the case where X k are unbounded positive random variables. Our inequalities reduce to the Hoeffding inequality if 0 ⩽ X k ⩽ 1. Our conditions are X k ⩾ 0 and E S < ∞. We also provide improvements comparable with the inequalities of Bentkus [5]. The independence of X k can be replaced by supermartingale-type assumptions. Our methods can be extended to prove counterparts of other inequalities of Hoeffding [16] and Bentkus [5].

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. V. Bentkus, An inequality for large deviation probabilities of sums of bounded i.i.d. random variables, Lith. Math. J., 41(2):112–119, 2001.

    Article  MATH  MathSciNet  Google Scholar 

  2. V. Bentkus, An inequality for tail probabilities of martingales with bounded differences, Lith. Math. J., 42(3):255–261, 2002.

    Article  MATH  MathSciNet  Google Scholar 

  3. V. Bentkus, A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand, Lith. Math. J., 42(3):262–269, 2002.

    Article  MATH  MathSciNet  Google Scholar 

  4. V. Bentkus, An inequality for tail probabilities of martingales with differences bounded from one side, J. Theor. Probab., 16(1):161–173, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  5. V. Bentkus, On Hoeffding’s inequalities, Ann. Probab., 32(2):1650–1673, 2004.

    Article  MATH  MathSciNet  Google Scholar 

  6. V. Bentkus, On measure concentration for separately Lipschitz functions in product spaces, Israel. J. Math., 158:1–17, 2007.

    Article  MATH  MathSciNet  Google Scholar 

  7. V. Bentkus, G.D.C. Geuze, M.G.F. Pinenberg, and M. van Zuijlen, Unimodality: The symmetric case, Report No. 0612 of Dept. of Math. Radboud University Nijmegen, pp. 1–12, 2006.

  8. V. Bentkus, G.D.C. Geuze, and M. van Zuijlen, Optimal Hoeffding-like inequalities under a symmetry assumption, Statistics, 40(2):159–164, 2006.

    MATH  MathSciNet  Google Scholar 

  9. V. Bentkus, G.D.C. Geuze, and M. van Zuijlen, Unimodality: The General Case, Report No. 0608 of Dept. of Math. Radboud University Nijmegen, 2006.

  10. V. Bentkus, G.D.C. Geuze, and M. van Zuijlen, Unimodality: The Linear Case, Report No. 0607 of Dept. of Math. Radboud University Nijmegen, 2006, 1–11.

  11. V. Bentkus, N. Kalosha, and M. van Zuijlen, On domination of tail probabilities of (super)martingales: explicit bounds, Lith. Math. J., 46(1):1–43, 2006.

    Article  MATH  Google Scholar 

  12. V. Bentkus, N. Kalosha, and M. van Zuijlen, Confidence bounds for the mean in nonparametric multisample problems, Stat. Neerlandica, 61(2):209–231, 2007.

    Article  MATH  Google Scholar 

  13. V. Bentkus and M. van Zuijlen, On conservative confidence intervals, Lith. Math. J., 43(2):141–160, 2003.

    Article  MATH  Google Scholar 

  14. van de S. A. Geer, On Hoeffding’s inequalities for dependent random variables, Empirical Process Techniques for Dependent Data, Birkhauser Boston, MA, Contemp. Math., 234:161–169, 2002. Am. Math. Soc., Providence, RI.

    Google Scholar 

  15. A. Godbole and P. Hitczenko, Beyond the method of bounded differences, Microsurveys in Discrete Probability (Princeton, NJ, 1997), 41:43–58, 1998.

    MathSciNet  Google Scholar 

  16. W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58:13–30, 1963.

    Article  MATH  MathSciNet  Google Scholar 

  17. N. Laib, Exponential-type inequalities for martingale difference sequences. application to nonparametric regression estimation, Commun. Stat. Theory Methods, 28:1565–1576, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  18. C. McDiarmid, On the method of bounded differences, Surveys in Combinatorics (Norwich 1989), London Math. Soc. Lecture Note Ser., 141:148–188, 1989.

  19. F. Perron, Extremal properties of sums of Bernoulli random variables, Stat. Probab. Lett., 62:345–354, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  20. I. Pinelis, Optimal tail comparison based on comparison of moments, High Dimensional Probability (Oberwolfach, 1996), Progr. Probab., 43:297–314, 1998.

  21. I. Pinelis, Fractional sums and integrals of r-concave tails and applications to comparison probability inequalities, Advances in Stochastic Inequalities (Atlanta, GA, 1997), Contemp. Math., 234:149–168, 1999. Am. Math. Soc., Providence, RI.

    Google Scholar 

  22. I. Pinelis, On normal domination of (super)martingales, Electron. J. Prabab, 11(39):1049–1070, 2006.

    MATH  MathSciNet  Google Scholar 

  23. I. Pinelis, Inequalities for sums of asymmetric random variables, with applications, Probab. Theory Related Fields, 139(3–4):605–635, 2007.

    Article  MATH  MathSciNet  Google Scholar 

  24. I. Pinelis, Toward the best constant factor for the Rademacher-Gaussian tail comparison, ESAIM Probab. Stat., 11:412–426, 2007.

    Article  MATH  MathSciNet  Google Scholar 

  25. M. Talagrand, The missing factor in Hoeffding’s inequalities, Ann. Inst. H. Poincaré Probab. Stat., 31(4):689–702, 1995.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics and Informatics, Akademijos 4, LT-08663, Vilnius, Lithuania

    V. Bentkus

Authors
  1. V. Bentkus
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Bentkus.

Additional information

The research was partially supported by the Lithuanian State Science and Studies Foundation, grant No T-25/08.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bentkus, V. An extension of the Hoeffding inequality to unbounded random variables. Lith Math J 48, 137–157 (2008). https://doi.org/10.1007/s10986-008-9007-7

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10986-008-9007-7

Keywords

Search

Navigation