HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

"Practical forms" of Chernoff bound for inequality in expectation

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#41839, answer score: 2

Revisions (0)

No revisions yet.