patternMinor
"Practical forms" of Chernoff bound for inequality in expectation
Viewed 0 times
formsboundexpectationforpracticalinequalitychernoff
Problem
From Wikipedia:
The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:
(i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0<\delta<1$
(ii) $Pr(X\leq (1-\delta)\mu)\leq e^{-\frac{\delta^2\mu}{2}}, 0<\delta<1$
The assumption they use is $E[X]=\mu$.
Would (i) still hold if we only assume $E[X]\leq \mu$? Would (ii) still hold if we only assume $E[X]\geq\mu$?
If not, what "practical forms" do we have in these cases?
The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:
(i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0<\delta<1$
(ii) $Pr(X\leq (1-\delta)\mu)\leq e^{-\frac{\delta^2\mu}{2}}, 0<\delta<1$
The assumption they use is $E[X]=\mu$.
Would (i) still hold if we only assume $E[X]\leq \mu$? Would (ii) still hold if we only assume $E[X]\geq\mu$?
If not, what "practical forms" do we have in these cases?
Solution
It is more practical just because it has
the advantage of being easier to state and compute with in many situations (quoted from [1]).
I am not sure whether (i) still holds for $\mu' = E[X] \le \mu$. At least, we cannot obtain that directly from the following computation:
$$Pr[X \ge (1 + \delta) \mu] \le Pr[X \ge (1 + \delta) \mu'] \le e^{-\frac{\delta^2 \mu'}{3}} \ge e^{-\frac{\delta^2 \mu}{3}}$$
[1] Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.
the advantage of being easier to state and compute with in many situations (quoted from [1]).
I am not sure whether (i) still holds for $\mu' = E[X] \le \mu$. At least, we cannot obtain that directly from the following computation:
$$Pr[X \ge (1 + \delta) \mu] \le Pr[X \ge (1 + \delta) \mu'] \le e^{-\frac{\delta^2 \mu'}{3}} \ge e^{-\frac{\delta^2 \mu}{3}}$$
[1] Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.
Context
StackExchange Computer Science Q#41839, answer score: 2
Revisions (0)
No revisions yet.