LeoMath

概率论基础 · 第 1 / 3 节

概率空间

样本空间、事件与三条公理;生日问题为什么反直觉。

约 12 分钟

从一个问题开始

问题

一个 30 人的班级里,至少有两个人同一天生日的概率有多大?

多数人的第一反应是:一年有 365 天,30 个人才占了不到十分之一,概率大概只有 8% 左右。

真实答案超过 70%。直觉错得这么远,说明我们还没有说清楚"概率"到底在算什么:所有可能的结果是什么?"至少两人同一天"对应其中哪一部分?"可能性"又按什么规则相加?这三个问题的答案,合起来就是概率空间。

观察

先玩再读。拖动人数 n,黑色曲线是理论概率;再按"模拟",一次随机生成一整个班的生日,红点是到目前为止的频率。人数到多少时,概率第一次超过一半?

交互实验生日问题
  • 至少两人同一天
  • 指数下界1−e−n(n−1)/730
  • 有人和第一个人同一天
1−365⋅364⋯(365−n+1)365n对数 253精确值 0.507297指数下界 0.500002有人和第一个人同一天 0.058571
已模拟班级 0有人同一天 0频率 —

你观察到了什么?先动手,再回答。想清楚之后再看解释。

  1. 1.人数从 10 拖到 60,曲线在哪一段涨得最快?至少多少人时概率超过一半?
  2. 2.n = 23 时,“两人同一天”的概率约 50%,可“有人和第一个人同一天”只有约 6%。两者差在哪里?
  3. 3.只模拟 10 个班,频率和理论值差多少?模拟 1000 个班之后呢?
猜想

曲线涨得比人数快得多,因为可能撞上的不是"人",而是"对"。n 个人有 (n2)=n(n−1)2 对,23 人就有 253 对,每一对撞上的机会是 1365。对数按 n2 增长,所以不需要接近 365 人,二十几个人就够了。

要把这个猜想变成可以证明的结论,先得有一个精确的框架。

定义

定义 1.1样本空间与事件

随机试验所有可能结果组成的集合 Ω 称为样本空间,其中的元素 ω 称为样本点。Ω 的子集称为事件。试验结果 ω∈A 时,称事件 A 发生。

事件就是集合,所以集合运算就是事件的逻辑:A∪B 是"A 或 B 发生",A∩B 是"A 与 B 同时发生",Ac=Ω∖A 是"A 不发生"。A∩B=⌀ 时称 A,B 互斥。

例 1.1生日问题的样本空间

把 n 个人依次编号,每个人的生日是 {1,…,365} 中的一天。一个样本点是一个有序的 n 元组 ω=(d1,…,dn),所以

Ω={1,…,365}n,|Ω|=365n.

"至少两人同一天"是事件 A={ω: 存在 i≠j, di=dj};它的补事件 Ac 是"n 个生日两两不同"。

定义 1.2概率(Kolmogorov 公理)

设 Ω 是有限或可数集。函数 P 把每个事件 A⊆Ω 对应到一个实数 P(A),若满足

  1. 非负:P(A)≥0;
  2. 规范:P(Ω)=1;
  3. 可列可加:若 A1,A2,… 两两互斥,则 P(⋃iAi)=∑iP(Ai),

则称 P 为概率,(Ω,P) 为概率空间。

公理只说概率满足什么,不说某个事件的概率等于多少。数值要由模型给出。最简单的模型是"每个结果一样可能":

定义 1.3古典概型

若 Ω 有限,且每个样本点的概率相等,则对任意事件 A,

P(A)=|A||Ω|.

于是古典概型里的概率问题就变成了计数问题:数清 A 里有多少个样本点。

定理与证明

公理只有三条,但常用的性质都能从它们推出来。

定理 1.1概率的基本性质

对任意事件 A,B:

  1. P(⌀)=0;
  2. P(Ac)=1−P(A);
  3. 若 A⊆B,则 P(A)≤P(B);
  4. P(A∪B)=P(A)+P(B)−P(A∩B)。
证明

(1) 取 A1=Ω,A2=A3=⋯=⌀,它们两两互斥,由可列可加性 P(Ω)=P(Ω)+∑i≥2P(⌀),所以 ∑i≥2P(⌀)=0;每一项非负,只能 P(⌀)=0。

有了 (1),可列可加性对有限个互斥事件也成立(后面补上空集即可)。

(2) A 与 Ac 互斥,并起来是 Ω,所以 P(A)+P(Ac)=P(Ω)=1。

(3) B=A∪(B∖A),两部分互斥,所以 P(B)=P(A)+P(B∖A)≥P(A)。

(4) A∪B=A∪(B∖A) 且 B=(A∩B)∪(B∖A),两处都是互斥并。于是 P(A∪B)=P(A)+P(B∖A)=P(A)+P(B)−P(A∩B)。

