15 Who Knows What It Looks Like, But It Exists. The Probabilistic Method
The Notion of Probability
扔一个硬币四次，想知道至少三次正面（头）朝上的概率。结果一共有种，关心的结果的数量是五种，分别是。那么至少三次正面向上的概率就是关心的结果个数比上总的结果的个数，。这个形成概率概念的常识性做法，当然，稍微有点不严谨，比如没有说硬币是公平的，正面和反面向上的概率是相同的。
Definition 15.1. 令是实验的某些序列的结果的有限集合，各个结果的发生是等概率的。令，那么称为样本空间(sample space)，是事件(event)，那么比率
是事件的概率。
是定义在的所有子集的结合上的函数，取值范围是。
当是无限集合的时候，这个定义是无意义的。这里我们只讨论有限集合的概率问题。
如果是的不相交子集，并且，因此。一般地，，蕴含。进一步泛化可以得到下面这个简单但是有用的不等式。
Proposition 15.2. 令来自同一个样本空间，那么
Proof. 上式等价于
左边对于至少属于其中一个的样本空间的元素只计数了一次，而右边至少计数了一次。
三至七章有大量排列组合的例子和练习，它们能很容易的转化成概率的例子和练习。比如有多少个六位数包含数字6，可以变成随机取一个六位数字，包含6的概率是多少。所以这里就不再讨论这些基础问题。这一小节给出两个反直觉的例子。
Example 15.3. 彩票游戏。从36个数字中选择6个，至少选中一个中奖数字的概率是多少？
Solution. 令表示至少选中一个中奖数字，表示不包含中奖数字。很明显，是不相交的，且，所以。因此我们计算的概率即可，事件是从30个数字选择6个。
所以任意选择六个数字，至少有一个中奖数字的概率接近百分之七十。
如果是不相交的，我们称之为互斥(mutually exclusive)。也就是说，不可能同时发生。在此基础上，如果，那么是的补集(complement)，记作。
Example 15.4. 某个聚会上有四十个人，没有人是二月二十九号出生的。Adam向Bill提意玩一个游戏，每一个客人写下出生的月份和天，如果两个人是同一天则Adam赢，否则Bill赢。Bill看了看，只有四十个人，比一年的天数小多了，觉得自己会赢。实际情况呢？
Solution. Bill没有分清百分百会发生和大于百分之五十会发生。如果一定赢，那么需要366个人，但是超过一半的机会是完全不同的问题。
下面会证明至少需要23个人，Adam大概率会赢，否则Bill会赢。
至少有两人在同一天生日的补集是没有两个人的生日在同一天。第一个人可以是任意一天出生，365个可能性，第二个人不能是同一天，364个可能性，依此类推。23个人可能总数是。所有可能的结果集有。所有没有任何两个人的生日在同一天的概率是
所以超过一半的可能性是存在两个人的生日在同一天。 w
我们为什么要排除二月二十九号呢？因为这一天和其他天不等概率，闰年才会有这一天，几率是其他天的四分之一（近似）。那么为了使得样本空间是等概率的，需要考虑四年，天作为整个样本空间，使得论证过程会复杂很多。
上面这个例子有时被称为生日悖论(birthday paradox)。
Non-constructive Proofs
如果一个盒子里面装者一些球，随机挑一个是蓝球的概率大于0，那么至少有一个蓝球。这个看似简单实则很有用的。
第十三章提到了Ramsey number，如果我们用两种颜色对个点的完全图染色，总能找到一个完全子图是同色的。
下面要证明下界。这个命题是说对个顶点的完全图染色，可能不存在一种染色能够找到一个同色的完全子图。第十三章的证明了，明确找出了不符合题意的图。但是回到这个问题上，不需要这么严格。只需要证明上述所阐述的存在性即可，而不需要找到这样一种染色。
Theorem 15.5. 对所有正整数，不等式都成立。
Proof. 令，对按照如下方式染色：对于每条边而言，通过掷硬币的方式，如果正面向上染成红色，否则染成蓝色，每条边是红色或者蓝色的概率都是二分之一。我们将会证明没有同色完全子图的概率是大于0的。，是个顶点的完全图进行二染色的集合，意味着至少有一个二染色的完全图不包含同色完全子图。
我们会通过证明来证明。前者的意思是对随机染色，至少有一个同色完全子图的概率。
将中的子图二颜色的方式有}，其中有两个是同色的。所以随机对其染色是同色的概率是
有
个。每一个都有可能包含同色的子图。根据Proposition 15.2这些子图中至少有一个同色子图的概率最多是这些可能性之和。如果用表示的子图是同色的，那么
代入
最后一步使用递归法很容易证明。
第十三章证明了，这里证明了。基本上这是已知的Ramsey numbers最好的范围了。
Theorem 15.6. 令是大于1的正整数，并且。对进二染色，没有同色边的是可能的。
Proof. 对进行二颜色的方式有种，其中两种是单色的。那么至少有一个同色子图的概率最多是^2 2^{1-m^2}，我们需要证明
也就是
插入两个中间表达式
中间的不等式用到的就是题目中的关系。
可以从另一个角度来解读这个问题。如果，那么存在一个元素是零或一的的矩阵，没有的子矩阵只包含零或者只包含一。
事实上，前面的证明只是存在性，没有找到这么一个染色，对应到这里，我们不知道怎么构造这个矩阵来满足要求。换句话说，知道是可能的和知道怎么到之间有巨大的鸿沟。目前已知的当时来构造满足要求的矩阵。但这距离我们证明为真的命题之间也就很大的距离。
Independent Events
The Notion of Independence and Bayes' Theorem
扔两个骰子。表示第一个骰子是六这个事件，表示第二个骰子是六这个事件，那么，可以看出来，这是个巧合吗？从中任选一个数，表示该数能被2整除，表示概述能被3整除，表示该数能被4整除。那么，接着可以计算得到，看似乘积关系依旧成立。但是。
为什么有时但是有时？因为有的时候的发生增加或者减少了发生的概率，有的时候对没有影响。回到前面从12个数中选择一个的问题。能被2整除增加了能被4整除的概率。全集从12个减少为6个，但是能被4整除的结果集个数没有变化。相反，能被2整除对能否被3整除没有影响。全集从12个减少到了6个，同时，能被3整数的结果集的个数也有相应的减少（从4个到2个）。
Definition 15.7. 如果事件来自同一样本空间，有，那么称为独立事件(independent events)，否则是非独立事件(dependent)。
Definition 15.8. 令事件来自同一样本空间，且假设，有
是条件概率(conditional probability)，表示给定事件发生的前提下发生的概率。
Proposition 15.9. 事件是独立事件等价于成立。
换句话说，事件是独立的等价于的发生不会使得更容易或更不容以发生。
Example 15.10. 连续扔四次硬币。看不最后的结果，只知道至少有两次正面向上，问四次都向上的概率是多少？
Solution. 令表示四次正面向上，表示至少两次正面向上，那么。所以。每次扔掷硬币正面向上的概率是二分之一，所以。有的几率四次正面向上，的几率三次正面向上，的几率两次正面向上，所以。。
Example 15.11. 令是一个随机挑选的排列。令事件是，事件是。计算，是否是独立事件？
Solution. 明显。是，概率是六分之一。因此
所以不是独立事件。
你的第一反应明显不是独立事件，因为如果成立的话，那么较小，所以成立的可能性会小一些。当处理条件概率时利用直觉的话一定要小心。比如下面这个例子就和直觉相悖。
Example 15.12. 一个大学两个学院，人文学院和工程学院，两个学院统计上学年申请人的情况，都是国内学生的入学比例比国际学生的高。那么对于整个大学而言，国内学生入学比例比国际学生高吗？
Solution. 答案是不能。比如下表就是个反例。
| |Liberal Arts|Engineering|Entire University|
|--|--|--|--|
|Domestic
applicants|Admitted: 10
Applied:120
success rate:8.3%|Admitted: 10
Applied:10
success rate:100%|Admitted: 20
Applied:130
success rate:15.9%|
|International
applicants|Admitted: 1
Applied:15
success rate:6.7%|Admitted: 90
Applied:100
success rate:90%|Admitted: 91
Applied:115
success rate:79.1%|
这个反例是著名的辛普森悖论(Simpson's paradox)。对工程学院而言，虽然国内学生入学比例高，但是国际学生占比非常高，国内学生的申清者只占全校国内学生申清总数的8%，国际学生的申请者占全校国际学生申请人数的85%以上。而人文学院恰恰相反，并且国际学生的申清人数很少，不会对国际学生的入学比例有大的影响，而国内学生的申清总数很大，入学比例低，一下子就大大减少了国内学生申清成功的比例。
下面的贝叶斯定理可以给出更精准的解释。
Theorem 15.13 (Bayes' Theorem). 令是互斥事件，那么。令为任意事件，那么
也就是说的概率是条件概率的加权平均数。
Proof. 由于互斥，那么和不相交，又因为，它们的并集就是。因此
上式右边的第一项（第二项）和要证明的等式右边的第一项（第二项）是相等的，就是条件概率的公式。
现在我们可以对前面的辛普森悖论有更深的理解了。令表示事件——国际学生申请人文学院，表示国内学生申请人文学院，类似的表示申请工程学院，表示国际学生、国内学生申请整个大学。根据Theorem 15.13
要求国内学生有更大的机会被任何一学院录取的标准确保了。但是对任意（是的补集，是的补集）而言，命题能不成立呢？我们可以选择对非常有利且对非常不利。怎么选择呢？如果很大，选择一个很大的，反之很小的话，可以选择一个很小的；选择也类似。
换句话说，加权平均值比非加权平均值难控制的多。事实上，如果要求，甚至只要求，那么对于整个大学而言，国内学生的入学比更高。
Example 15.14. 假设有两个人和，其中一人是罪犯。现在知道犯罪分子是特殊的型血，人群中有百分之五的人是型血。如果是这种血型，那么是犯罪分子的概率是多少？
Proof. 令表示对应犯罪嫌疑人是犯罪分子。表示是型血。那么
获得血型信息之前，。如果是犯罪分子，那么肯定是型血，所以。如果是犯罪分子，是型的概率是1/20，所以。根据Bayes' Theorem
所以
所以如果附加了血型信息，那么是犯罪分子的概率是20/21。
上面的例题中的方法非常有用。我们需要计算，直接计算不容易，但是反转条件，是容易确定的，那么我们可以利用等于，也等于。
习题34也是类似的，是Bayes' Theorem的典型应用场景，解决一个乍看不容易的问题，结论是很重要的，而且反直觉。
More Than Two Events
定义三个或多个事件相互独立不是显而易见的事情。可以类似的给出一个需要满足的等式。如果，不管其他事件多么的相互依赖，等式都成立。为了有一些局部信息，可以强加要求，但是考虑下面的情况。
表示从随机选出一个奇数，表示从随机选出一个奇数，表示两次选出来的数差值是奇数。
不难证明，并且两两独立。但是，因此，我们也不想称这些事件相互独立。
通过一个更强的要求：事件的任意子集都相互独立来解决上述的问题。
Definition 15.15. 我们称是相互独立的，当对于任意非空子集都有
Theorem 15.16 (Bayes' Theorem, General Version). 假设是同一样本空间的事件，有，并且。令是任意事件 Proof. 证明类似于Theorem 15.13。
一个著名的使用泛化版本的例子是三门问题(Monty Hall problem)。给出三个门，竞猜者选择一个自认为有大奖的一个，其余两个门里面是羊。一旦竞猜者做出了选择，主持人（知道三个门背后的东西）选择一个是羊的门打开，然后问竞猜者是否要更换选择。
一个直观的想法是只有两个门，一个是羊，一个是大奖，换不换都一样，都是二分之一的概率选中。
这个想法是错的。没有任何信息的情况下选择正确的概率是1/3，错误的概率是2/3，排除一个错误答案之后，选择不变就还是1/3的几率，变相当于选择到对立面，2/3的概率赢得大奖。
从数学角度严格求解。令表示大奖在门的后面。不妨设竞猜者选择的一号门，主持人打开了二号门（不妨令其为事件）。我们需要计算的是，就是主持人打开了二号门不换选择能够得到大奖的几率。
显然。如果一号门是大奖，那么主持人可以选择二号门或者三号门，所以，如果二号门后面是大奖，主持人不能开二号门，所以，如果三号门是大奖，主持人不得不开二号门，因为一号门已经被竞猜者选择了，所以。代入上面的式子得到
选择不变只有1/3的几率得到大奖，所以选择改变选择比较好。
Expected Values
随机变量(random variable)是定义在样本空间上的函数(function)，范围是实数的一个集合。比如，是所有个带标签的点组成的图的集合，我们可以通过令是的边的数量来定义随机变量，也可以通过令是的连通分量的个数来定义随机变量。
在同一个样本空间上，我们可以定义随机变量的和与积，。
或许最有用的随机变量参数是期望值(expected value)，也被称为期望(expectation)，平均值(average value or mean)。
Definition 15.17. 令是随机变量那么集合是有限的，也就是说只能取有限多的值。那么
是期望值，或被称为在上的期望。
这里是事件的概率，即
换句话说，是所有取值的加权平均数，这里的权重是取对应值的概率。
这就蕴含了
注意：一些随机变量可以定义在许多不同的样本空间上。比如之前的例子，图的边数，可以定义在所有个顶点的图上，也可以是所有个顶点的连通图上，甚至可以是所有至多个顶点的图上，等等。对于每个例子，是不同的，那么的期望也是不同的。因此，如果有含糊的可能性，我们写作以示区别，否则简写作。
有时我们一句话同时说明，比如，令是随机选择一个个顶点的连通图的边数。这里的是所有个顶点的连通图，是任意一个图的边数。
当是无穷集合时，在某些情况下也能定义的期望。如果是可数无限集，只要无穷求和存在，就可以定义。如果不可数，需要用积分替代求和。
Definition 15.18. 对所有的，随机变量是独立的(independent)，那么下面等式成立。
Linearity of Expectation
对于任意实数，通过令来定义随机变量。在计数组合学中，下面这个看似普通的定理非常有用。
Theorem 15.19.
(1) 令上有两个随机变量，那么
(2) 令是一个随机变量，实数，那么
所以“取期望值”是线性操作。这个定理不要求是独立的。不管它们之间多么交错复杂，不管它们多么难以计算，的期望值都能通过这个简单的公式计算得到。这也是为什么这个定理是最用的期望相关的属性，同时可以用于很多问题。
Proof.
(1) 根据，
(2) 类似地，
这个证明依赖于公式，要求的每个事件是等概率的。但是Theorem 15.19是不要依赖这个条件的。
Proof.
(1) 令随机变量有正数概率的值有，有正数概率的值有，那么
(2) 令，根据定义，取值，那么。因此
令是排列，如果，即小于两边的元素，那么称之为谷(valley)。
Theorem 15.20. 令，随机选择一个长度为的排列，平均而言，有个谷。
如果不使用Theorem 15.19，我们必须要对于每个计算有个谷的排列数量（这一步是困难的），然后计算。而应用Theorem 15.19的话，小菜一碟。
Proof. 取个随机变量。对某个排列，如果是谷的话，，否则。对于每一个而言，有三分之一的几率是谷，即是集合中最小的。所以
定义，那么表示的谷的个数。
类似于随机变量，如果某个事件发生则指为1，否则为0，被称为指示随机变量(indicator (random) variables)。
Theorem 15.21. 随机选择一个排列的固定点的个数的期望值是1。
Proof. 定义个随机变量。对于一个排列，令如果，即在位置处有一个固定点，否则。
是随机的从选取一个值，所以有的可能性它的值是。因此
定义，那么就表示的固定点的个数。应用Theorem 15.19求期望
Existence Proofs Using Expectation
平均数不会比集合中最大的数大，同理，加权平均值也不会比集合中的最大值大。
Theorem 15.22. 令是随机变量，集合是有限集合，是中最大的元素，那么
Proof. 运用定义
Theorem 15.23. 令是简单图，个顶点，条边。包含一个超过条边的二分图。
Proof. 令分成两个不相交的非空子集。移除内部的边，生成一个二分图。通过这种方式，有种不同的二分图。令表示中的边数。
边的两个顶点一个在中一个在中，那么，否则。
是多少呢？的顶点分别属于，那么剩余个顶点可以随意放，共。因此.
对所有的边重复这个事情，即。根据Theorem 15.19
所有的二分子图的边的个数的期望值大于，那么必然包含一个边数大于的二分子图。
下面是复杂理论(complexity theory)中一个很有名的问题———中间性问题(Betweenness problem)。
Example 15.24. 给定有序三元组的列表，对于任意，都是不同的数。不同下标对应的中包含的数可以相同。
令是排列。如果中有元素大小介于之间，就说满足。这里和顺序无关，这三个元素在中可以是也可以是。
存在一个排列满足任意给定的中至少三分之一的。
Solution. 随机变量表示随机选取一个排列是否满足。那么，即有三分之一的概率在之间，所以。根据Theorem 15.19
根据Theorem 15.22可以推出存在性。
Conditional Expectation
计算变量期望的另一种方式是条件期望。条件期望是事件发生时的期望值。通过替换中的绝对概率为发生时的条件概率，可以定义。
扩展Theorem 15.16得到下面的定理。
Theorem 15.25. 令是随机变量，是样本空间的一系列事件，有，且。那么
Proof. 接着Theorem 15.16，类比是那个定理中的。两边同乘以，求和就可以得到要证明的式子了。
Example 15.26. 掷一个骰子三次。第一次结果至少是四，那么结果是偶数的次数的期望是多少？
Solution. 后面两次结果是偶数的次数的期望值是一，如果第一次是偶数，那么期望值是二，如果第一次是奇数，那么期望值是一。所以
上面的例子比较容易算，下面这个就不这么明显了。
Example 15.27. 一个球队赢球的概率是四分之三。如果已知前四场至少胜利了三场，那么12场比赛胜利的场次期望值是多少？
Solutioin. 根据已知信息，前四场要么胜了三场（）要么胜了四场（）。忽略条件，前四场胜至少三场称为事件。
这里就是样本空间。我们将记作。
后面八场比赛，胜利的场次期望值是6场。加上前面四场，胜利场次用变量表示
最终结果比9略大一些。因为我们知道了一些额外信息，前四场至少胜了三场。
Exercises
(1) 令是个字符的字符串包含连续字符字串Probability is fun的概率。求证。
Solution. 首先，序列是递增的，或者严格地说，是非递减的。。的含义是个字符中没有包含需要的字符字串，但是个包含的概率。
接下来证明会收敛到1。比如有序列，因为题目中的字符串有16个字符。
令随机选择一个十六个字符的字符串是题目中要求的字符串是事件，那么，所以（可以把长度的字符串分割成个十六个字符的字符串）。
综上，有
趋于无穷时，趋于0。
(13) 令是随机的选择的的分割。表示的第一个部分的元素数量，表示的部分的个数。求。
Solution. 的第一部分有个元素，那么其共轭分割就有个部分，那么，因此。
(16) 回忆十四章有。令是大于7的固定整数。令事件表示排列包含1234模式，事件表示排列包含1324模式。令表示随机选择一个排列包含1234模式，表示随机选择一个排列包含1324模式。那么哪个大呢？
Solution. 随机选择四个不同的数，组成模式的概率是，那么排列任选四个数的个数是
，所以/24。根据Theorem 15.25有
由于，那么，又有，所以。
(18) 令是随机选择的排列的固定点个数。求证。
Solution. ，又有，那么需要证明的就是。
和Theorem 15.21一样定义指示随机变量，那么
只能是零和一，那么，所以。如果是随机选择的排列，那么对于，有的几率有，所以。所以