原理层 T16 / 27 · 概率与期望
四个不等式:「多少样本才够」的定量答案
Markov 只用非负性,Chebyshev 加方差,Hoeffding 加独立性——一层层收紧,前提一层层变多。策略评估要跑多少个 episode,是有公式的。
一句话结论
样本量不是拍的。同一件事「均值偏离 0.1」,Markov 界给 0.75、Chebyshev 给 0.21、Hoeffding 给 0.135、实测是 0.012——界宽松不代表无用,它们的作用是给出可证明的样本量下限。
「评 100 个 episode 够不够」「mini-batch 取 64 还是 256」,这类问题有定量答案,出处就是本篇。更重要的副产品:Jensen 不等式是策略梯度里 log 项处理、KL 散度推导的底层工具。
为什么需要它
你训练了一个策略,跑了 100 个 episode,平均回报 42.7。领导问:真实期望回报是 43 以上吗?你手头的武器只有样本均值和它的方差估计——要从样本推总体,必须给「偏离超过 δ 的概率」一个上界,而计算这个上界不能再用样本(否则循环论证)。
出路是只用总体的少量信息(均值?方差?有界性?)推出最坏情况界。信息用得越少,界越松;愿意假设得越多(独立性、有界性),界越紧。四个不等式就是这条权衡线上的四个刻度。
先建立记号:X 是随机变量,μ=E[X],我们要界 P(X − μ ≥ t),即 X 超过均值 t 以上的概率。
定义
定理与证明
定理 4.1 Markov 不等式
X≥0 且 t>0,则 P(X ≥ t) ≤ E[X]/t。只假设非负,别的什么都不要。
证
构造指示函数:1X≥t ≤ X/t 对每个样本点成立(X≥t 时左边 1 ≤ X/t;X<t 时左边 0,显然)。
两边取期望(期望保序:A≤B 则 E[A]≤E[B],这由定义 2.2 的 sup 构造直接可得):
注证明只用了「非负」和「期望保序」。代价是界非常松——它对一切非负分布成立,等于对分布形状一无所知时的最坏情况。
定理 4.2 Chebyshev 不等式
P(|X−μ| ≥ t) ≤ Var(X)/t²。
证
构造非负变量 (X−μ)²,对它用 Markov(取阈值 t²):P((X−μ)² ≥ t²) ≤ E[(X−μ)²]/t²。
左边 { (X−μ)² ≥ t² } 与 { |X−μ| ≥ t } 是同一事件(非负函数单调),右边 E[(X−μ)²] = Var(X)。∎
注多用了方差信息,换来 t 的一次变平方:偏离概率随 t² 衰减而非线性。注意左右两边事件的等价改写是证明的全部技巧——「把要界的事件改写成某个非负变量超阈值」是这一族不等式的通用套路。
定理 4.3 Jensen 不等式
f 凸,X 可积,则 E[f(X)] ≥ f(E[X])。凹函数反向。
证
凸函数的支撑线性质:对任何锚点 x₀,存在斜率 s 使 f(x) ≥ f(x₀) + s·(x − x₀) 对一切 x 成立(切线在凸函数下方;不可导点取次梯度)。
取锚点 x₀ = E[X]:f(X) ≥ f(E[X]) + s·(X − E[X])。
两边取期望,用线性(T2 定理 2.1):E[f(X)] ≥ f(E[X]) + s·(E[X] − E[X]) = f(E[X])。∎
注证明的全部原料:支撑线 + 期望保序 + 线性。应用预览:log 是凹的,所以 E[log X] ≤ log E[X]——重要性采样的有效样本量、KL 散度的非负性、EM 算法的下界化,全是这一条换装登场。
定理 4.4 Hoeffding 不等式(陈述)
X_1,…,X_n 独立,均在 [a,b] 内,样本均值 X̄,则 P(X̄ − μ ≥ t) ≤ exp(−2nt²/(b−a)²)。
证
完整证明需要 Hoeffding 引理(有界变量的矩生成函数控制),超出本篇边界。我们只陈述并使用。
注两个新前提(独立、有界)换来的报酬:n 倍的指数加速。Chebyshev 给的是 n/t² 型衰减,Hoeffding 给的是 e−nt² 型。凡是大数定律级别的保证(蒙特卡洛样本量、泛化界)背后都是这类指数界。
手算一遍
成功率为 p=0.3 的策略,跑 n=100 个 episode 估计成功率。问「估计值偏高 0.1 以上」的概率上界分别是多少(Markov/Chebyshev/Hoeffding)?要保证偏高 0.1 以上的概率 ≤1%,n 至少多大?
- 设 X̄ = (1/n)ΣX_i,X_i~Bernoulli(p)。μ=0.3,Var(X̄) = p(1−p)/n = 0.21/100 = 0.0021。
- Markov:对非负变量 X̄−μ 直接用会得到 P(X̄≥0.4) ≤ 0.3/0.4 = 0.75——界比 0.5 还大,因为 X̄−μ 可能为负而 Markov 不利用对称性。改用 P(X̄−μ ≥ 0.1) ≤ E[X̄]/(μ+0.1) = 0.75(这是 Markov 能给的全部)。
- [object Object]
- [object Object]
- 样本量:Hoeffding 逆解。要求 e−2n(0.1)² ≤ 0.01 → n ≥ ln(100)/(2·0.01) = 4.605/0.02 ≈ 230。
三界分别 0.75 / 0.21 / 0.1353,实测(20 万次模拟)0.0122。要 1% 置信,Hoeffding 说 n≥230。解读:界全部保守(实测比界小一个量级),但界的作用不是预测实测值,是给出可证明的最低样本量——没有它,n 只能靠拍。
实跑一遍
数字出处
p=0.3、n=100、阈值 t=0.1,40 万次模拟实测与三界对比:
- 实测 P(X̄ > 0.4) = 0.01215
- Markov 界 0.750(只用非负性)|Chebyshev 界 0.2100(加方差)|Hoeffding 界 0.1353(加独立+有界)
- Hoeffding 逆解样本量:置信 99% 时 n ≥ 230;置信 99.9% 时 n ≥ 346
映射回强化学习
| 这里的对象 | RL 里的对应物 | 站内用法 |
|---|---|---|
| Hoeffding 样本量 | 策略评估跑多少 episode、A/B 对比需要多少流量 | 用法 → |
| Jensen(log 凹) | 策略梯度里 E[log π] 的处理、KL 散度非负性 | 用法 → |
| Jensen(f 凸) | 信任域推导里 E[KL] ≥ KL(E[·]) 的方向判断 | 用法 → |
| Chebyshev | mini-batch 方差分析、学习率的粗调依据 | 用法 → |
边界:这一篇停在哪里
本篇停在哪里:Hoeffding 引理的证明、Bennett/Bernstein 更紧的界、集中不等式的一般理论(Talagrand),都不讲。够用判据:独立有界样本的均值集中,Hoeffding 已经给出工程上够用的样本量公式。
自测 4 题
全是手算和「找证明错在哪」类题目,不出背诵题。答不上来回到对应小节。
01Markov、Chebyshev、Hoeffding 各自用了什么前提?代价换来了什么?
Markov:非负 → 线性衰减界。Chebyshev:加方差 → t² 衰减。Hoeffding:加独立+有界 → e−nt² 指数衰减。前提每加一层,界紧一个量级,适用范围窄一圈。
02Jensen 不等式证明里的「支撑线性质」在不可导点怎么办?
凸函数在不可导点有次梯度(次微分非空),支撑线取任一次梯度斜率即可。证明不依赖可导性。这也是为什么 Jensen 对 log(处处可导)、|x|(尖点)这类函数都成立。
03为什么 Chebyshev 是双侧界而 Hoeffding 写成单侧?
Chebyshev 的证明对 (X−μ)² 用 Markov,天然对称,界的是 |X−μ|。Hoeffding 证明路径不对称,单侧形式更紧;双侧就是单侧乘 2。工程上通常只关心单侧(估计偏高或偏低),单侧版刚好。
04评估一个策略要「99% 置信下回报均值不低于实测减 0.5」,奖励在 [0,10],需要多少 episode?
Hoeffding 逆解:n ≥ ln(1/0.01)·(b−a)²/(2t²) = 4.605·100/(2·0.25) = 921。界很保守(实际常常几十个 episode 就够),但这是可证明的下限——写报告时用它,不用拍脑袋。