Chernoff Bounds For Bernoulli Random Variable
09 Dec 2019Prologue To The Chernoff Bounds For Bernoulli Random Variable
The Error Probability After Test
Let Xi to be a Bernoulli random variable for i={1,2,…,n}
➀Xi=1 with probability pi
➁Xi=0 with probability 1-pi
, where all Xis are I.I.D and suppose at least one of the pi is non-zero.We are testing with a hope that we can make our target value meet the expectation level after some amount of trials. To express the target value we want in terms of expect value, we let X=∑ni=1Xi, E[X]=μ=∑ni=1pi.
[Question]How confident we are in the final outcome by the random variable X? It is asking you 2 kinds of questions:
➀the range of the confidence interval
➁the error probability for the target value X above or below the expect value μThe follwing section would guide you through the process to build the upper and lower bound of such error probability in Chernoff exponential decreasing form.
[Notes] Even if our proof of ➁ holds, the range of confidence interval must be guaranteed by the native design in your experiment.
The Upper Bound On Error Probability
It is asking the error probability when target value X is greater than the expect value μ, and we’d like to bound it on the upper side.
P(X>(1+δ)⋅μ), for δ>0
=P(et⋅X>et⋅(1+δ)⋅μ), for all t>0
≤E[et⋅X]et⋅(1+δ)⋅μ…Markov inequalitySince each Xi is independent, we have
E[et⋅X]
=E[et⋅∑ni=1Xi]
=E[et⋅(X1+X2+…+Xn)]
=E[∏ni=1et⋅Xi]
=∏ni=1E[et⋅Xi]
=∏ni=1et⋅1⋅pi+et⋅0⋅(1−pi)
=∏ni=1et⋅pi+1⋅(1−pi)
=∏ni=11+(et−1)⋅piBecause 1+X<eX for all X>0, we have
E[et⋅X]
=∏ni=11+(et−1)⋅pi
<∏ni=1e(et−1)⋅pi
=e(et−1)⋅(p1+…+pn)
=e(et−1)⋅μTherefore, we have
P(X>(1+δ)⋅μ)
≤E[et⋅X]et⋅(1+δ)⋅μ
<e(et−1)⋅μet⋅(1+δ)⋅μ
=e((et−1)−t⋅(1+δ))⋅μ…➀Next would be to figure out the minimum of e((et−1)−t⋅(1+δ))⋅μ by taking its first derivative with respect to t, set it to zero, get such value of t to make it zero:
de((et−1)−t⋅(1+δ))⋅μdt
=[et−(1+δ)]⋅μ⋅e[(et−1)−(1+δ)⋅t]⋅μThe right side of exponential part won’t be zero, then
[et−(1+δ)]⋅μ=0
⇒et−(1+δ)=0
⇒t=ln(1+δ) could we have the minimum valueTake t=ln(1+δ) into ➀, we get:
P(X>(1+δ)⋅μ)<[eδ(1+δ)(1+δ)]μ…[A]
As a result, (eln(1+δ))(1+δ)⋅μ=(1+δ)(1+δ)⋅μ
The Lower Bound On Error Probability
It is asking the error probability when target value X is less than the expect value μ, and we’d like to bound it on the lower side.
P(X<(1−δ)⋅μ), for δ>0
=P(−X>−(1−δ)⋅μ)
=P(et⋅(−X)>et⋅(−(1−δ))⋅μ), for all t>0
≤E[et⋅(−X)]et⋅(−(1−δ))⋅μ)…Markov inequalityVia similar approach, we could have
P(X<(1−δ)⋅μ)<[e−δ(1−δ)(1−δ)]μ…[B]
Bounding The Bounds
We now have 2 bounds in [A] and [B], such bounds [eδ(1+δ)(1+δ)]μ and [e−δ(1−δ)(1−δ)]μ are difficult to use, we should turn it into human readable format.
The nominator is the exponential raised to the power of δ, take upper bound [eδ(1+δ)(1+δ)]μ for illustration, we’d like to turn (1+δ)(1+δ) into exponential powered base expression, to be believed the most efficient way.
[1] The upper boundBegin from the the natural logarithm of 1+δ, that is ln(1+δ)=y, then ey=1+δ, we can just express (1+δ)(1+δ) as (ey)(1+δ), the very next thing would be to figure out ln(1+δ) in the expression of approximation.
Since dln(1+δ)dδ=11+δ, the ln(1+δ) begins from integration:
ln(1+δ)
=∫1011+δdδ
=∫10(1−δ+δ2−δ3+δ4−…)dδ
=δ-δ22!+δ33!-δ44!+…
=∑∞1(−1)k−1⋅δkk!This δ is quiet small, temporarily forget about it after the power of 3, then we have
(1+δ)(1+δ)>(eδ−δ22!+δ33!)(1+δ)
≈eδ+δ22−δ36
≈eδ+δ22+εTherefore, the upper bound in [A] becomes:
P(X>(1+δ)⋅μ)<[eδ(1+δ)(1+δ)]μ
⇒P(X>(1+δ)⋅μ)<[eδeδ+δ22+ε]μ
⇒P(X>(1+δ)⋅μ)<e−δ22+ε⋅μTo be more narrow down, the choice of e−δ23⋅μ won’t violect, for ε→0:
[2] The lower bound
⇒P(X>(1+δ)⋅μ)<e−δ23⋅μ
ln(1−δ)
=ln(1+(−δ))
=∑∞1(−1)k−1⋅(−δ)kk!Thus, we have it that
ln(1−δ)=−δ−δ22!−δ33!−δ44!−…
⇒ln(1−δ)>−δ−δ22!
⇒(1−δ)>e−δ−δ22!
⇒(1−δ)(1−δ)>(e−δ−δ22!)(1−δ)
⇒(1−δ)(1−δ)>e−δ+δ22+δ32
⇒(1−δ)(1−δ)>e−δ+δ22, where we ignore the term δ32Therefore, we have the lower bound
P(X<(1−δ)⋅μ)<[e−δ(1−δ)(1−δ)]μ
⇒P(X<(1−δ)⋅μ)<[e−δe−δ+δ22]μ
⇒P(X<(1−δ)⋅μ)<e−δ22⋅μ