Skip to main content
Commonmark migration
Source Link

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?

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?

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?

Tweeted twitter.com/#!/StackCompSci/status/592347609857163264
Source Link
mba
  • 385
  • 1
  • 2
  • 6

"Practical forms" of Chernoff bound for inequality in expectation

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?