随机算法不仅需要平均表现,还需要失败概率的保证。集中不等式将随机变量的信息转化为异常事件的概率界。我们先证明两个基本界,再说明放大成功率时独立性在哪里起作用。
定义
定理 3.2.1
(马尔可夫(Markov)不等式)
若 X≥0、a>0 且期望有限,则 Pr(X≥a)≤E[X]/a。
逐点有 X≥a1{X≥a}。两边取期望并除以 a 即得。
反例模式
没有非负性,马尔可夫不等式不成立
设 X 以各一半的概率取 100 或 −100。则 E[X]=0,若在 a=100 套用马尔可夫界,会得到 Pr(X≥100)≤0,但真实概率为 1/2。只有当变量非负时,该不等式才成立。
定理 3.2.2
(切比雪夫(Chebyshev)不等式)
若 X 的均值为 μ、方差为有限数 σ2,则对 a>0,
Pr(∣X−μ∣≥a)≤a2σ2.
将马尔可夫不等式应用于非负变量 (X−μ)2,阈值取 a2。
若独立随机变量 X1,…,Xn 具有共同均值 μ 和方差 σ2,其平均值 Xˉ 的方差为 σ2/n,因此 Pr(∣Xˉ−μ∣≥ε)≤σ2/(nε2)。独立性使交叉协方差为零;分别给出均值和方差界时,无须要求同分布。若右边大于一,可改用概率的平凡上界一。
放大判定算法的成功率
假设每次独立试验以至少 2/3 的概率给出正确答案,进行奇数次 n 次试验。令 Yi 为第 i 次失败的指示变量,S=i∑Yi。于是 ES≤n/3,而独立性给出 Var(S)=i∑pi(1−pi)≤n/4。多数投票失败必有 S≥n/2,故 S−ES≥n/6。切比雪夫不等式给出
Pr(多数投票失败)≤(n/6)2n/4=n9.
这是多项式下降的上界;更强的集中界可以得到指数下降。单纯重复并不足够:若所有答案复制同一次随机试验,多数投票的失败概率与原来完全相同。仅知道错误次数的期望也不能证明独立性。
练习
每次独立运行得到一个方差为 4 的无偏估计。取 n=400 次的平均值,其方差为 0.01。当 ε=0.2 时,误差至少为 0.2 的概率至多为 0.01/0.04=1/4;这不是说实际概率等于 1/4。
快速检查
(非负随机变量的期望为 3。求它至少为 12 的概率上界。)
取 a=12 套用马尔可夫不等式。
解答 · 答案
马尔可夫不等式给出 Pr(X≥12)≤3/12=1/4。
快速检查
(独立无偏估计的方差均至多为 9。为保证平均值偏离真值至少 1 的概率至多为 0.01,切比雪夫不等式需要多少次运行?)
对平均值套用切比雪夫不等式,其方差至多为 9/n。
解答 · 答案
平均值方差至多为 9/n,故概率至多为 9/n。取 n≥900 即可。这是充分条件,不一定是某个具体分布的最小次数。
定理/命题
换一种尺度后仍可应用马尔可夫不等式。若 λ>0 且 E[eλX] 有限,指数函数单调性给出
Pr(X≥a)=Pr(eλX≥eλa)≤e−λaE[eλX].
参数 λ 可以自由选择。先计算或估计指数矩,再选使右边小的参数,便得到有用的上界。这个推导本身不需要独立性;对和的指数矩进行乘积分解时才需要独立性。
定理 3.2.4
(独立伯努利(Bernoulli)试验的霍夫丁(Hoeffding)界)
设 Y1,…,Yn 独立且服从伯努利分布,不必同分布,各自均值为 pi。令 S=i∑Yi、μ=ES。对每个 a>0,
Pr(S−μ≥a)≤e−2a2/n.
对均值为 p 的伯努利变量 Y,定义
g(λ)=logEeλ(Y−p).有 g(0)=g′(0)=0。求两次导数得到 g′′(λ)=q(1−q)≤1/4,其中 q=peλ/(1−p+peλ);p=0,1 两种端点情形可直接验证。积分两次得到当 λ≥0 时 g(λ)≤λ2/8。独立性使指数矩分解,因此
Pr(S−μ≥a)≤exp(−λa+nλ2/8).取 λ=4a/n 即得结论。
证明透视
霍夫丁证明在哪里用到各假设
各假设用在哪里:每个 Yi 有界,给出 g′′≤1/4,因此不论均值 p 为何,都有二次上限 g(λ)≤λ2/8。独立性只用一次,即把 n 个指数矩相乘。关键一步是用二阶导数控制矩母函数的对数:因减去了均值,g(0)=g′(0)=0,而 g′′=q(1−q) 是倾斜后伯努利变量的方差。收尾一步是优化:−λa+nλ2/8 在 λ=4a/n 处最小,值为 −2a2/n。没有独立性便无法把矩相乘,本节稍后的重复反例就说明了这一点。
对于独立的判定试验,若每次失败概率至多为 1/3,多数失败蕴含 S−ES≥n/6,因此概率至多为 e−n/18,随试验次数指数下降。若要它至多为 δ∈(0,1),取奇数 n≥18log(1/δ) 即可。这里的对数为自然对数。结论针对固定输入:每次试验都须在同一输入上满足成功保证,并使用新的独立随机性。
例题详解
假设每次独立运行失败概率恰为 1/3,取 n=180,并把票数相同视为失败。前述切比雪夫界为 9/180=0.05,指数界为 e−10<0.000046。后者是保证,而非精确二项尾概率。多数投票通常取奇数次;若取 181 次,相应界分别为 9/181 和 e−181/18。如果只知道方差,却没有有界性或适当指数矩,即使较弱的界仍可能有用。
快速检查
(100 个独立伯努利变量的均值总和为 40。求它们的和至少为 50 的概率上界。)
解答 · 答案
取 a=10、n=100,霍夫丁界为 e−2(10)2/100=e−2。各变量不必有相同的成功概率。
单侧与双侧界
上尾不等式控制高于均值的偏差。将它应用于独立伯努利变量 1−Yi,便控制低于均值的偏差。再用并集界合并两个事件,得到
Pr(∣S−μ∣≥a)≤2e−2a2/n.
并集界不要求这两个事件独立:由 1A∪B≤1A+1B 取期望即可。独立性是在此前估计各指数矩时需要的。系数二来自需要覆盖两个偏差方向。右边大于一时不等式仍成立,但没有信息;概率本来就不超过一。
对均值同为 p 的独立伯努利样本,令 S=np^,得到
Pr(∣p^−p∣≥ε)≤2e−2nε2.
要使它至多为 δ,取 n≥log(2/δ)/(2ε2) 即可。此界对未知的 p 一致成立,所以可在观察样本前确定样本量。这是对随机抽样程序的保证,并非说固定观察区间包含固定参数的概率是随机的。
要以至多 0.05 的失败概率把伯努利均值估计到误差 0.1 以内,取 n≥log(40)/0.02≈184.44,所以 185 个独立样本足够。这个界可能保守;它没有声称 185 对所有分布和估计方法都是最小样本数。
同时估计多个量
假设要估计 m 个量,每个量内部使用独立样本。如果每个估计的误差至少为 ε 的概率至多是 δ/m,并集界说明至少一个估计失败的概率至多为 δ。最后这一步不要求不同估计之间独立。对伯努利样本,每个量取
n≥2ε2log(2m/δ)
个样本就足够,其中 m 是正整数且 0<δ<1。对 m 的依赖是对数级,但若样本不能共享,m 组数据仍可能需要 mn 个观测。证明运行时间时必须计算实际抽样成本,不能把概率界当作复杂度分析。
对 m=10、ε=0.1、δ=0.05,公式要求 n≥log(400)/0.02≈299.57,故每个量取 300 次观测足够。即使十个失败事件高度相关,只要各自满足概率界,并集界仍成立。
相关性会破坏重复的效果
反例模式
没有独立性的重复
令 B 为单个伯努利变量,Pr(B=1)=1/3,并令每次试验的失败指示变量 Yi=B。每次试验各自失败的概率都是 1/3,但无论重复多少次,多数失败恰在 B=1 时发生。此时 S=nB,所以 Var(S)=n2Var(B),而非 nVar(B);被遗漏的协方差项解释了差别。
独立随机性是对联合分布的数学条件,不仅仅是把算法运行多次。重复使用随机种子、共享随机预处理或共享样本都可能引入相关性。某些相关过程可以用别的集中方法分析,但需要单独证明。
快速检查
(五个估计器各自失败的概率至多为 0.02。不假设它们独立,至少一个失败的概率有何上界?)
解答 · 答案
并集界给出 5(0.02)=0.10。事件不需要互斥或独立;若它们重叠,概率相加可能重复计数。
快速检查
(独立伯努利样本的均值为 p。要以至多 0.01 的失败概率估计到误差 0.05 以内,双侧界要求多少样本?)
由 2e−2nε2≤δ 解出 n。
解答 · 答案
取 n≥log(200)/(2(0.05)2)=200log(200)≈1059.66 即可,故 1060 个样本足够。该界控制误差大于或等于 0.05 的事件,因此也控制误差严格大于 0.05 的事件。
仅知道期望能保证什么?
仅知道均值和非负性时,马尔可夫界有时已无法改进。固定 0<μ<a,令 X 以概率 μ/a 取 a,其余时候取零。则 EX=μ,而 Pr(X≥a)=μ/a,恰好达到马尔可夫界。若要得到更强的普遍结论,必须加入分布的其他信息。
这对运行时间分析很重要。若非负运行时间 T 的期望至多为某个 M>0,马尔可夫界给出 Pr(T≥10M)≤1/10。这不意味着每次运行都在 10M 内结束,也不意味着尾概率随阈值指数下降。期望为 M 的算法仍可能偶尔运行很久;均值限制这些情况对平均值的贡献,却不能消除它们。
令 T 以概率 0.01 取 100,其余时候取零。期望为一,但一次运行耗时 100 的概率为百分之一。事件 T≥100 的概率为 0.01,恰好达到马尔可夫界 1/100。这是抽象模型;实际算法如有正的最小开销,可加上一个常数。
常见错误
假设判定算法在每个输入上的错误概率各自至多为 1/3。对一个固定输入,使用新的独立随机性重复,便能应用多数投票界。但不能因此断言某一次随机选择对所有可能输入同时正确。若输入集合有限且需要同时正确,可以尝试对输入使用并集界,但必须把集合大小计入计算。如果输入在随机性公开后被自适应选择,逐输入保证的解释也会改变,须另行论证。
例如,若有 m 个固定输入,每个输入放大后的失败概率至多为 e−n/18,则至少一个输入失败的概率至多为 me−n/18。这里不要求不同输入的失败事件独立。取奇数 n≥18log(m/δ) 可使该界至多为 δ。当 δ<1 时,这证明存在一组对所有这些输入都有效的随机种子;但并不自动给出有效的确定性方法找到它。
快速检查
(非负算法运行时间的期望至多为 20 秒。马尔可夫不等式对超过 100 秒的概率给出什么结论?)
解答 · 答案
Pr(T>100)≤Pr(T≥100)≤20/100=0.2。不等式并不说明运行时间必定不超过 100 秒。
总结
可用假设决定适用的界。马尔可夫不等式使用非负性和有限均值;切比雪夫不等式将它用于偏差的平方,并使用有限方差。这里的指数界增加了独立有界伯努利试验的条件,得到更强尾界。并集界合并失败事件时不要求这些事件独立。每次应用时,应先确定随机试验、目标事件和假设,再代入数值。上界可能不紧、大于一,也可能在特殊情况下达到;它并不自动等于精确概率。固定输入的高概率保证也不同于对所有输入同时成立的保证。假设失效时,即使公式看似合理,也可能有反例推翻结论。