質問

This question: Chernoff bound when we only have upper bound of expectation is similar, but for an upper bound of expectation.

The standard Chernoff bound says that is $X$ is a sum of 0/1 random variables, then, for any $\delta \in (0,1)$,

$P(X \leq (1-\delta) E(X)) \leq e^{-\frac{\delta^2 E(X)}{2}}$.

Suppose we only have $\alpha \leq E(X)$. Is it true, and if so, how to prove, that

for any $\delta \in (0,1)$,

$P(X \leq (1- \delta) \alpha) \leq e^{-\frac{\delta^2 \alpha}{2}}$.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top