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

Chernoff bound when we only have a lower bound of expecation


简体版||繁體版
4
vote

问题

中文

这个问题: Chernoff绑定了我们只有期望的上限是相似的,而是对于期望的上限。

标准chernoff绑定说,它是$ x $的是0/1随机变量的总和,然后是任何$ delta in(0,1)$,

$ p(x leq(1- delta)e(x)) leq e ^ { - frac { delta ^ 2 e(x)} {2}} $。

假设我们只有$ alpha leq e(x)$。是真的,如果是这样,如何证明,那是

对于(0,1)$中的任何$ delta ,

$ 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
 
vote
vote
最佳答案
 

可以使用耦合。让$ x = x_1, ldots,x_n $,并假设$ pr [x_i = 1] = beta_i $(如此$ beta:= mathbb {e} [x] = sum_i beta_i geq alpha $)。让$ p = alpha / beta $,define $ alpha_i = p beta_i $。让$ z_i sim mathrm {bernoulli}(p)$,并定义$ y_i = x_i z_i $。请注意,$ x_i geq y_i $和那个$ pr [y_i = 1] = p beta_i = alpha_i $。如果我们定义$ y:= y_1 + cdots + y_n $ that y $ x geq y $和$ mathbb {e} [y] = sum_i alpha_i = alpha $,因此chernoff的绑定适用于$ y $ ,显示$ pr [y leq(1- delta) alpha] leq e ^ { - delta ^ 2 alpha / 2} $。自$ y leq x $以来,我们得出结论 $$ PR [X LEQ(1- delta) alpha] leq pr [y leq(1- delta) alpha] leq e ^ { - delta ^ 2 alpha / 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 ) 
我需要证明 $ forall a&gt; 0.bpp [{a,a + frac {1} {n}}] = bpp $ $ bpp [a,b] $ 定义: 语言 L 在 BPP(a,b) 如果只有存在 概率性图灵机<码> M ,这样 M 在 x 中的所有输入上的多项式时间运行> L , M 输...

3  从一组数字以固定的总和采样  ( Sampling from a set of numbers with a fixed sum ) 
让$ s = {x_1,x_2, ldots,x_n } $是一组$ n $随机的非负整数,其中$ sum_i x_i = n $。让$ {y_1,y_2, ldots,y _ { sqrt {n}} } $表示$ s $的szize $ sqrt {n} $的子集,随机选择。定义$ y $ to $ su...

