离散概率本质上依然是组合计数，但引入概率论的概念能够让我们的讨论更加直观更加方便。

概率

麦克斯韦说：“我们这个世界的真正逻辑寓于概率的计算之中。”这句话强调了概率的空前的重要性。但仔细想想，我发现我其实并不真的知道“概率”指的是什么。我们平时在生活中经常使用“机会”或“可能形”这样的词，通常我们是在做一种猜测。为什么我们要猜测呢？因为我们希望在不完全掌握信息时做出我们必须做出的决定。事实上，我们的任何一个判断本质上都是一种猜测。

所谓“概率”，就是指我们在大量重复某个观察时对其中出现的某个特定结果的最有可能分数的估计，这时候我们就把发生的次数除以总次数定义为“概率”。由此可见，我们只能对可重复的观察谈概率。概率有赖于我们的知识以及进行估计的能力，因此它并不是完全客观的！很有可能，当我们所掌握的知识发生变化后，对事物的概率的估计就会变得完全不同。

随机事件

概率空间

为了严格地描述“概率是什么”，人们抽象出了概率空间的概念。概率空间由三个要素组成：样本集\(\Omega\)，事件集\(\mathcal{F}\)，概率函数\(\Pr\)。我们可以把它写成三元组\((\Omega,\mathcal{F},\Pr)\)。样本集是所有可能结果的集合（我们总是默认\(\Omega\)是可数集）；\(\mathcal{F}=2^{\Omega}\)，它是\(\Omega\)的所有子集的集合；\(\Pr\)是\(\mathcal{F} \to \R\)的函数，对应一个事件发生的概率。

只有样本集中的每个元素是现实世界中产生的结果，并且一旦随机事件进行了，一定只会出现样本集中的一个元素的结果。而“事件”是我们对“可能的结果”的一种描述，一个“事件”可能描述了许许多多种可能发生的结果。概率函数就是要描述自然语言描述的那些可能结果合在一起发生的可能性。比如，我们尝试用概率空间\((\Omega,\mathcal{F},\Pr)\)来描述“掷一次骰子”这件事。那么样本集只能是\(\Omega=\{1,2,3,4,5,6\}\)。而我们的事件可以是“掷出偶数”，它对应着\(A=\{2,4,6\} \in \mathcal{F}\)，对应的概率\(\Pr(A)=1/2\)。

事件是集合，因此我们可以用集合的符号来表示来表示事件：例如\(A \cup B\)表示两个事件的并集，\(A \cap B\)表示两个事件的交集。我们还可以定义\(\overline{A}=\Omega \setminus A\)，表示\(A\)的补事件。

我们发现，概率函数的取值不能是任意的。首先，它的取值必须在\([0,1]\)之间，并且满足\(\Pr(\empty)=0,\Pr(\Omega)=1\)。由此可见\(\Pr(A)+\Pr(\overline{A})=1\)。我们还必须规定，对于两两不相交的有限或可数无穷序列\(A_1,A_2,\cdots\)，必须满足\(\Pr\left(\bigcup\limits_{i \geq 1}A_i\right)=\sum\limits_{i \geq 1}\Pr(A_i)\)。这些事实称为“概率公理”，它描述了符合我们日常经验的概率的性质。必须满足这些条件才能称为“概率空间”。

\(\Omega\)中的每一个元素本身就可以单独构成一个事件（集合），这些集合两两不交；同时，任意一个事件都是\(\Omega\)的一个子集，因此一定是这些集合中的某一些的无交并。所以我们就把这些单独构成的集合称为“基本事件”，任何一个事件都是一系列基本事件的并，求任何一个事件的概率只需要把对应的基本事件的概率累加。所以，只要直到了所有基本事件的概率，理论上就可以计算出任何事件的概率。

容斥原理

对于两个有交集的事件\(A,B\)，如何求出\(\Pr(A \cup B)\)？直觉就是\(\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)\)。但我们必须用公理来推导它。根据公理，我们只会计算无交集的两个集合的并的概率，所以我们做这样的的拆分：\(\Pr(A) = \Pr(A \setminus (A \cap B))+\Pr(A \cap B)\)，\(\Pr(B) = \Pr(B \setminus (A \cap B))+\Pr(A \cap B)\)。而\(\Pr(A \cup B)=\Pr(A \setminus (A \cap B))+\Pr(B \setminus (A \cap B))+\Pr(A \cap B)\)。这样我们就解出来\(\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)\)。

