为什么有限计算需要极限
无限次试验的问题,往往可以先用有限次试验逼近。例如“曾经成功”是“前 n 次内至少成功一次”这些事件的并集;当 n 增加,后者逐渐扩大。要由有限事件的概率推到并集的概率,必须先证明定理,不能假设概率与任何集合运算都能交换。
若每个 n 都有 An⊆An+1,而 A=n≥1⋃An,记作 An↑A。若 An⊇An+1,而 A=n≥1⋂An,则记作 An↓A。这些记号描述每个结果属于哪些事件,并不只是比较数字 P(An)。
若 An↑A,则 P(An)↑P(A);若 An↓A,则 P(An)↓P(A)。
令 D1=A1,并对 n≥2 令 Dn=An∖An−1。各 Dn 两两不相交,并集是 A,而前 n 个的并集是 An。由可数可加性,
P(A)=k=1∑∞P(Dk)=n→∞limk=1∑nP(Dk)=n→∞limP(An).若事件递减,德摩根(De Morgan)律给出 Anc↑Ac;应用递增情况,再用 P(An)=1−P(Anc),便得结论。此补集证法用到 P(Ω)=1 为有限数;一般无限测度若没有有限测度的假设,未必有由上连续性。
证明透视
嵌套与有限总质量用在哪里
从下连续性的证明只用到可数可加性,而嵌套只用了一次:因为 An−1⊆An,差集 Dn 两两不相交,而且前 n 个重新拼成 An。关键一步是把 P(An) 看成非负项级数的部分和,于是极限存在,并等于全和,即 P(A)。没有嵌套就没有这种拆分,下面的反例说明此时任何极限结论都不再成立。
从上连续性借助补集化为递增情形,而 P(Ω)=1 正是在这一步使用:恒等式 P(An)=1−P(Anc) 需要有限的总质量。在实数轴的长度测度下,集合 An=[n,∞) 递减到空集,但每个的长度都是无穷大,所以那里从上连续性不成立。
假设各次试验互相独立,第 n 次成功概率为 pn,容许它随 n 改变。令 An 为前 n 次至少成功一次。其补集是连续 n 次失败,因此
P(An)=1−k=1∏n(1−pk),P(最终成功)=1−n→∞limk=1∏n(1−pk).乘积介于零与一之间且递减,所以极限存在。若各次成功概率固定为 p>0,乘积极限为零,最终成功的概率是一。这并不提供一个确定的最后期限:当 0<p<1,任何有限 n 的连续失败概率 (1−p)n 仍为正。
概率为一的事件不一定就是整个样本空间。在无限次公平掷硬币模型中,全部都是反面的序列是可能的结果,但其概率对每个 n 都不超过 2−n,故为零。“几乎必然”容许例外结果,并不代表这些结果在逻辑上不可能。
递减事件的结果也是收敛模式与强大数定律一篇中极限论证的基础。Borel–Cantelli 引理一篇则利用上极限事件,处理另一个问题:事件是否发生无限多次。
可数个事件的界
对任意事件 B1,B2,…,
P(n=1⋃∞Bn)≤n=1∑∞P(Bn).右边可以是无穷大;不需要独立性。
令 C1=B1,Cn=Bn∖k<n⋃Bk。这些事件互不相交,并集与 Bn 的并集相同,且 Cn⊆Bn。可数可加性及单调性便给出上界。
对补集应用此上界,也得到
P(n≥1⋂Bn)≥1−n≥1∑P(Bnc).
若右边是负数,这个下界便没有比概率非负更有用。若每个 Bn 的概率都是一,交集的概率也是一。“可数”不可省略:若 U 在 [0,1] 上均匀分布,每个事件 {U=x} 的概率均为一,但对所有 x∈[0,1] 取交集却得到空集。
反例模式
概率的极限并不足够
在 [0,1] 上取均匀概率,令 A2n−1=[0,1/2],A2n=(1/2,1]。所有 P(An)=1/2,但 n⋃An=[0,1] 的概率是一,n⋂An=∅ 的概率则是零。连续性定理要求事件互相包含,不只是概率收敛。
精确计算重叠
对有限个事件 B1,…,Bm,
P(i=1⋃mBi)=∅=I⊆{1,…,m}∑(−1)∣I∣+1P(i∈I⋂Bi).
首先加上各事件的概率,再减去两两交集,加回三重交集,如此类推。
固定一个恰好属于 r 个事件的结果。若 r=0,两边的贡献都是零;若 r≥1,右边的系数为
j=1∑r(−1)j+1(jr)=1,这是二项式恒等式 (1−1)r=0 的结果。因此相应的示性函数恒等式对每个结果成立;对这个有限和取期望便得所示公式。
公式不需要独立性,但交集概率必须依照所给模型计算。要换成无限交错级数,则须另外论证收敛性。
从三个有标号的对象的六个排列中均匀选一个。令 Bi 为第 i 个对象留在原位的事件。每个 P(Bi)=2/6,每个两两交集及三重交集的概率都是 1/6。因此
P(B1∪B2∪B3)=362−361+61=32.其余两个排列没有不动点。这三个事件并不独立:知道两个对象留在原位,第三个便必然留在原位。
对 n 个有标号对象的均匀随机排列,令集合 I 中每个对象都留在原位,剩下 (n−∣I∣)! 个排列,所以 P(i∈I⋂Bi)=(n−∣I∣)!/n!。大小为 j 的集合有 (jn) 个,而 (jn)(n−j)!/n!=1/j!。因此容斥原理给出
P(i=1⋃nBi)=j=1∑nj!(−1)j+1.n=4 时,这是 1−21+61−241=85,即 24 个排列中有 15 个有不动点,9 个没有。若只计前两组和,会得到 1/2,并不是答案:有限公式的每一项都不可少。n=3 时,公式给出上例的 2/3。
在三个对象的例子中,把各自的概率相加得 3⋅31=1,等于断言每个排列都有对象留在原位。两个循环排列没有不动点;正确值 2/3 已减去重叠部分。和 i∑P(Bi) 只是上界;只有当所有两两交集的概率均为零时,它才等于并集的概率。
练习
快速检查
(在 [0,1] 的均匀概率下,令 An=(0,1/n)。找出交集,并用由上连续性计算其概率。)
解答 · 答案
交集是空集:任何 x>0 最终会大于 1/n,而零从未包含在内。事件递减且 P(An)=1/n→0,由连续性得概率零。
快速检查
(事件 En 满足 P(En)≤2−n−1,其中 n≥1。求至少一个发生的概率上界及一个也不发生的概率下界。是否需要独立性?)
解答 · 答案
几何级数之和为 1/2。并集界给出 P(⋃En)≤1/2,故其补集概率至少为 1/2;不需要独立性。
快速检查
(三个事件满足 P(Bi)=1/2,所有两两交集概率都是 1/4,三重交集概率为 1/8。求至少一个发生的概率。计算是否用到独立性假设?)
解答 · 答案
容斥给出 3/2−3/4+1/8=7/8。所提供的交集概率已足够;公式本身不假设独立性。
快速检查
(独立试验中第 n 次的成功概率为 pn=1/(n+1)。求前 n 次均未成功的概率,以及最终成功的概率。)
解答 · 答案
乘积消去后得 k=1∏nk/(k+1)=1/(n+1)。由连续性,永不成功的概率是零,故最终成功的概率是一;每个有限时刻的失败概率仍为正。