机器算法验证 - 霍夫丁的束缚在任何方面都紧密吗？ - 吾爱随笔录

机器算法验证可能性随机变量概率不等式

2022-04-11 10:02:29

不平等：

Pr (\bar{X} - E [\bar{X}] \geq t) \leq \exp (- \frac{2 n^{2} t^{2}}{\sum_{i = 1}^{n} (b_{i} - a_{i})^{2}})

$\Pr(\overline X - \mathrm{E}[\overline X] \geq t) \leq \exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$

从某种意义上说，这种束缚（或任何其他形式的束缚）是否紧密？例如，是否存在一个分布，其界限不超过每个 n 的真实概率的常数倍？

2个回答

一个简单的例子是如果 $X_i$ 是确定性的（比如总是等于 0）。那么右手边将是 0 处的狄拉克质量（如在Hoeffding 不等式的证明中所见）。

是有界的假设相矛盾 $\bar{X}$ ，因为

0 < C \exp (- \frac{2 n^{2} t^{2}}{\sum_{i = 1}^{n} (b_{i} - a_{i})}) \leq P (\bar{X} \geq E [\bar{X}] + t) \forall t \geq 0

$0 < C \exp\left( -\frac{2n^2 t^2}{\sum_{i=1}^n (b_i-a_i)}\right) \leq P( \bar{X} \geq E[\bar{X}] + t) \qquad \forall t \geq 0$

我不确定您是否可以准确地为 Hoeffding对于 Chernoff，您可以说矩界比 Chernoff 界更紧。在链接的论文中，作者还指出（但将证明推迟到引文中，对于大，如果是切尔诺夫界，那么， $n$ $t$ $C(t)$

Pr (X > t) \leq C (t) e x p (- o (t))

$\Pr(X>t) \leq C(t)exp(-\mathcal{o}(t))$

其中是通常的“小哦”符号（当时值变为 0 ）暗示对于大。链接的 Philips 和 Nelson 论文中的证明方法也适用于 Hoeffding 案。 $\mathcal{o}(t)$ $t \to \infty$ $\Pr(X>t) \leq C(t)$ $t$

该证明的论文中引用的参考文献是 Bucklew 的 Large Deviations 书籍，

这是该书的谷歌图书页面的链接。如果您想要证明，希望您可以通过当地大学图书馆找到一份副本。

其它你可能感兴趣的问题