用同样的方法，类比集合中我们采用的算贡献的想法，可以证明概率的容斥原理\(\Pr[\bigcap\limits_{i\in [n]} \overline{A_i}]=\sum\limits_{J\subseteq [n]}(-1)^{|J|}\cdot \Pr(\bigcap\limits_{j\in J} A_j)\)。（证明每个基本事件在等式两边的贡献相等）

Union Bound

从二元情形的容斥原理\(\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)\)中可以看出，如果我们丢掉\(-\Pr(A \cap B)\)这一项，因为概率函数一定是非负的，我们就会直接得到\(\Pr(A \cup B)\leq\Pr(A)+\Pr(B)\)，推广到\(n\)元就是\(\Pr\left(\bigcup\limits_{i \in I}A_i\right)\leq \sum\limits_{i \in I}\Pr(A_i)\)，这个结论称为“Union Bound”。

这个结论虽然推导很简单，但却在应用中有着巨大的价值。

为了看到Union Bound的巨大价值，我们来看一个复杂的例子。

我们发现一个事实，6个人之间要么至少有三个人互相之间都认识，要么至少有三个人之间互相都不认识。用一般的数学语言来描述，在6个节点的完全图（\(K_6\)）上，每条边要么染成红色要么染成蓝色（代表认识与不认识），那么对于任何一种染色方案，“所有边都是红色的\(K_3\)子图”和“所有边都是蓝色的\(K_3\)子图”都至少存在一个。

我们可以证明（枚举），在5个点的完全图上这一点是做不到的。也即要做到这一点至少需要6个节点，在5个点的图上至少存在一种染色方案使得红色和蓝色的\(K_3\)子图都不存在。

由此我们定义Ramsey数\(R(r,s)\)，他表示使得完全图\(K_N\)的边任意红蓝染色始终存在“红色的\(K_r\)子图”或“蓝色的\(K_s\)子图”中的至少一个的最小的\(N\)。这是Well-Defined的，因为我们已经看到太小的\(N\)是不行的，而显然\(N\)足够大时一定是可行的，所以它被限制在一个闭区间里，所以最小值一定存在。上面这个例子可以描述为\(R(3,3)=6\)。

我们可以证明\(\dbinom{r+s-2}{r-1}\)是\(R(r,s)\)的一个上界，这并不需要用到概率的知识：我们首先证明\(R(r,s) \le R(r-1,s)+R(r,s-1)\)。令\(M=R(r-1,s)+R(r,s-1)\)，只需证明\(K_M\)中一定存在红色\(K_r\)或蓝色\(K_s\)。对于任意某个特定的染色，考虑与某个点（比如点1）相邻的\(M-1\)条边的染色情况，由于\(M=R(r-1,s)+R(r,s-1)\)，因此根据鸽巢原理，这\(M-1\)条边中“至少有\(R(r-1,s)\)条红边”与“至少有\(R(r,s-1)\)”条蓝边中总有一个成立，不然总边数就小于等于\(M-2\)，矛盾。如果是前者满足，那么把这些边连出去的点收集在一起就有\(R(r-1,s)\)个点了，根据定义，这些点构成的完全子图里一定要么存在一个红色\(K_{r-1}\)或者蓝色\(K_s\)。如果存在蓝色\(K_s\)则证毕，否则对于得到的\(K_{r-1}\)附加上原先固定的点1就一定能得到一个红色\(K_r\)，因此无论如何都成立。“至少有\(R(r,s-1)\)”的情况也是完全相同的。所以我们证明了这个递推不等式。对\(r+s\)归纳，那么\(R(r,s) \leq R(r-1,s)+R(r,s-1) \leq \dbinom{r+s-3}{r-2}+\dbinom{r+s-3}{r-1}=\dbinom{r+s-2}{r-1}\)，得证。

