CMSC 5728 Decision Analysis & Game Theory - Lecture 09
- The Chebyshev Inequality
- The Central Limit Theorem (CLT)
- Cramer-Chernoff Methods and Sub-Gaussian RVS
- Hoeffding’s Inequality
- Azuma-Hoeffding’s Inequality
- Summary
The Chebyshev Inequality
- 对于随机变量 X，定义有限均值 μ，方差 σ^2
- 如果方差很小，那么 X 不太可能离它的均值太远
application：
对于 k = 3，相距三个标准差的概率上的上限是 1/ 9
使用 Chebyshev ineuality，我们可以根据随机变量 X 的方差来限定 empirical estimate 的两侧尾部概率
- 因此，这种双向边界取决于
- 参数 ε
- X 的方差（我们可能不知道，或者至少这是我们必须处理的另一种 estimation）
The Central Limit Theorem (CLT)
令
CLT 指出
的极限分布式标准的高斯分布，均值为0，方差为单位方差，记为 
因为
，我们有 
，尾部概率为
但是这需要 n 区域无穷，我们需要有限的 n。
Cramer-Chernoff Methods and Sub-Gaussian RVS
Sub-Gaussian：对于所有 λ ∈ R，一个随机变量 X 是 σ-sub-Gaussian 的话，那么
上述定义是说 X 是有限的并且被所有 λ 所限制
不是所有随机变量都是 σ-sub-Gaussian。例如，如果 X 是 exponential R.V.，它的概率密度函数是
，对于 x ≥ 0，我们有
值得重要一提的是，σ-sub-Gaussian 随机变量的尾部衰减至少与平均值为 0 且方差一样的 Gaussian 的尾部衰减一样快，这是限制 sub-Gaussian R.V. 的关键
Theorem 2.1
如果 X 是一个 σ-sub-Gaussian R.V.，那么对于任意 ε ≥ 0，我们有
Proof
使用类似的方法，同样也可以获得 left tail probability 的限制，即，P(X ≤ -ε)。通过使用 union bound，P(A ∪ B) ≤ P(A) + P(B)，我们有
现在我们想要 tail probability 很小。此外，我们还要在这个概率中表达 ε，我们令 
，转换可得 
。所以我们可以将 two-sided tail 限制为
上面的表达式更有吸引力，因为当 δ 很小时，它表明至少在 1 - δ 的概率，随机变量 X 在以下区间内
Properties of Sub-Gaussian RVs
Lemma 2.1
如果 X 是 σ-sub-Gaussian R.V.，那么 X 的均值是 E[X] = 0，并且 X 的方差是 V[X] ≤ σ^2
Proof
Lemma(Scaling property) 2.2
如果 X 是σ-sub-Gaussian R.V.，那么对于任意 c ∈ R，非零 scaled 随机变量 cX 是 |c|σ-sub-Gaussian R.V.
Proof
Leema(Additive property) 2.3
如果 X1 和 X2 是两个独立随机变量，Xi 是 σi-sub-Gaussian (i ∈ {1, 2})，那么 X1 + X2 是
Proof
Corollary 2.1
如果 X1, X2, …, Xn 是 IID RVs 并且 每个都是σ-sub-Gaussian随机变量，那么 X1 + X2 + ··· + Xn 是 
Important remark
- 如何联系起 MAB？
- 考虑仅一个 arm，这个 arm 的收益由 E 建立，比方说，Bernoulli 随机变量的结果为 0（失败）或1（获胜），使得获胜的概率为 μ。我们的目标是估计平均获胜（即 μ）然后我们使用 unbiased estimator
。我们想要通过一些有限的观察来得到 
- 这可以通过以下引理来说明
Leema 2.4
如果 Xi - μ 是独立的，则是 σ-sub-Gaussian RVs。令
，那么对于任意 ε ≥ 0，我们有
使用 union bound，我们有 
Proof
Summary (more convenient form)
定义 δ ∈ [0, 1] 与
。所以 
右边尾部
。或者参数 μ 有较高可能性被 
与 ε 限定。同样地，
使用 union bound，我们说 μ 在区间内有至少 1- 2δ
Hoeffding’s Inequality
假设 X1, X2, …, Xn 是独立随机变量，它们的均值为 μ1, μ2, …, μn，并且 Xi - μi 是一个 σi-sub-Gaussian，那么
特别地，当 σi = σ ∀ i ∈ {1, 2, …, n}，那么不等式是我们之前提到的简化版
Different forms
Azuma-Hoeffding’s Inequality
Summary
- 利用 Hoeffding 不等式，我们现在有了一个数学工具可以帮我们断言我们想要估计的处于高概率区间内的均值参数 μ
- 区间由我们设置的阈值以及观察次数决定
- 我们取得了