Homework 2

Problem 1

注意到 Theorem 2 为 Theorem 1 的特殊情况，故服从 Theorem 1 中的不等式

（通过技术手段发现 Theorem 2 中的不等式集体比 Theorem 1 松）

下面证明：Theorem 2 的不等式比 Theorem 1 更松，即

首先证

对上式，两边取对同除 后变为

考察

二阶导在 正， 负，而 ，故

又 ，故

再证

同理化为

既得

最后证

同理化为

其中

又

原式得证

综上，证毕

Problem 2

则 , ，由 Chernoff Bound (Theorem 1),

另一方面，由 Theorem 2 得

故更紧的 bound 是 ，这也侧面印证了 Problem 1 的结论。

即预测概率小于