On Hoeffding's inequalities

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_n\geq x}\leq cP{S_n\geq x}, where c is an absolute constant and S_n=ε_1+... +ε_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 x\in R where the survival function x\mapsto P{S_n\geq 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_n\geq 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.

Published by the Institute of Mathematical Statistics (http://www.imstat.org) in the Annals of Probability (http://www.imstat.org/aop/) at http://dx.doi.org/10.1214/009117904000000360

Cited by in corpus (23)

• Optimal Uncertainty Quantification
• Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in random environment
• Contextuality without nonlocality in a superconducting quantum system
• Clinical trial design enabling ε-optimal treatment rules
• Concentration inequalities for mean field particle models
• Exact inequalities for sums of asymmetric random variables, with applications
• (Nearly) optimal P-values for all Bell inequalities
• Device-independent randomness generation from several Bell estimators
• Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above
• Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control
• Total variation distance between stochastic polynomials and invariance principles
• Towards Machine Wald
• Witnessing Entanglement in Experiments with Correlated Noise
• Robustness of Accuracy Metric and its Inspirations in Learning with Noisy Labels
• Hoeffding's inequality for sums of weakly dependent random variables
• Exact lower bounds on the exponential moments of Winsorized and truncated random variables
• Positive-part moments via the characteristic functions, and more general expressions
• Near-Optimal Confidence Sequences for Bounded Random Variables
• Sharp large deviation probabilities for sums of independent bounded random variables
• Improved nonuniform Berry--Esseen-type bounds
• Bregman Deviations of Generic Exponential Families
• On the Exponential Probability Bounds for the Bernoulli Random Variables
• A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry