P( X >= (1+d)M ) <= exp( -Md^{2}/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(tX_{i}) = p_{i}exp(t) + (1 - p_{i}) =
1 + p_{i}(exp(t) - 1) <= exp( p_{i}(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( -d^{2}/3 ). Taking logarithms, this is equivalent to
(1 + d) ln(1 + d) - d - d^{2}/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.