3  在期望不等式的Chernoff的“实用形式”  ( Practical forms of chernoff bound for inequality in expectation ) 
从 wikipedia : 上述公式通常在实践中笨重,因此通常使用以下宽松但更方便的界限: (i) $ pr(x geq(1+ delta) mu) leq e ^ { - frac { delta ^ 2 mu} {3} },0&lt;&lt; 1 $ (ii) $ pr(x leq(1- de...

0  Chernoff边界(上尾)  ( Chernoff bounds upper tail ) 
对于克奈多界的证明(上尾),我们假设δ​​<2E-1。 就像本文一样([参见此链接]) 1 < / a>。你能告诉我为什么? ...

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 ) 
这个问题: Chernoff绑定了我们只有期望的上限是相似的,而是对于期望的上限。 标准chernoff绑定说,它是$ x $的是0/1随机变量的总和,然后是任何$ delta in(0,1)$, $ p(x leq(1- delta)e(x)) leq e ^ { - frac { delta ^ 2...

6  Chernoff-Hoeffd界限为底层中的非安利斯特数量  ( Chernoff hoeffding bounds for the number of nonzeros in a submatrix ) 
考虑$ n times n $ matrix $ a $ w $ w $ n $ nonzero条目。假设每一行,每列$ a $的每一列都有$ sqrt {k} $ nonzeros。按时均匀地均匀行驶和$ a $的列。除以$ k $ a $ a $ $ n / sqrt {k} times n / sqr...

3  用Chernoff绑定找到期望  ( Find expectation with chernoff bound ) 
我们有一群员工,他们的公司将尽可能多地为尽可能多的员工分配给尽可能多的员工。该公司分配了同样的 $ 2 $ 任务到每个员工,并使用 $ 2 $ 值 $ x,y $ 在 $ [0,1] $ 中。如果没有其他员工在两个任务中没有比分数更好的员工,该公司选择了其他人的最佳员工。 知道这两个分数都是统一分布在 $ [0,1]...

2  预期的最大垃圾箱负荷,用于箱中的球,球和箱数等于球和垃圾箱[关闭]  ( Expected maximum bin load for balls in bins with equal number of balls and bins ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并阐明编辑此帖的问题。 关闭 6年前。 ...

6  当我们只有上限的期望时,Chernoff绑定  ( Chernoff bound when we only have upper bound of expectation ) 
如果$ x $是i.i.d的总和。随机变量在$ {0,1 } $和$ e [x] = mu $中占据价值,CHERNOFF绑定告诉我们 $$$$(x geq(1+ delta) mu) leq e ^ { - frac { delta ^ 2 mu} {3}} $$ 所有$ 0&lt; delta...

1  证明了一种随机算法,总和数组元素  ( Proving a randomized algorithm that sums array elements ) 
我试图证明以下算法是正确的: Sum(A[1..n], s)= sum = 0 for r=1 to s i = some random index i in interval [1, n] sum = sum + A[i] return n(sum/s...

1  BPP可以围绕1/2以外的任何常数界定?  ( Can bpp be bounded around any constant other than 1 2 ) 
语言 $ l $ 如果存在随机的tm,则为它以至少 $ 1/2 + 1 / p(n)$ 对于某些多项式 $ p(n)$ ,其中 $ n $ 是输入的长度。此概率可以放大到 $ 1-2 ^(n)} $ ,对于某些多项式 $ q(n) $ 通过重复算法多次多次并取代大多数。 我想知道是否有必要在常量 $ 1/2 $ 上有...

3  减少图灵机所需的随机性  ( Reducing randomness needed by turing machine ) 
我正在阅读与yi li,huy nguyen和david woodruff,huy nguyen和david woodruff,名为"门旋流算法可能也是线性速写的速刷算法的流式速写算法" 相关的文章。 在某些时候,它们具有随机算法(使用随机位的磁带),解决了超过$ mathbb z_ {| m | m | m |}...

1  使用Chernoff绑定的任何分布的计算欺骗性  ( Computational indistinguishability for any distribution using a chernoff bound ) 
我对关于找到任何分布的有关找到计算难以区分的分布的一般声明有问题(在第11页第31页第31页的第三段)这里。这是声明: 对于任何分发 $ d $ over $ {0,1 } ^ {n} $ ,存在一个分发 $ d'$ ,使得 $ d $ 和 $ d'$ $ epsilon $ 与大小的任何古典克萨诸塞级的...

-1  仅使用期望的上限应用Chernoff绑定  ( Applying a chernoff bound with only an upper bound of the expectation ) 
首先,我知道堆栈交换中至少有一个或两个类似的问题,但我经历了他们得到的答案,并没有找到对我案件令人满意的答案。 问题本身如下。假设我有一个sum $ x = sum_ {i = 1} ^ {n} {x_i} $彼此独立的指示器随机变量。还假设我有一个上限$ mu $上的预期值$ e [x] $ x $,但我不知道...

5  塞尔诺夫的浓度界限在排列上  ( Chernoff like concentration bounds on permutations ) 
假设我有$ n $球。其中,有$ m leq n $黑色球,其他$ n-m $球是白色的。修复了这些球的随机排列$ PI $,并在您的折放$ PI $的第一个$ i $职位中表示$ Y_I $ y $ y_i $ of black balls。我想展示$ Y_I $大幅集中在其平均值周围。 预期值 不难计算...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有