大偏差有多罕见?
弱大数定律指出,独立同分布、方差有限的变量,其平均数依概率趋向均值。但面对有限样本,我们常需要指定误差发生的概率上界。切比雪夫(Chebyshev)不等式只利用方差,固定误差下所得界按 的速度下降。若观测值独立且有界,指数变换能提供更强的信息,得到随 指数下降的界。
令 。对任何 ,只要所需期望有限,把马尔可夫(Markov)不等式应用于正随机变量 ,便有
每个允许的 都给出有效的界;选择 是方法的一部分。独立性令期望分解为各变量指数矩的乘积。控制每个因子后,才得到样本数增加带来的改善。
有界变量的指数矩引理
定理 20.1.1
(Hoeffding 引理)
若实随机变量 几乎必然满足 ,其中 ,则对每个实数 ,
若 ,中心化变量为零,同一公式的右边为 。
证明
(对数矩母函数的曲率)
设 及 。由于 有界,我们可对期望在所有实数 下微分。在密度为 的倾斜概率测度之下,微分得到 及 。倾斜后 仍落在长度为 的区间。
对任何落在 的随机变量 ,由 得 ,因此
所以 。又 ,从 到 积分两次便得 。若 ,可对 和 应用同一论证。取指数即得结论。
证明透视
区间长度为何要平方
证明从不直接估计 ,而是转到 ,控制它的曲率。 有界这一点用了两次:它允许对所有实数 在期望号下求导;它在指数倾斜后仍然保留,因为倾斜后的分布有相同的支撑集,所以 仍落在长度为 的区间内。中心化只用了一次,给出 ;连同 ,它去掉了泰勒(Taylor)估计中的常数项和一次项。
关键一步是把 看成倾斜测度下的方差,并用同一常数 控制所有这些方差。积分两次后,正是这个一致上界变成 。只控制 处的方差,只能控制 ,对远离零的 毫无信息。因此区间长度的平方,是作为限于该长度区间的变量所能有的最大方差而出现的。
定理 20.1.2
(和的 Hoeffding 不等式)
设 独立,且几乎必然有 。令 。若 、,则
因此双尾概率不超过 。若 ,和几乎必然为常数,两个偏差事件的概率均为零。
证明
(最优化二次指数)
由独立性和引理,对每个 ,上尾概率不超过 。此二次式在 达到最小值,得到所述指数。对 应用同一论证可得下尾界,再用并集界处理双尾。
若独立变量都在 内,代入 得
它们不必同分布:这里的中心是各自期望的平均。若观测值独立同分布,中心便是共同均值 。
常见错误
(单尾不等于双尾)
上界 只控制一条尾。像 这样的事件是两条尾的并,并集上界把两个估计相加,因子 不能省去。在下面的样本量例子中,若省去它, 会变成 ,所需样本量会被低估为 ,而不是 。
例题 20.1.3
(有限样本的精度保证)
假设 是 内独立同分布的测量,未知均值为 。要保证 的上述上界不超过 ,只需
因此 足够。这是针对最坏情况的充分样本数,不是说实际误差概率等于 ,也不表示某个特定分布不能使用较少观测值。
例题 20.1.4
(同一保证下的 Chebyshev 与 Hoeffding)
沿用上例的设定。由引理证明中的区间方差上界,落在 内的变量方差至多为 。因此 Chebyshev 不等式给出
只有 时它才不超过 ,约为 Hoeffding 所需 的九倍。样本很小时,两个界都可能不提供信息。 时,Chebyshev 给出 ,Hoeffding 给出 ;后者大于一,因此什么也没有说明。只有当 大到足以使指数项抵消因子 时,指数界才有用。
保留伯努利分布的信息
只使用范围的界忽略了成功概率;保留它可以得到更精确的指数。
定理 20.1.5
(伯努利(Bernoulli)和的 Chernoff 界)
设 独立同分布且服从伯努利(Bernoulli),其中 ,则 计算成功次数。令
若 ,则 ;若 ,则 。
证明
(最优化指数参数)
对 及 ,Markov 不等式与独立性给出
右边的对数除以 后,其导数为 。唯一零点满足 ,此时 。代入得
若 ,对失败次数 应用上尾情形:它服从成功概率为 的二项分布,事件 即 ,其中 ,且 。
门槛 不必是整数;事件的意思是 。端点 及 可直接处理:其概率分别是 和 。以上是不等式而非尾概率的精确值; 是两个概率的函数,一般不对称,故不是距离。
常见错误
(Chernoff 指数只适用于越过均值的一侧)
上尾界要求 。由于对每个 都有 ,把它用在均值错误的一侧,会得到虚假地小的数。取 、,若选 ,则 ,;但 接近一:正确的下尾界给出 ,因此 。
例题 20.1.6
(偏置硬币)
取 、、,Chernoff 界为
只利用范围的单尾 Hoeffding 界用 ,结果为 。此例中的 Chernoff 界较精确,但两者都不是二项分布尾概率的精确值。
反例模式
相同的观测值未必独立
令 ,其中 服从伯努利。每个 均在 内,但 ,因此对每个 都有 。若错误代入独立变量的界,随 增加最终会得到小于 的数值。有界和同分布不能取代独立性。
练习
快速检查
(独立变量几乎必然满足 。求 的双尾上界。)
解答 · 答案
共同区间长度为 ,所以上界是 。事件中的均值是各个均值的平均,无须同分布。
快速检查
(独立的 分别几乎必然在 和 。求 的上界。)
解答 · 答案
、,故界为 。
快速检查
(若 ,用伯努利 Chernoff 计算求 的精确形式上界。)
解答 · 答案
取 、,得到 。由于 ,此界适用于 。
快速检查
(一个独立同分布样本在 内。对 ,找出 ,使 以至少 的概率包含均值。说明哪个对象是随机的。)
解答 · 答案
令 ,得 。区间随样本改变,而总体均值是固定的。覆盖结论来自双尾不等式;观察到某个区间后,不能说固定均值以概率 落在该特定区间内。