We consider extensions of Hoeffding's " exponential method " approach for obtaining upper estimates on the probability that a sum of independent and bounded random variables is significantly larger than its mean. We show that the exponential function in Hoeffding's approach can be replaced with any function which is non-negative, increasing and convex. As a result we generalize and improve upon Hoeffding's inequality. Our approach allows to obtain " missing factors " in Hoeffding's inequality. The later result is a rather weaker version of a theorem that is due to Michel Talagrand. Moreover, we characterize the class of functions with respect to which our method yields optimal concentration bounds. Finally, using ideas from the theory of Bernstein polynomials, we show that similar ideas apply under information on higher moments of the random variables.
See @cite_26 for a proof of this theorem and for a precise definition of the function @math . In other words, Talagrand's result improves upon Hoeffding's by inserting a "missing" factor of order @math in the Hoeffding bound. Notice that Talagrand's result holds true for @math , for some absolute constant @math whose value does seem to be known. Talagrand (see @cite_26 , page 692) mentions that one can obtain a rather small numerical value for @math , but numerical computations are left to others with the talent for it. One of the purposes of this paper is to improve upon Hoeffding's inequality by obtaining "missing" factors with exact numerical values for the constants. Part of Bentkus' paper performs comparisons between @math and tails of binomial and Poisson random variables. A crucial idea in the results of @cite_25 is to compare @math with means of particular functions of certain random variables. In particular, in the proof of Theorem @math in @cite_25 one can find the following result.
@cite_26 @cite_25
2479913478 2037982184
Un article celebre d'Hoeffding etablit des bornes pour la deviation d'une somme de variables aleatoires independantes par rapport a sa moyenne. Combinant la methode d'Hoeffding avec la transformation d'Esscher, on montre comment sous des hypotheses supplementaires minimes ces bornes peuvent etre ameliorees d'une facon essentiellement optimale. 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 ≥ x ≤ cP S n ≥ x , where c is an absolute constant and S n = e 1 + ... + e 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 ∈ Ρ where the survival function x → P S n ≥ 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 ≥ 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. The inequalities have applications to measure concentration, leading to results of the type where, up to an absolute constant, the measure concentration is dominated by the concentration in a simplest appropriate model, such results will be considered elsewhere.