下面我们证明下界。这里我们只能给出\(r=s\)时的下界\(R(s,s) > 2^{s/2}\)。只需证明对于\(M=2^{s/2}\)，\(K_M\)中一定不存在同色的\(K_s\)子图。这里我们要用到概率方法——转而证明如果给\(K_M\)随机着色，出现“不存在同色\(K_s\)子图”这一事件的概率大于0，这等价于“存在同色\(K_s\)子图”这一事件的概率小于1。在这里，概率空间中样本集就是所有可能的染色方案（每条边可以选择染红或染蓝，共有\(2^{|E|}\)种）。“存在同色\(K_s\)子图”这一事件对应着样本集中的一个子集，即那些符合我们条件的染色方案。这是不容易计算的。然而，如果我们枚举所有的大小为\(s\)的子图，那么每一个子图的“同色”也是一个事件。并且我们发现对于我们枚举的所有的子图，这些事件的并集恰好就是“存在同色\(K_s\)子图”这一事件（如果一个子图同色，那么它在“存在同色\(K_s\)”里有贡献；如果它在“存在同色\(K_s\)”里有贡献，那么一定在适当的时候被枚举到）。这些事件之间可能有交集，因此精确计算他们的并集的概率必须要容斥，但我们可以用Union Bound给出上界，而对于每个事件的概率是容易计算的——只需保证枚举到的点集里的所有边同色，边的个数为\(\dbinom{s}{2}\)，因此每个事件的概率就是\(\left[\dfrac{1}{2}\right]^{\binom{s}{2}} \times 2\)（乘以2是因为有两种可能的“同色”）。因此总的概率就可以被放缩为\(\dbinom{M}{s}\times 2^{1-\binom{s}{2}}\)，代入\(M=2^{s/2}\)，\(\dfrac{2^{s/2}!}{s!(2^{s/2}-s)!} \times 2 \times \dfrac{1}{2^{\frac{s(s-1)}{2}}}\)，它是小于1的！这样证明就结束了。

当我们要证明“可能出现不存在的情况”时，只需证明“存在的概率小于1”。为此，我们可以枚举所有可能情况，这些可能情况的并集恰好构成“存在”这一事件。我们不直接计算这个并集的概率，而是计算每个可能情况的概率之和，这个和通过Union Bound给出了“存在的概率”一个上界，如果这个上界都已经小于1，那么我们想证明的概率就一定小于1。这就是证明“存在”的一种概率方法。

独立事件

对于概率空间\((\Omega,\mathcal{F},\Pr)\)中的两个事件\(A,B \in\mathcal{F}\)，定义两个事件是独立的当且仅当\(\Pr(A \cap B)=\Pr(A) \cdot \Pr(B)\)。对于多个事件\(A_1,\cdots,A_n\)，定义它们“两两独立”当且仅当对于任何\(I\subseteq [n]\)，\(\Pr(\bigcap\limits_{i \in [n]}A_i) = \Pr(\bigcap\limits_{i \in I}A_i) \cdot \Pr(\bigcap\limits_{j \not\in I}A_j)\)。

“独立”这个概念根据字面意思来理解，就是两个事件之间“没有关联”。比如就“在1，2，3，4中选数”这个样本空间中，“选到1或2”这个事件对应着\(A=\{1,2\}\)，“选到1或3”这个事件对应着\(B=\{1,3\}\)，那么发现\(\Pr(A \cap B)=\Pr(A)\Pr(B)\)，所以这两个事件根据我们的定义就是独立的！

我们来看一个多项式恒等判定的例子。如果两个多项式\(P(x),Q(x)\)是黑箱，那么如何判定它们是否恒等？假设它们的次数都不超过\(d\)次，那么假如我们选取\(d\)个不同的实数\(x_i\)，对于每个都满足\(P(x_i)=Q(x_i)\)，那么对于多项式\(T(x)=P(x)-Q(x)\)，\(x_1,\cdots,x_d\)就是\(T(x)\)的\(d\)个根。如果我们再选一个\(x_{d+1}\)，依然满足\(T(x_{d+1})=0\)，那说明\(T\)有\(d+1\)个根——这只可能是\(T(x) \equiv 0\)，因为代数基本定理告诉我们一个\(d\)次多项式最多只能有\(d\)个不同的实数根。

由此我们可以采用概率方法来判定两个多项式是否恒等。我们选取一个样本集\(A\)，里面是一些不同的实数（整数或许更加方便）。均匀随机（Uniformly At Random, u.a.r.）从\(A\)中选取一个数字\(a\)，如果\(P(a)=Q(a)\)就返回二者恒等，否则返回二者不等。这个算法怎么样呢？如果\(P,Q\)确实恒等，那么我们的算法始终返回的是正确结果；如果\(P,Q\)不等， 我们的算法返回“恒等”的概率是多少？由于\(P,Q\)不等， 能满足\(P(x_i)=Q(x_i)\)的\(x_i\)在实数范围内就一定不超过\(d\)个，因此我们抽取的\(a\)恰好满足的概率不超过\(\dfrac{d}{|A|}\)。因此如果选择大小为\(100d\)的样本集，算法的出错概率就达到了\(\leq \dfrac{1}{100}\)。

