# 当我们只有少的延期界限时绑定 -- probability-theory 领域 和 chernoff-bounds 领域 cs 相关 的问题

## Chernoff bound when we only have a lower bound of expecation

4

### 问题

$p（x leq（1- delta）e（x）） leq e ^ { - frac { delta ^ 2 e（x）} {2}}$。

$p（x leq（1- delta） alpha） leq e ^ { - frac { delta ^ 2 alpha} {2}}$。

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}}$.

## 回答列表

2

You can use a coupling. Let $X = X_1,\ldots,X_n$, and suppose that $\Pr[X_i=1] = \beta_i$ (so $\beta := \mathbb{E}[X] = \sum_i \beta_i \geq \alpha$). Let $p = \alpha/\beta$, and define $\alpha_i = p\beta_i$. Let $Z_i \sim \mathrm{Bernoulli}(p)$, and define $Y_i = X_i Z_i$. Notice that $X_i \geq Y_i$ and that $\Pr[Y_i=1] = p\beta_i = \alpha_i$. If we define $Y := Y_1 + \cdots + Y_n$ then $X \geq Y$ and $\mathbb{E}[Y] = \sum_i \alpha_i = \alpha$, and so Chernoff's bound apply to $Y$, showing that $\Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}$. Since $Y \leq X$, we conclude that $$\Pr[X \leq (1-\delta)\alpha] \leq \Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}.$$

## 相关问题

2  证明$forall a> 0.bpp [{a，a + frac {1} {n}}] = bpp$  ( Prove forall a0 bppa a frac1n bpp )

3  从一组数字以固定的总和采样  ( Sampling from a set of numbers with a fixed sum )

0  Chernoff边界（上尾）  ( Chernoff bounds upper tail )

2  Chernoff界限和蒙特卡罗算法  ( Chernoff bounds and monte carlo algorithms )
Wikipedia的一个使用削减界限的例子是算法$a$计算函数$f$的正确值，概率$p＆gt; 1/2$。基本上，Chernoff边界用于使用重复呼叫对$A$和大多数协议将$a$的误差概率绑定。 我不明白如何，坦率。如果有人可以逐一拆分它会很好。此外，是否有价值是否是决策算法或可以返回更多值？ ...

4  当我们只有少的延期界限时绑定  ( Chernoff bound when we only have a lower bound of expecation )

2  预期的最大垃圾箱负荷，用于箱中的球，球和箱数等于球和垃圾箱[关闭]  ( Expected maximum bin load for balls in bins with equal number of balls and bins )

6  当我们只有上限的期望时，Chernoff绑定  ( Chernoff bound when we only have upper bound of expectation )

1  使用Chernoff绑定的任何分布的计算欺骗性  ( Computational indistinguishability for any distribution using a chernoff bound )

-1  仅使用期望的上限应用Chernoff绑定  ( Applying a chernoff bound with only an upper bound of the expectation )