这一篇介绍QE理论中出现了两个信封问题相关的题目：2015年1月的第二题和2015年5月的第一题。信封问题最原始的设定是有$n$n个信封和$n$n个信件，把$n$n个信件随机装入$n$n个信封中。关于这个问题有个非常重要的结论，用$P_m$Pm​表示恰好有$m$m个信件被放入了正确的信封的概率，则
$P_m = \frac{1}{m!}\sum_{j=0}^{n-m} \frac{(-1)^j}{j!}$Pm​=m!1​j=0∑n−m​j!(−1)j​

这个式子的推导也非常容易，根据Waring公式（参考UA MATH564 概率论 计算至少有一个发生的概率：Waring公式）
$P_m= \sum_{k=m}^n (-1)^{k-m}C_k^mS_k$Pm​=k=m∑n​(−1)k−mCkm​Sk​

假设事件$A_i$Ai​表示第$i$i个信件被装在正确的信封中，则记号$S_k$Sk​表示
$S_k = \sum_{1 \le i_1 < i_2 < \cdots < i_k \le n} P(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}) = C_n^k \frac{(n-k)!}{n!} = \frac{1}{k!}$Sk​=1≤i1​<i2​<⋯<ik​≤n∑​P(Ai1​​∩Ai2​​∩⋯∩Aik​​)=Cnk​n!(n−k)!​=k!1​

这个概率的计算比较简单，从$n$n个信件中抽$k$k个，这$k$k个的位置是确定的，所以基本事件数目等于另外$(n-k)$(n−k)个的全排列，基本事件总数等于$n$n的全排列。因此
$P_m= \sum_{k=m}^n (-1)^{k-m}C_k^mS_k = \sum_{k=m}^n (-1)^{k-m}\frac{k!}{m!(k-m)!}\frac{1}{k!} = \frac{1}{m!}\sum_{j=0}^{n-m} \frac{(-1)^j}{j!}$Pm​=k=m∑n​(−1)k−mCkm​Sk​=k=m∑n​(−1)k−mm!(k−m)!k!​k!1​=m!1​j=0∑n−m​j!(−1)j​

2015年1月的第二题

Part a
这一问比较简单，不限制每个袋子容纳的球的数目，则基本事件总数为$n^n$nn，每个球都不在对应编号的袋子里的基本事件数目为$(n-1)^n$(n−1)n，因此概率为
$\frac{n^n - (n-1)^n}{n^n}$nnnn−(n−1)n​

Part b
这一问就是典型的信封问题，每个袋子只能容纳一个球，每个球都不在对应编号的袋子里的概率，根据信封问题的公式，就是
$P_0 = \sum_{j=0}^{n} \frac{(-1)^j}{j!}$P0​=j=0∑n​j!(−1)j​

但！考试的时候是不能这样写的。这里提供两种推导的思路，分别从概率论与组合学的角度入手，概率论方法的核心是用示性函数的期望表示事件的概率，把复杂概率化归为简单概率计算；组合学方法的核心是容斥原理。

概率论方法
引入Bernoulli随机变量$X_i$Xi​，$X_i = 1$Xi​=1表示编号为$i$i的球被放在对应编号的袋子中，则
$P_0 = E \left[ \prod_{i=1}^n (1-X_i) \right] \\= E \left[ 1- \sum_{i=1}^n X_i + (-1)^{m}\sum_{1 \le i_1 < \cdots < i_m \le n} X_{i_1}\cdots X_{i_m} \cdots +(-1)^n X_1\cdots X_n \right]$P0​=E[i=1∏n​(1−Xi​)]=E[1−i=1∑n​Xi​+(−1)m1≤i1​<⋯<im​≤n∑​Xi1​​⋯Xim​​⋯+(−1)nX1​⋯Xn​]

假设事件$A_i$Ai​表示编号为$i$i的球被装在对应编号的袋子中
$E[X_{i_1}\cdots X_{i_m}] = P(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_m}) = \frac{(n-m)!}{n!}$E[Xi1​​⋯Xim​​]=P(Ai1​​∩Ai2​​∩⋯∩Aim​​)=n!(n−m)!​

带入可得
$P_0 = \sum_{j=0}^{n} \frac{(-1)^j}{j!}$P0​=j=0∑n​j!(−1)j​

组合学方法
沿用上述记号，根据容斥原理，至少有一个球在对应编号的袋子里的基本事件总数为
$\# \bigcup_{i=1}^n A_i = \sum_{i=1}^n \#A_i +(-1)^{m+1} \sum_{1 \le i_1 < \cdots < i_m \le n}\# \bigcap_{j=1}^m A_{i_j} + (-1)^{n+1}\#\bigcap_{i=1}^n A_{i}$#i=1⋃n​Ai​=i=1∑n​#Ai​+(−1)m+11≤i1​<⋯<im​≤n∑​#j=1⋂m​Aij​​+(−1)n+1#i=1⋂n​Ai​

其中
$\# \bigcap_{j=1}^m A_{i_j} = (n-m)!$#j=1⋂m​Aij​​=(n−m)!

基本事件总数为$n!$n!，因此概率为
$P_0 = \frac{n! - \# \bigcup_{i=1}^n A_i}{n!} = \sum_{j=0}^{n} \frac{(-1)^j}{j!}$P0​=n!n!−#⋃i=1n​Ai​​=j=0∑n​j!(−1)j​

2015年5月的第一题

这道题其实就是对上一题中概率论方法定义的Bernoulli随机变量的深入讨论。注意到$X_i \sim Ber(1/n)$Xi​∼Ber(1/n)，因此
$E[X_i^2] = 1^2 \times \frac{1}{n} + 0^2 \times \frac{n-1}{n} = \frac{1}{n}$E[Xi2​]=12×n1​+02×nn−1​=n1​

$X_iX_j$Xi​Xj​也服从Bernoulli分布，
$P(X_iX_j = 1) = P(X_i = 1,X_j = 1) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)} \\ E[X_1X_j] = \frac{1}{n(n-1)}$P(Xi​Xj​=1)=P(Xi​=1,Xj​=1)=n!(n−2)!​=n(n−1)1​E[X1​Xj​]=n(n−1)1​

有了这两个结论，剩下两个计算就十分容易了
$E[S_n^2] = E \left( \sum_{i=1}^n X_i \right)^2 = \sum_{i=1}^n EX_i^2 + 2\sum_{1 \le i < j \le n} EX_iX_j = 1 + 2 \times C_n^2 \frac{1}{n(n-1)} = 2 \\ E[S_n] = \sum_{i=1}^n EX_i = 1 \\ Var(S_n) = E[S_n^2] - (E[S_n])^2 = 1$E[Sn2​]=E(i=1∑n​Xi​)2=i=1∑n​EXi2​+21≤i<j≤n∑​EXi​Xj​=1+2×Cn2​n(n−1)1​=2E[Sn​]=i=1∑n​EXi​=1Var(Sn​)=E[Sn2​]−(E[Sn​])2=1