On Hoeffding's inequalities.

DOI10.1214/009117904000000360zbMATH Open1062.60011arXivmath/0410159OpenAlexW2037982184MaRDI QIDQ1879841FDOQ1879841

Authors: Vidmantas Bentkus 

Publication date: 15 September 2004

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: In a celebrated work by Hoeffding [J. Amer. Statist. Assoc. 58 (1963) 13-30], several inequalities for tail probabilities of sums M_n=X_1+... +X_n of bounded independent random variables X_j were proved. These inequalities had a considerable impact on the development of probability and statistics, and remained unimproved until 1995 when Talagrand [Inst. Hautes Etudes Sci. Publ. Math. 81 (1995a) 73-205] inserted certain missing factors in the bounds of two theorems. By similar factors, a third theorem was refined by Pinelis [Progress in Probability 43 (1998) 257-314] and refined (and extended) by me. In this article, I introduce a new type of inequality. Namely, I show that P{M_ngeq x}leq cP{S_ngeq x}, where c is an absolute constant and S_n=epsilon_1+... +epsilon_n is a sum of independent identically distributed Bernoulli random variables (a random variable is called Bernoulli if it assumes at most two values). The inequality holds for those xin R where the survival function xmapsto P{S_ngeq x} has a jump down. For the remaining x the inequality still holds provided that the function between the adjacent jump points is interpolated linearly or log-linearly. If it is necessary, to estimate P{S_ngeq x} special bounds can be used for binomial probabilities. The results extend to martingales with bounded differences. It is apparent that Theorem 1.1 of this article is the most important.

Full work available at URL: https://arxiv.org/abs/math/0410159

Recommendations

• An extension of the Hoeffding inequality to unbounded random variables
• Addendum to ``An extension of an inequality of Hoeffding to unbounded random variables: The non-i.i.d. case
• An inequality for the sum of independent bounded random variables
• An inequality for tail probabilities of martingales with bounded differences
• On inequalities for sums of bounded random variables

zbMATH Keywords

martingaleinequalitiesbounds for tail probabilitiesHoeffding's inequalitiesprobabilities of large deviationsbounded differences and random variables

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15)

Cites Work

• On the distribution of the number of successes in independent trials
• On the Distribution of the Number of Successes in Independent Trials
• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Inequalities: theory of majorization and its applications
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Extremal probabilistic problems and Hotelling's \(T^ 2\) test under a symmetry condition
• Concentration of measure and isoperimetric inequalities in product spaces
• Title not available (Why is that?)
• A Note on Symmetric Bernoulli Random Variables
• A Topological Application of the Isoperimetric Inequality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The missing factor in Hoeffding's inequalities
• Some Results for Discrete Unimodality
• Title not available (Why is that?)
• Sur quelques applications des fonctions convexes et concaves au sens de I. Schur
• A probability inequality for linear combinations of bounded random variables
• On the asymptotical behavior of the constant in the Berry-Esseen inequality
• An inequality for tail probabilities of martingales with differences bounded from one side
• Title not available (Why is that?)
• Title not available (Why is that?)
• On conservative confidence intervals
• Estimates of the proximity of a distribution to the normal law
• An inequality for large deviation probabilities of sums of bounded i. i. d. random variables
• On measure concentration for separately Lipschitz functions in product spaces
• Some comments on deviation inequalities for infinitely divisible random vectors
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (69)

• An improved Hoeffding’s inequality of closed form using refinements of the arithmetic mean-geometric mean inequality
• Characterizations of \(B\)-valued concentration inequalities via the Rademacher type
• Locally simultaneous inference
• Improving Hoeffding's inequality using higher moments information
• Hoeffding and Bernstein inequalities for weighted sums of exchangeable random variables
• Extended acceptable random variables and Hoeffding inequalities
• On large deviations for sums of i.i.d. Bernoulli random variables
• An inequality for tail probabilities of martingales with bounded differences
• Exponential inequalities for bounded random variables
• Sharp large deviation results for sums of independent random variables
• Extensions of the Hoeffding-Azuma inequalities
• On Hoeffding and Bernstein type inequalities for sums of random variables in non-additive measure spaces and complete convergence
• Title not available (Why is that?)
• Comparison inequalities for suprema of bounded empirical processes
• Parallel bootstrap and optimal subsample lengths in smooth function models
• Title not available (Why is that?)
• On Bernstein type inequalities for stochastic integrals of multivariate point processes
• A Hoeffding inequality for Markov chains using a generalized inverse
• On extensions of Hoeffding's inequality for panel data
• The KLS isoperimetric conjecture for generalized Orlicz balls
• Positive-part moments via characteristic functions, and more general expressions
• Probability inequalities for bounded random vectors
• An extension of the Hoeffding inequality to unbounded random variables
• The moderate deviation principle for self-normalized sums of sums of i.i.d. random variables
• Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment
• A multivariate version of Hoeffding's inequality
• Concentration inequalities for sums and martingales
• The missing factor in Hoeffding's inequalities
• Inequalities for sums of random variables in noncommutative probability spaces
• Positive-part moments via the Fourier-Laplace transform
• Finite-sample exact tests for linear regressions with bounded dependent variables
• Total variation distance between stochastic polynomials and invariance principles
• Hoeffding's inequality for supermartingales
• New deviation inequalities for martingales with bounded increments
• On the Bernstein-Hoeffding method
• Exact lower bounds on the exponential moments of truncated random variables
• Addendum to ``An extension of an inequality of Hoeffding to unbounded random variables: The non-i.i.d. case
• Concentration inequalities for mean field particle models
• Stable polynomials and sums of dependent Bernoulli random variables: application to Hoeffding inequalities
• On domination of tail probabilities of (super)martingales: explicit bounds
• About the rate function in concentration inequalities for suprema of bounded empirical processes
• Inferring probability densities from expert opinion
• Asymptotic expansions and strategies in the online increasing subsequence problem
• A refinement of Hoeffding's inequality
• A Note on Hoeffding's Inequality
• Concentration inequalities for separately convex functions
• Rigorous error control methods for estimating means of bounded random variables
• Exact inequalities for sums of asymmetric random variables, with applications
• Bounds for tail probabilities of the sample variance
• Characteristic function of the positive part of a random variable and related results, with applications
• On the Bennett-Hoeffding inequality
• Hoeffding's inequalities: A counterexample
• On inequalities for sums of bounded random variables
• A maximal 𝕃_{𝕡}-inequality for stationary sequences and its applications
• Title not available (Why is that?)
• An inequality for the sum of independent bounded random variables
• Theorems on large deviations for randomly indexed sum of weighted random variables
• Hoeffding's inequality for sums of dependent random variables
• On measure concentration for separately Lipschitz functions in product spaces
• Toward the best constant factor for the Rademacher-Gaussian tail comparison
• Title not available (Why is that?)
• On Bayes equality and related issues
• Concentration inequalities for suprema of unbounded empirical processes
• PENELOPE MADDY. Defending the Axioms: On the Philosophical Foundations of Set Theory. Oxford: Oxford University Press, 2011. ISBN 978-0-19-959618-8 (hbk); 978-0-19-967148-9 (pbk). Pp. x + 150
• Title not available (Why is that?)
• Convergence in distribution norms in the CLT for non identical distributed random variables
• Bounds for tail probabilities of martingales using skewness and kurtosis
• Concentration inequalities via zero bias couplings
• Sharp large deviations for sums of bounded from above random variables

This page was built for publication: On Hoeffding's inequalities.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879841)