第17章 事件和概率空间
17.1 做个交易吧
假设你有三扇门可供选择。其中一扇门背后是一辆汽车,另外两扇门背后是一只山羊。你选择了一扇门,比如1号门。然后知道门后面有什么的主持人,开启了另一扇后面有山羊的门,假设是3号门。现在,你有一次转换选择的机会,我们想知道现在转换选择是否有利?
17.1.1 理清问题
我们对以上问题做出如下假设:
- 这辆车被等可能地藏在三扇门后。
- 不管车在哪扇门后,选手等可能地选择三扇门中的任意一扇。
- 当选手选择了一扇门之后,主持人必须打开不同于选手所选的藏着羊的一扇门,并提供选手改变选择或坚持原来选择的机会。
- 如果主持人可以在藏着羊的门中进行选择,则主持人等可能地选择一扇门打开。
17.2 四步法
在本节中,我们对于“什么的概率是多少”这样的问题,介绍一种四步法。在这种方法中我们逐步建立一个概率模型,并根据该模型形式化原始问题。
17.2.1 步骤一:找到样本空间
我们的第一个目标是确定实验的所有可能结果。一个典型的实验通常涉及几个随机确定的量。例如,在蒙特霍尔问题中就涉及如下三个量:
这些随机确定的量的每一种可能的组合称为一次结果。所有可能结果的集合称为该实验的样本空间。
为了表示方便,我们把每个结果标记为门的三元组,其中三个门分别用A,B,C表示:
那么样本空间就是:
此外,我们可以用树状图表示样本空间。第一层、第二层、第三层分别表示车的位置、选手最初的选择、主持人打开的那一扇门。
17.2.2 步骤二:确定目标事件
结果的集合称为事件。
现在我们真正关心的是事件[选手转换选择从而赢得奖品]:
对于这种结果,我们用对钩表示:
刚好一半结果有对钩,但是选手转换选择赢得奖品的概率并不是1/2。因为这些结果并不是等概率发生的。
17.2.3 步骤三:确定结果的概率
到此为止,我们已经列举了实验的所有可能结果。现在我们必须开始评估这些结果的可能性。具体来说,这一步的目标是为每个结果分配概率,即这个结果期望发生的次数占总次数的比例。所有结果的概率之和一定等于1,这表示实验总是必须有一个结果。
步骤3a:分配边的概率
首先,我们在树状图的每条边( edge )上记一个概率。这些边的概率取决于我们最初做的假设。
步骤3b:计算结果的概率
下一步是将边的概率转化成结果的概率。将从根节点到结果叶子节点路径上的概率值相乘,得到这个结果的概率。
计算每个结果的概率就是定义一个从结果到概率的映射函数。这个函数通常记作Pr[·]。所以有:
17.2.4 步骤四:计算事件的概率
现在,我们知道了每个结果的概率,但我们还要知道事件的概率。事件E的概率记作Pr[E],即E中所有结果的概率之和。
17.2.5 蒙特霍尔问题的另一种解释
那么,Marilyn真的正确吗?我们的分析表明她是对的。不过更准确的说法是:在我们接受她对这个问题的解释的前提下,她的回答是正确的。这个问题还有一种解释,在这个解释下,Marilyn的答案是错误的。
17.3 奇怪的骰子
有三个奇怪的骰子,虽然每个骰子都有六个面,但同一个骰子的对立面上的数字相同,并且不同骰子上的数字不同,如图所示。
你选择骰子B,而你的对手选择骰子A,让我们算一下你赢的概率是多少?
17.3.1骰子A vs.骰子B
步骤1:找到样本空间
对于这个实验,样本空间包含9个结果:
步骤2:定义目标事件
我们感兴趣的事件是骰子A的数字大于骰子B的数字。这个事件由5个结果组成:
步骤3:确定结果的概率
不管哪个骰子,每个骰子上每个数字出现的概率都是1/3。所以每个结果的概率是1/9。
步骤4:计算事件的概率
事件的概率是该事件所有结果的概率之和。这里,所有结果的概率都相同,所以我们说样本空间是均匀的。计算均匀样本空间的事件概率尤其简单,只需要知道事件的结果数目。
17.3.2 骰子A vs.骰子C
如果你选择骰子A而你的对手选择骰子C呢?
经过四步法分析后,我们都到骰子C战胜骰子A的概率是5/9。
17.3.3骰子B vs.骰子C
现在我们已经知道了骰子C很可能战胜骰子A,而且骰子A很可能战胜骰子B,所以骰子C当然是最好的。当我们选择骰子B时,会有很大的可能赢得骰子C。
但是事实并不是这样的,经过四步法画树状图之后,我们发现骰子B有5/9的概率战胜骰子C。
为什么会出现这种情况呢?问题并不出在数学上,而是出在你的直觉上。因为A更可能战胜B,B更可能战胜C,所以看起来A应该更可能战胜C,也就是说,“更可能战胜”的关系应该是可传递的。但是,这个直觉是错误的。
17.3.4掷两次
如果每个玩家掷两次,树状图将会有四层—34=813^4 = 8134=81个结果。如下图:
每个结果的概率是(1/3)4 =1/81,所以这又是一个均匀的概率空间。
经过计数,我们得到满足A之和大于B之和的对数有37个,满足B之和大于A之和的对数有42个,满足A之和等于B之和的对数有两个。
也就是说B更可能赢,为什么掷一次的时候A比B更可能赢,而掷两次B更可能赢呢?事实上,无论选择哪两个骰子,骰子的优势都发生了改变。
所以,对于一次投掷,
而对于两次投掷,
我们用>和<来表示哪个骰子更可能得到更大的点数。
以上三个奇怪的骰子的怪异行为可以推广为:存在任意大的骰子集合,根据投掷次数不同,它们以一定的模式相互战胜。
17.4 生日原理
班上有95名学生。请问有两人是同一天生日的概率是多少?95名学生、365个可能的生日,你可能会猜测概率大概在1/4左右——但你错了:班级中有两人是同一天生日的概率超过0.9999。
17.4.1匹配概率的确切公式
设人数为n,不同的天数为d。则一共有dnd^ndn种序列,且这些序列是等可能的。共有d(d-1)…(d-(n-1))个不同的生日序列,则大家生日不同的概率为
当n = 95,d = 365时,式17.7的值小于1/200 000,这意味着有两人的生日相同的概率实际上大于1-1/200 000 > 0.99999。所以,班上没有学生的生日相同才是令人震惊的事情。
生日原理:
如果一年中有d天,一个房间中有2d\sqrt{2d}2d个人,那么房间中有两人生日相同的概率约为1-1/e = 0.632。
在其他应用领域,这意味着当你用一个散列函数将n个项目映射到大小为d的散列表时,如果n2大于d的一小部分,将会遇到很多冲突。此外,生日原理也因“生日攻击”而著名,它用于破解某些加密系统。
17.5集合论和概率
17.5.1 概率空间
定义17.5.1: 一个可数的样本空间S是一个非空可数集。样本空间中的元素w∈ S称为结果,S的子集称为事件。
定义17.5.2:在样本空间S上的概率函数是一个全函数 Pr: s →R,其满足
样本空间和概率函数一起称为概率空间。对于任意事件E⊆8,E的概率定义为其中结果的概率之和:
17.5.2 集合论的概率法则
由两个不相交事件E和F的事件概率定义,可以直接推导得,
法则17.5.3:(加和法则)设E0,E1 … ,En…是两两不相交的事件,那么,
两个事件的容斥原理等式同样可以推广到任意n个可数事件的集合。同理,布尔不等式也可以推广到有限或无限可数事件的集合。
法则17.5.4(并集的上界)
17.5.3 均匀概率空间
定义17.5.5给定有限的概率空间s,如果对每个o ∈ S来说,Pr[o]都相等,那么这个概率空间是均匀的。
这意味着一旦知道了E和S的基数,马上就可以得到Pr[E]。
17.5.4无穷概率空间
无穷概率空间很常见。例如,两名玩家轮流抛一枚公平的硬币。先抛得正面者胜。第一位玩家胜的概率是多少?这个问题的树状图如图17.10所示。
样本空间是无穷集:
其中TnT^nTn表示n个T字符串。概率函数是
要验证这是一个概率空间,只需检验所有的概率是非负的并且它们的和为1。所有已知的概率都是非负的,再利用几何级数求和公式,我们得到