由于\(|A|\)的增大是有代价的，使得\(|A|\)越大并不一定越是好事。如何进一步提高算法的正确性呢？如果我们多次选择\(a\)，比如选\(t\)次，只有当每一次都满足\(P(a_i)=Q(a_i)\)才返回“恒等”，否则只要有一个不相等就返回“不恒等”，这样的算法在多项式明明不恒等却返回恒等的概率是多少？此时我们的样本空间变成了\(A^t\)，其中的基本事件为“一种取\(t\)次的方法”。我们考虑“第\(i\)次选到的数\(x\)满足\(P(x)=Q(x)\)”这一事件发生的概率，记为\(\Pr[P(a_i)=Q(a_i)]\)。我们可以验证\(P(a_i)=Q(a_i)\)与\(P(a_j)=Q(a_j)\)是独立的，因为\(\Pr[P(a_i)=Q(a_i) \cap P(a_j)=Q(a_j)]=\dfrac{|D|^2}{|A|^2}\)，其中\(D\)是\(A\)中\(P(x)-Q(x)\)的根的集合；而\(\Pr[P(a_i)=Q(a_i)]=\Pr[P(a_j)=Q(a_j)]=\dfrac{|D|}{|A|}\)，这样我们就验证了独立性，并且可以用类似的方法验证第\(1\)次到第\(n\)次每一次满足\(P(a_i)=Q(a_i)\)所有这些事件是“两两独立的”，因此直接得到\(\Pr[\bigcap\limits_{i \in [t]}P(a_i)=Q(a_i)]=\prod\limits_{i=1}^{t}\Pr[P(a_i)=Q(a_i)]=\dfrac{|D|^t}{|A|^t}\)，当\(|A|\)取\(100d\)时，可放缩为\(\dfrac{1}{100^t}\)。

条件概率

对于概率空间\((\Omega,\mathcal{F},\Pr)\)中的两个事件\(A,B \in\mathcal{F}\)，定义\(A\)事件在\(B\)事件发生下的条件概率为\(\Pr(A|B)=\dfrac{\Pr(A \cap B)}{\Pr(B)}\)，记为\(A \perp B\)。这是符合我们的直观的，当我们讨论“\(B\)发生的条件下”时，我们把讨论区域限制在了\(B\)内，因此\(B\)就“好像是整个空间”了——所以我们除掉\(B\)发生的概率。

两个互相独立的事件其中一个在另一个的条件下发生的概率应该就是它本身发生的概率，代入验证这确实成立：由于\(\Pr(A \cap B)=\Pr(A) \cdot \Pr(B)\)恰好得到\(\Pr(A|B)=\dfrac{\Pr(A \cap B)}{\Pr(B)}=\dfrac{\Pr(A)\Pr(B)}{\Pr(B)}=\Pr(A)\)。这也是我们理解独立的一种方法，两事件独立等价于其中一个在另一个发生下的条件概率就是它自己，这表明\(A,B\)是“没有关系”的。

我们可以把条件概率的等式变形为\(\Pr(A\cap B) = \Pr(A|B) \cdot \Pr(B)\)。于是我们能够得到一个求解事件的交集的概率的链式法则：\(\Pr(A_1 \cap \cdots \cap A_n)\)\(=\Pr(A_n|A_1 \cap \cdots \cap A_{n-1}) \cdot \Pr(A_1 \cap \cdots \cap A_{n-1})\)\(=\cdots\)\(=\Pr(A_1)\cdot \Pr(A_2 | A_1)\cdot \Pr(A_3|A_1 \cap A_2) \cdots \cap \Pr(A_{n-1}|A_1 \cap \cdots \cap A_{n-2})\cdot\Pr(A_n|A_1 \cap \cdots \cap A_{n-1})\)。它在直观上似乎更好理解，因为所有事件同时发生的概率可以写作“第一个事件发生的概率乘上在第一个事件发生的条件下第二个事件发生的概率乘上第一个事件和第二个事件都发生的条件下第三个事件发生的概率……”

Birthday Paradox

23个人里有两个人生日在同一天的概率达到50%，60个人里有两个人生日在同一天的概率达到99%。如何计算这个“生日悖论”的概率？

