Chernoff Bounds
01 Mar 2018Prologue To The Chernoff Bounds
Chernoff Bounds
Let Z be any random variable, then for any t>0,
P(Z≥E[Z]+t)≤minλ≥0E[eλ⋅(Z−E[Z])]⋅e−λ⋅t=minλ≥0MZ−E[Z](λ)⋅e−λ⋅t
and
P(Z≤E[Z]−t)≤minλ≥0E[eλ⋅(E[Z]−Z)]⋅e−λ⋅t=minλ≥0ME[Z]−Z(λ)⋅e−λ⋅t
; where MZ(λ)=E[exp(λ⋅Z)] is the moment generating function of Z.Proof:
➀for any λ>0, we have:
Z≥E[Z]+t
⇔eλ⋅Z≥eλ⋅(E[Z]+t)
Or equivalently,
Z−E[Z]≥t
⇔eλ⋅(Z−E[Z])≥eλ⋅t
➁by Markov inequality, below holds:
P(|Z−E[Z]|≥t)
=P(eλ⋅(Z−E[Z])≥eλ⋅t)≤E[eλ⋅(Z−E[Z])]⋅e−λ⋅t
➂the second inequality could be proved in the similar way.To be believed that a reasonable upper bound could be built by choosing appropriate λ.
Chernoff Bounds Extension
We can further extend Chernoff bounds with summation of multiple random varaibles.
➀suppose that all Zi’s are independent and zero meanfor all i, then we have it that:
MZ1+…+Zn=∏ni=1MZi(λ)
, which is a consequence of the moment generating function, because the independence of each Zi.
E[exp(λ⋅∑ni=1Zi)]
=E[∏ni=1exp(λ⋅Zi)]
=∏ni=1E[exp(λ⋅Zi)]
➁by Chernoff inequality, for any λ>0,
P(∑ni=1Zi≥t)≤∏ni=1E[exp(λ⋅Zi)]⋅e−λ⋅t
⇔P(∑ni=1Zi≥t)≤(E[exp(λ⋅Z1)])n⋅e−λ⋅t