性质 (2) 看似平凡,却是生日问题的钥匙:"至少两人同一天"情况繁多(两人撞、三人撞、两对各自撞……),而它的补事件"两两不同"只有一种情况,好数得多。

命题 1.2生日问题

在古典概型下(n≤365 个人,生日独立且均匀地落在 365 天中),

P(至少两人同一天)=1−365⋅364⋯(365−n+1)365n=1−∏k=1n−1(1−k365).
证明

数补事件 Ac 的样本点:第 1 个人的生日有 365 种选法,第 2 个人要避开前一个,有 364 种,……,第 n 个人有 365−n+1 种。所以 |Ac|=365⋅364⋯(365−n+1)。由古典概型 P(Ac)=|Ac|/365n,再由性质 (2) 得 P(A)=1−P(Ac)。第二个等号只是把每个因子写成 365−k365=1−k365。

代入 n=23 得 0.5073,n=30 得 0.7063。公式是精确的,但看不出"为什么是二十几"。把乘积换成指数,结构就出来了。

引理 1.31 − x ≤ e^{−x}

对所有实数 x,1−x≤e−x,等号当且仅当 x=0。

证明

令 g(x)=e−x−(1−x),则 g(0)=0,g′(x)=1−e−x。x>0 时 g′>0,x<0 时 g′<0,所以 g 在 x=0 取到最小值 0。这就是 e−x 的Taylor 展开只取前两项时的误差符号:曲线永远在切线上方。

推论 1.4二十三个人就够了
P(至少两人同一天) ≥ 1−exp⁡(−n(n−1)2⋅365).

特别地,n=23 时概率超过 12。

证明

对每个因子用引理:1−k365≤e−k/365。所有因子都是正数,相乘得

∏k=1n−1(1−k365)≤exp⁡(−1+2+⋯+(n−1)365)=exp⁡(−n(n−1)730).

取补即得不等式。n=23 时 23⋅22730=506730≈0.693151>ln⁡2≈0.693147,所以右边大于 1−12=12。

指数里恰好是对数 (n2) 除以 365:猜想说的就是这件事。要让概率达到一半,需要 (n2)≈365ln⁡2,也就是 n≈2⋅365ln⁡2≈22.5。人数只需要天数的平方根量级。

常见错误

"有两个人同一天生日"和"有人和我同一天生日"是两个不同的事件。后者只涉及 n−1 对(我和其他每个人),概率是 1−(364365)n−1,23 人时只有约 5.9%;除我之外还要有 253 个人,才能过半。直觉给出的 8% 其实是在回答后一个问题。在实验里看那条点线:在 n=23 附近,它比黑色曲线低了将近十倍。

注

古典概型假设生日在 365 天中均匀分布,而真实生日并不均匀(有季节差异)。可以证明:只要生日仍然相互独立、一年仍按 365 天算,在所有可能的分布中,均匀分布给出的撞上概率最小,对每个 n 都是如此。所以在这个模型里,上面的数值是下界,结论只会更强。(双胞胎会破坏独立性,2 月 29 日会让一年多一天,这些都不在模型里。)

应用

应用哈希碰撞与生日攻击

一个输出 m 位的哈希函数有 d=2m 种可能的值。把"天数"换成 d,同样的推导说明:只要随机试大约

n≈2dln⁡2≈1.18⋅2m/2

个输入,就有一半的机会找到两个哈希值相同的输入。对 64 位哈希,这只要五十亿次左右,而不是 264 次。所以 m 位哈希抵抗碰撞的强度只有 m/2 位:想要 128 位的安全性,输出就得有 256 位。

用函数绘图器试一试 →

在绘图器里画 1−exp⁡(−x(x−1)/730),再把 730 换成 2d 试试不同的"天数":曲线的形状几乎不变,只是横向近似按 d/365 伸缩。

注

这一节只用到了"数样本点"。可是很多问题里,我们会先得到一部分信息,再问概率:已知检测结果呈阳性,真正患病的概率是多少?信息改变了样本空间,这就是下一节条件概率与 Bayes 公式要回答的问题。

生日问题实验的思路参考:github.com/huzhuofan1020-svg/GDGX

练习

已完成 0 / 4

1
掷两颗均匀骰子,点数之和为 7 的概率是多少?(可以填分数)

可以填小数或分数;与标准答案相差不超过 0.001 即判对。

2
已知 P(A)=0.5,P(B)=0.4,P(A∪B)=0.7。求 P(A∩B)。

填精确值,可以写成分数,如 1/3。

3
3 个人中至少两人同一天生日的概率是多少?(按 365 天均匀计,保留四位小数)

可以填小数或分数;与标准答案相差不超过 0.00006 即判对。

4
一个 23 人的班里,有人和你同一天生日(你是其中之一)的概率约为?
第 4 题的答案

讨论

发现错误、有疑问或建议,也可以直接写信到 620026600@qq.com

还没有评论。写下你的理解、疑问,或者指出这一页的错误。

登录后参与讨论