Suppose X1, X2, ..., Xn are independent random variables with P( Xi = 1 ) = pi and P( Xi = 0 ) = 1 - pi, and X = X1 + X2 + ... + Xn. Let M = E[X] = p1 + p2 + ... + pn. Then for any d between 0 and 1 we have

P( X >= (1+d)M ) <= exp( -Md2/3 )

proof: Using Markov's inequality

P( X >= (1+d)M ) = P( exp( tX) >= exp( t(1+d)M ) <= E[ exp(tX) ]/exp( t(1+d)M )
Since the components of X are independent, the numerator can be written as a product of terms

E[ exp(tXi) = piexp(t) + (1 - pi) = 1 + pi(exp(t) - 1) <= exp( pi(exp(t) - 1) )

so the numerator is at most exp( M(exp(t) - 1) ). If we set t = ln(1 + d) in the numerator and denominator, we get

( exp(d)/(1 + d)(1+d) )M

We need to show that the quantity in parentheses is at most exp( -d2/3 ). Taking logarithms, this is equivalent to (1 + d) ln(1 + d) - d - d2/3 being non-negative. The first derivative of this is ln(1 + d) - 2d/3 and the second derivative is 1/(1 + d) - 2/3. The second derivative is positive up to 1/2 and negative after, and the first derivative is 0 at 0 and positive at 1, so it must be positive between 0 and 1. The quantity in question is 0 at 0 and has a positive derivative, so it is non-negative between 0 and 1.