Two refinements of the Chernoff bound for the sum of nonidentical Bernoulli random variables

摘要

We give two refinements to the Chernoff bound for the sum of nonidentical Bernoulli random variables with parameters p(i), where 0 < p(i) < 1 and i = 1, ... , n. Traditionally, the Chernoff bound is a function of the arithmetic mean of the p(i)'s, n(-1) Sigma(n)(i=1) p(i). The refined bounds contain the term n(-1) Sigma(n)(i=1) p(i)(2), and hence, are able to capture the variations of p(i)'s.