On Hoeffding's inequalities

• 成果类型: Article
• 署名作者: Bentkus, V
• 署名单位: Vilnius University; Vytautas Magnus University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/009117904000000360
• 发表日期: 2004
• 页码: 1650-1673
• 关键词: successes; number

摘要

In a celebrated work by Hoeffding [J. Amer Statist. Assoc. 58 (1963) 13-30], several inequalities for tail probabilities of sums Mn = 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 greater than or equal to x} less than or equal to cP{S-n greater than or equal to 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 X E R where the survival function x --> P{S-n greater than or equal to 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 greater than or equal to 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.