机器人入行指南
原理层/四个不等式:「多少样本才够」的定量答案

原理层 T16 / 27 · 概率与期望

四个不等式:「多少样本才够」的定量答案

Markov 只用非负性,Chebyshev 加方差,Hoeffding 加独立性——一层层收紧,前提一层层变多。策略评估要跑多少个 episode,是有公式的。

Markov只要非负 · 界最松P(X≥a)≤EX/aChebyshev加方差 · 平方衰减P≥σ²/(a²)Hoeffding有界独立 · 指数衰减e^{−2na²}三 个 concentration 不等式强化学习的 regret bound 和收敛速度全从这三个里挑一个用——越强的假设换越紧的界
约 45 分钟4 定理9 步证明4 题自测

一句话结论

样本量不是拍的。同一件事「均值偏离 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 构造直接可得):

P(X≥t) = E[1X≥t] ≤ E[X/t] = E[X]/t。∎

注证明只用了「非负」和「期望保序」。代价是界非常松——它对一切非负分布成立,等于对分布形状一无所知时的最坏情况。

定理 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 至少多大?

  1. 设 X̄ = (1/n)ΣX_i,X_i~Bernoulli(p)。μ=0.3,Var(X̄) = p(1−p)/n = 0.21/100 = 0.0021。
  2. 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 能给的全部)。
  3. [object Object]
  4. [object Object]
  5. 样本量: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[·]) 的方向判断用法 →
Chebyshevmini-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 就够),但这是可证明的下限——写报告时用它,不用拍脑袋。

接着看

全系列 27 篇

T1矩阵就是旋转的记账本约 25 分钟T2从斜率到梯度:机器人学习算法的第一行约 25 分钟T3向量与受力:点积的物理读法约 20 分钟T4两把尺子和一把更好的尺子约 25 分钟T5电机转一圈的账:弧度、转速与功率约 20 分钟T6复数乘法就是旋转:四元数的一维版约 20 分钟T7基与坐标:为什么机器人什么都用矩阵约 45 分钟T8矩阵乘法:变换的串联,不是表格运算约 40 分钟T9雅可比:关节转一度,末端动多少约 45 分钟T10特征向量:矩阵不敢动的方向约 45 分钟T11SVD 与伪逆:没有精确解时,找最近的解约 50 分钟T12泰勒展开:用直线替曲线打工约 40 分钟T13概率空间:为什么「随机」需要公理约 50 分钟T14期望:「平均」的严格构造约 55 分钟T15条件期望:竖线的真正含义约 60 分钟T16四个不等式:「多少样本才够」的定量答案约 45 分钟T17范数与不动点:「一定收敛」的出处约 55 分钟T18马尔可夫链:时间平均何时等于集合平均约 55 分钟T19MDP 的数学构造:一条公理值多少钱约 50 分钟T20动态规划:两种迭代的账约 50 分钟T21优化:约束为什么不能只靠罚约 55 分钟T22随机逼近:学习率公式里的每一条约 55 分钟T23接触的数学:Hertz 理论约 45 分钟T24摩擦与摩擦锥:约束的几何形状约 40 分钟T25力封闭与抓取度量:ε 是一个线性规划约 50 分钟T26接触运动学:滚动为什么不是「贴着滑」约 45 分钟T27滑移检测:从「感觉到了」到「算出来了」约 50 分钟