抽象为数学问题，我们可以这样描述：把\(m\)个小球随机放进\(n\)个箱子里，存在一个箱子里有至少两个小球的概率是多大？我们的概率空间是所有从\([m]\)到\([n]\)的映射\(f\)，要计算的是“映射不为单射”这一事件的概率。为此，我们再考虑一系列事件\(A_i\)，其中\(A_i\)表示“\(f(i) \neq f(j)\)对\(j\in [i-1]\)恒成立”这一事件，它对应了一系列映射，直观上表示的是如果我们把丢球的过程拆分成一个个按顺序丢球的过程，这个事件代表第\(i\)个球在丢的时候箱子里还是空的。于是“映射不为单射”这一事件等价于所有\(A_i\)都发生，因此我们要算的就是\(\Pr[A_1 \cap A_2 \cap \cdots \cap A_m]\)。利用链式法则，我们可以把它转化为条件概率：\(\Pr[A_i|A_1 \cap \cdots \cap A_{i-1}]\)是容易计算的，由于前\(i-1\)个球都对应了不同的箱子，留下的空箱子只有\(n-(i-1)\)个，因此它的值就是\(\dfrac{n-i+1}{n}\)。于是求得\(\Pr[A_1 \cap A_2 \cap \cdots \cap A_m]=\prod\limits_{i=1}^{m}\dfrac{n-i+1}{n}\)，它可以写作\(\left( 1-\dfrac{1}{n}\right)\cdots \left( 1-\dfrac{m-1}{n}\right)\)，根据\(1+x\leq e^x\)恒成立，\(1-\dfrac{k}{n} < e^{-\frac{k}{n}}\)，因此原式放缩为\(e^{-\frac{1}{n}[1+2+\cdots+(m-1)]}=e^{-\frac{m(m-1)}{2n}}\)。

取\(n=365\)，则当\(m=23\)时值恰好在0.5左右。当\(m=60\)时它小于0.01，因此生日重复的概率高达99%。

全概率定理

设样本空间\(\Omega\)可以划分为互不相交的事件\(E_1, \cdots ,E_n\)。那么

\(\forall B, \Pr(B)=\sum\limits_{i=1}^{n}\Pr(B \cap E_i)=\sum\limits_{i=1}^{n}\Pr(B|E_i)\cdot \Pr(E_i)\)。

其中最后一步用到了条件概率的定义。

贝叶斯定理

设样本空间\(\Omega\)可以划分为互不相交的事件\(E_1, \cdots ,E_n\)。那么根据条件概率的定义和全概率定理：

\(\Pr(E_j|B)=\dfrac{\Pr(E_j \cap B)}{\Pr(B)}=\dfrac{\Pr(E_j \cap B)}{\sum\limits_{i=1}^{n}\Pr(B|E_i)\cdot \Pr(E_i)}\)

随机变量

随机变量是从样本空间到实数的映射。比如“投两个骰子”总共产生了36个可能的事件，而“点数之和”这一随机变量却只能有2到12这11个取值。形式化地，我们用\(X=a\)来表示随机变量\(X\)的取值为\(a\)这一事件，它其实表示的是集合\(\{s\in \Omega|X(s)=a\}\)。

根据基本事件的定义，\(\Pr(X=a)=\sum\limits_{X(s)=a,s\in\Omega}\Pr(s)\)。

同理我们可以定义随机变量的独立性：\(X\)与\(Y\)独立当且仅当对于任何的\(a,b\)始终成立\(\Pr((X=a)\cap (Y=b))=\Pr(X=a)\cdot\Pr(Y=b)\)。

期望是随机变量的一个基本特征：随机变量的期望定义为其概率的加权平均值。\(E[X]=\sum\limits_{i}i\Pr(X=i)\)。

期望的线性性

一个最重要的定理称为“期望的线性性”：对于有限个随机变量\(X_1,\cdots,X_n\)始终满足\(E\left[\sum\limits_{i=1}^{n}X_i\right]=\sum\limits_{i=1}^{n}E[X_i]\)。证明就是根据定义：\(E[X+Y]=\sum\limits_{i}\sum\limits_{j}(i+j)\Pr((X=i)\cap(Y=j))\)，提出固定的变量得到\(\sum\limits_{i}i\sum\limits_{j}\Pr((X=i)\cap(Y=j))+\sum\limits_{j}j\sum\limits_{i}\Pr((X=i)\cap(Y=j))\)，而后面的那个和式恰好就是全概率公式，因此直接可以化简得到\(\sum\limits_{i}i\Pr(X=i)+\sum\limits_{j}j\Pr(Y=j)\)，这就是\(E[X]+E[Y]\)。这就证明了期望的线性性。重要的是，期望的线性性没有对随机变量提出任何的要求，即使两个随机变量不是“独立”的，它们的期望也始终符合“线性性”这一特征。这对我们计算期望提供极大的方便。当然，为了完善“线性性”这一概念，我们还应当证明\(E[cX]=cE[X]\)：这是容易的，\(E[cX]=\sum\limits_{i}ci\Pr(X=i)=cE[X]\)。

