mjtsai1974's Dev Blog Welcome to mjt's AI world

Chernoff Bounds

Prologue To The Chernoff Bounds

The Chernoff bounds is essential another variation based on the Markov inequality, it derivates the exponential deviation bounds.

Chernoff Bounds

Let Z be any random variable, then for any t>0,
P(ZE[Z]+t)minλ0E[eλ(ZE[Z])]eλt=minλ0MZE[Z](λ)eλt
and
P(ZE[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:
ZE[Z]+t
eλZeλ(E[Z]+t)
Or equivalently,
ZE[Z]t
eλ(ZE[Z])eλt
➁by Markov inequality, below holds:
P(|ZE[Z]|t)
=P(eλ(ZE[Z])eλt)E[eλ(ZE[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=1Zit)ni=1E[exp(λZi)]eλt
P(ni=1Zit)(E[exp(λZ1)])neλt