浅谈概率集中不等式

这里面真的只有概率集中不等式基础，但是我确实也是第一次正经写某些 bound 。

Markov Inequality

• 对于非负的随机变量 ，对于任意 有：

• 证明比较简单，做截断即可。

Chebyshev Inequality

• 对于随机变量 与任意的 ，有：

• 之前我给过另一个证明，是直接按定义展开积分然后用方差的定义。现在我们给出一个更简洁的证明，考虑： Chebyshev 有一个好处是，我们知道做独立重复试验时均值的方差会变小，所以我们有时可以通过简单的重复得到更好的界。

Chernoff Bound

• 我们在 CS2701 的作业里面其实用过这个技巧，不过现在我们将正式介绍它。对于随机变量 ，我们希望衡量其集中的程度，我们希望利用比一阶矩（Markov）或是二阶矩（Chebyshev）更强的条件，也就是 的矩生成函数。为此我们要做特地的构造，对于非负的 与任意 ，应有： 在一般的情况下，此处应做对于 的最小化以得到尽量紧致的界。

Multi-Poisson Chernoff Bound

• 下面我们将会介绍一些具体的例子，先考虑 次泊松试验的例子。即，假设 服从 次独立的泊松试验使得 ，记 ，显然 。那么对于 ： 对于前者，考虑： 为了消除连乘： 令 ，得到： 现在我们断言：¹ 这个式子证起来没什么技巧，所以我们就不演示了。这样就有： 对于另一部分，取一 ，有： 令 ，比较简单可以得到： 从而：

Hoeffding Bound

• Hoeffding Bound 基本还是在用矩生成函数做要求，不过现在我们要将随机变量与高斯分布做比较，即借用高斯分布的 Chernoff Bound 。具体的，我们先提一些要求。

Sub-Gaussian Random Variable

• 对于随机变量 ，记 ，我们称 是次高斯的，当且仅当：² 容易验证，其中 为服从 的随机变量的 MGF 。³另外次高斯的随机变量有不少等价叙述，但是这里并不打算深入。

• 对于次高斯的随机变量 ，其集中程度可以比较方便的刻画。我们直接使用一个简单的 Chernoff Bound ，对于 ： 对 优化得到：

Hoeffding Lemma

• 大家可能会觉得次高斯是一个挺强的条件，但实际上一致有界的随机变量都是次高斯的，这就是 Hoeffding Lemma 。具体的，我们先给出 Hoeffding Lemma 的叙述：

  • 对于一致有界的随机变量 ，有：

  直觉上具备界 的随机变量的标准差至多为 ，而上式基本是在说这样的随机变量的矩可以被标准差为 的高斯分布控制，这很符合直观。

• 以下我们要严格的证明这个引理，应该需要一定技巧。我们先证明具备界 的随机变量的方差最多为 。我们有： 对于方差应有： 记 ，其最大值在 除取得，恰为 。注意到当 时方差恰为 ，故该上界是紧的。

  现在我们要用到一些技巧。对于具备界 的随机变量 的分布 ⁴，定义分布： 这个分布基本是在固定 时对 的矩生成函数做了归一化。现在考虑 ，记 ，我们有：⁵ 注意到 仍然具备界 ，因此必然有 。现在考虑带有 Lagrange 余项的 Taylor 公式： 其中 。注意到 ，从而： 这里的 是关于 的常数，从而： 从而 Hoeffding Lemma 得证。

Hoeffding Bound (Tensorized Version)

• 我们先考虑一下独立次高斯随机变量的和的矩生成函数。对于一列独立且次高斯的 ，其被标准差为 的高斯分布控制。记 ，考虑：

• 现在我们给出较为常用的 Hoeffding Bound 的叙述。对于一列独立随机变量 ，假设它们具备一致的界 ，记 ，则有： 通过 Union Bound 、Hoeffding Lemma 以及 Chernoff Bound ，上式可以被简单的证明，这里就不赘述。

Martingale Method

• 实际上鞅是现代概率中非常重要的工具，但是我还没详学，等我学完一定回来写这个。

---

1. 我也不知道他们是怎么想到这个的。也许是从 的情况推广来的。↩︎

2. 矩生成函数。↩︎

3. 这个积分基本就是 Poisson 积分。↩︎

4. 这里指的是概率密度函数。↩︎

5. 先承认期望和求导是可交换的。↩︎