Jensen不等式

对于非线性的函数，期望就不再满足这样的性质了：在\(\{1,99\}\)里选一个数，这构成随机变量\(X\)。由这个随机变量的大小为边长的正方形面积也对应着一个“随机变量”，方便起见我们记这个变量为\(X^2\)。根据定义，我们计算出\(E[X^2]=\sum\limits_{i=1}^{99}i^2 \Pr(X=i)=\dfrac{\sum\limits_{i=1}^{99}i^2}{99}=\dfrac{9950}{3}\)。而\((E[X])^2=\left(\sum\limits_{i=1}^{99}\dfrac{i}{99}\right)^2=2500\)，因此\(E[X^2] \neq (E[X])^2\)。

我们可以更精确地描述这二者的关系：我们构造一个\(E[(X-E[X])^2]\)，由于它只对非负的随机变量求期望，因此它的值一定非负。而把它展开\(E[(X-E[X])^2]=E[X^2+(E[X])^2-2XE[X]]\)，根据期望的线性性，它等于\(E[X^2]+E[(E[X])^2]-E[2XE[X]]\)。\(E[X]\)本身也是一个随机变量，只不过它是一个常数，因此它的期望就是这个常数，也可以作为常数被提出外面。于是得到\(E[X^2]+(E[X])^2-E[X]E[2X] \geq 0\)。化简得结论：\(E[X^2] \geq (E[X])^2\)。

这个结论只是函数\(X^2\)作为一个特例存在。对于任何下凸函数\(f\)这个不等式都是成立的，这就是概率形式的Jensen不等式：\(E[f(X)] \geq f(E[X])\)。证明：凸函数满足\(f(x)\geq f(\mu)+f'(\mu)(x-\mu)\)，那么取\(\mu=E[X]\)，并在不等式两边同时取期望（等式两边都是随机变量）就得到\(E[f(X)] \geq f(E[X])+f'(E[X])(E[X]-E[E[X]])=f(E[X])\)。

二项分布

如果事件表示某件事的成功与否，成功概率为\(p\)，变量\(X=1\)，否则失败，变量\(X=0\)，那么这个变量\(X\)就称为伯努利随机变量。独立重复\(n\)次，记成功的次数为\(Y\)，那么称\(Y\)为二项随机变量，满足二项分布：

\(\Pr(Y=i)=\dbinom{n}{i}p^i(1-p)^{n-i}\)

由此可以求出二项随机变量的期望：

\(\begin{aligned}E[Y]&=\sum\limits_{i=0}^{n}i\dbinom{n}{i}p^i(1-p)^{n-i}\\&=\sum\limits_{i=1}^{n}\dfrac{n!}{(i-1)!(n-i)!} \cdot p^i(1-p)^{n-i}\\&=np\sum\limits_{i=1}^{n}\dfrac{(n-1)!}{(i-1)!(n-i)!}p^{i-1}(1-p)^{}n-i\\&=np(p+1-p)^{n-1}\\&=np \end{aligned}\)

事实上还有更简单的证明方法，二项随机变量\(Y\)可以被拆解成\(n\)个基本事件的随机变量\(X_i\)，其中\(X_i\)表示第\(i\)次实验是否成功。于是就有关系\(Y=\sum\limits_{i=1}^{n}X_i\)。两边同时取期望，\(E[Y]=E\left[\sum\limits_{i=1}^{n}X_i\right]\)，根据期望的线性性，\(=\sum\limits_{i=1}^{n}E[X_i]=\sum\limits_{i=1}^{n}p=np\)。

几何分布

二项分布可以理解为丢\(n\)次硬币统计正面朝上的次数，那么几何分布就可以相应地理解为不停丢直到第一次出现正面的次数。因此\(\Pr(X=n)=(1-p)^{n-1}p\)。

如何算几何分布的期望？从直觉上看，丢一个\(1/10\)概率出正面的硬币大约需要10次，因此我们可以期望\(E[X]=\dfrac{1}{p}\)。它的计算就是暴力求解等差乘等比数列的和。

条件期望

基于事件我们定义了条件期望，那么依赖于这样的事件的期望就被称为条件期望。所以自然地定义\(E[Y|Z=z]=\sum\limits_{y}y\Pr(Y=y|Z=z)\)。