一个收发作业的问题

班上有 $n$ 名学生，每人交了一份作业。批改完之后，助教没有按名字发还，而是随机地把作业发给学生——等价于在所有排列中均匀随机地选一个。

问题：没有人拿到自己作业的概率是多少？

这正是经典的「错排」问题。直觉上，$n$ 很大时每个人都拿到别人作业的可能性不小，概率应该接近某个常数——最后算出来是 $1/e\approx0.368$。

引出这个答案的工具是容斥原理。它的思路极其朴素：先按最粗的方式数一遍，发现数多了就减掉，发现减多了就加回来，一直修正到正好。

时间轴

把问题写成事件

令 $A_i$ 表示「第 $i$ 名学生拿到了自己的作业」。我们要求的是

$$P(\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_n}).$$

直接算这个交很难，但它的补事件很好描述：至少有一名学生拿到自己的作业，即

$$\overline{\overline{A_1}\cap\cdots\cap\overline{A_n}}=A_1\cup A_2\cup\cdots\cup A_n .$$

于是

$$P(\text{无人拿对})=1-P(A_1\cup\cdots\cup A_n).$$

问题归结为计算 $n$ 个事件的并。

容斥：先过计，再修正

图：n=3 的错排例子：韦恩图计数、逐层加减与一般公式。

$n=2$ 的情形

画两个相交的圆 $A_1$、$A_2$。最粗的估计是

$$P(A_1)+P(A_2).$$

这样数，交集 $A_1\cap A_2$ 被数了两次，所以减去一次：

$$P(A_1\cup A_2)=P(A_1)+P(A_2)-P(A_1\cap A_2).$$

这就是容斥的雏形。

对本问题取 $n=2$：两名学生的排列只有两种——两人都对，或两人互换。所以

$$P(A_1)=\frac12,\quad P(A_2)=\frac12,\quad P(A_1\cap A_2)=\frac12,$$

（两人都对的情形只有「两人都对」这一种排列），于是

$$P(A_1\cup A_2)=\frac12+\frac12-\frac12=\frac12, \qquad P(\text{无人拿对})=1-\frac12=\frac12 .$$

注意 $P(A_1\cap A_2)=1/2\ne1/4$：两个事件不独立。一旦第一个人拿到了自己的作业，剩下的作业也就唯一确定，第二个人必然也拿对。这正是本问题不能简单地用乘法处理的原因。

$n=3$ 的情形

先加三个单事件，交集被重复计算；再减去三个两两交。此时三个圆的共同中心 $A_1\cap A_2\cap A_3$ 被加了三次、又减了三次，等于没算。所以要加回来一次：

$$P(A_1\cup A_2\cup A_3) =P(A_1)+P(A_2)+P(A_3) -P(A_1\cap A_2)-P(A_1\cap A_3)-P(A_2\cap A_3) +P(A_1\cap A_2\cap A_3).$$

代入数值：$P(A_i)=1/3$；任意两事件同时发生意味着这两人的作业归位，第三人也只能归位，所以 $P(A_i\cap A_j)=1/6$；三事件同时发生也只有「完全正确」这一种排列，$P(A_1\cap A_2\cap A_3)=1/6$。于是

$$P(\text{至少一人拿对})=3\cdot\frac13-3\cdot\frac16+\frac16 =1-\frac12+\frac16=\frac23,$$ $$P(\text{无人拿对})=1-\frac23=\frac13 .$$

与错排数 $D_3=2$、总排列数 $3!=6$ 的比值 $2/6=1/3$ 一致。

一般公式

对任意事件 $A_1,\dots,A_n$，

$$P\!\left(\bigcup_{i=1}^{n}A_i\right) =\sum_{i}P(A_i) -\sum_{i<j}P(A_i\cap A_j) +\sum_{i<j<k}P(A_i\cap A_j\cap A_k) -\cdots +(-1)^{n+1}P(A_1\cap\cdots\cap A_n).$$

也就是：单事件加、两两交减、三重交加、四重交减……符号交替，直到 $n$ 重交。

为什么符号必须交替？可以这样看：一个恰好属于 $r$ 个事件的结果，在公式里被计算了

$$\binom{r}{1}-\binom{r}{2}+\binom{r}{3}-\cdots+(-1)^{r+1}\binom{r}{r} =1-(1-1)^r=1$$

次。二项式展开给出 $(1-1)^r=0$（$r\ge1$），所以这个和恰好等于 $1$：每个结果不多不少被计一次。

代回原问题

各项概率

发还作业相当于在 $n!$ 个排列中均匀随机取一个。对任意 $i$，

$$P(A_i)=\frac{(n-1)!}{n!}=\frac1n .$$

对 $r$ 个指定的学生同时拿到自己的作业，其余 $n-r$ 人可以任意排列，所以

$$P(A_{i_1}\cap\cdots\cap A_{i_r}) =\frac{(n-r)!}{n!} =\frac{1}{n(n-1)\cdots(n-r+1)} .$$

这正是条件概率的写法：第一位归位的概率是 $1/n$，在此条件下第二位归位的概率是 $1/(n-1)$，依此类推。

需要数项数：二项式系数

容斥公式里，$r$ 重交的项有 $\binom{n}{r}$ 个。这个量定义为

$$\binom{n}{r}=\frac{n(n-1)\cdots(n-r+1)}{r!}=\frac{n!}{r!\,(n-r)!}.$$

它的含义是「从 $n$ 个对象中选 $r$ 个」的方法数。分子先按顺序选：第一个有 $n$ 种，第二个有 $n-1$ 种……但这样把同一组的 $r!$ 种排列都数了一遍，所以要除以 $r!$。例如

$$\binom{n}{2}=\frac{n(n-1)}{2}.$$

求和

把每项「项数 × 概率」写出来：

$$P\!\left(\bigcup_i A_i\right) =\binom{n}{1}\frac{1}{n} -\binom{n}{2}\frac{1}{n(n-1)} +\binom{n}{3}\frac{1}{n(n-1)(n-2)} -\cdots$$

每一项都发生大规模约分。以第二项为例：

$$\binom{n}{2}\cdot\frac{1}{n(n-1)} =\frac{n(n-1)}{2}\cdot\frac{1}{n(n-1)} =\frac{1}{2!}.$$

一般地，第 $r$ 项等于 $1/r!$。于是

$$P(\text{至少一人拿对}) =1-\frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!}+\cdots+(-1)^{n+1}\frac{1}{n!}.$$

因此

$$P(\text{无人拿对}) =1-P(\text{至少一人拿对}) =\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^{n}\frac{1}{n!}.$$

把它写成从 $r=0$ 开始的完整级数——注意 $1-1=0$，可以补上首项：

$$P(\text{无人拿对})=\sum_{r=0}^{n}\frac{(-1)^r}{r!}.$$

当 $n\to\infty$ 时，

$$\sum_{r=0}^{\infty}\frac{(-1)^r}{r!}=\frac1e\approx0.3679 .$$

答案浮现：$e$ 从一个纯粹的排列计数问题里冒了出来。 具体数值：$n=2$ 时 $1/2$，$n=3$ 时 $1/3$，$n=4$ 时 $9/24=0.375$，之后在 $1/e$ 附近来回摆动并迅速收敛。

一个有用的启发

严格地说，$A_i$ 之间并不独立。但当 $n$ 很大时，它们「几乎独立」：第一个人是否拿对，对第二个人的影响只有 $1/n$ 量级。于是可以做一个不严谨但很快的计算：

$$P(\text{无人拿对})\approx\prod_{i=1}^{n}\left(1-\frac1n\right) =\left(1-\frac1n\right)^{n}\xrightarrow[n\to\infty]{}\frac1e .$$

这个推导不是证明（独立性并不成立），却给出了正确答案。容斥的作用正是把这种「几乎独立」的直觉变成严格结论。

容斥公式的归纳证明

定理。 对任意事件 $A_1,\dots,A_n$，上面的容斥公式成立。

证明。 对 $n$ 归纳。$n=2$ 的情形就是韦恩图给出的等式。

设公式对 $n$ 成立，记 $C=A_1\cup\cdots\cup A_n$，要证 $n+1$ 个事件的情形。把公式中的项分成两类：不含 $A_{n+1}$ 的，与含 $A_{n+1}$ 的。

不含 $A_{n+1}$ 的那些项，正好是 $n$ 个事件的容斥公式，由归纳假设等于 $P(C)$。

含 $A_{n+1}$ 的项，其符号在 $n+1$ 的公式里与原公式相反。定义辅助事件

$$B_i=A_i\cap A_{n+1}\qquad(i=1,\dots,n).$$

则含 $A_{n+1}$ 的那组项恰好是 $-1$ 乘以「对 $B_1,\dots,B_n$ 写出的容斥公式」，因为

$$B_i\cap B_j=(A_i\cap A_{n+1})\cap(A_j\cap A_{n+1})=A_i\cap A_j\cap A_{n+1}$$

（$A_{n+1}$ 交两次与交一次相同）。由归纳假设，这组项等于

$$-P(B_1\cup\cdots\cup B_n) =-P\bigl((A_1\cup\cdots\cup A_n)\cap A_{n+1}\bigr) =-P(C\cap A_{n+1}).$$

两类相加：

$$P(C)+P(A_{n+1})-P(C\cap A_{n+1}).$$

这正是 $n=2$ 情形的公式，等于 $P(C\cup A_{n+1})=P(A_1\cup\cdots\cup A_{n+1})$。归纳完成。$\square$

这个证明值得回味的不是代数，而是结构：把 $n+1$ 的表达式拆成「旧公式」与「旧公式的负数」，再把后者解释成新的辅助事件。写证明时，把读者需要跟随的逻辑顺序设计好，比逐步验算更重要。

用期望线性性一行解决相关问题

容斥用了一整节课才算出「无人拿对」的概率。现在换一个问题：拿到自己作业的人数，期望是多少？

定义随机变量

$$X=\sum_{i=1}^{n}\mathbf{1}_{A_i},$$

即拿到自己作业的人数。由期望的线性性（不需要任何独立性假设）：

$$\mathbb{E}[X]=\sum_{i=1}^{n}\mathbb{E}[\mathbf{1}_{A_i}] =\sum_{i=1}^{n}P(A_i) =\sum_{i=1}^{n}\frac1n=1 .$$

期望恰好是 $1$ 人，与 $n$ 无关。

这正是线性性最有价值的地方：它把「依赖关系」整个绕开了。$A_i$ 之间高度相关（一个人拿对会显著改变别人拿对的概率），但期望的可加性对此毫不在意。课程特意强调：这一点对期望成立，对期望的乘积不成立，对方差也不成立。

优惠券收集问题

问题

每份报纸随机附赠 $n$ 种优惠券中的一种（均匀分布、相互独立）。要收集齐全部 $n$ 种，平均需要看多少份报纸？取 $n=365$，就是「要问多少个学生，才能问遍所有生日」。

拆成阶段

关键技巧仍是「把复杂随机变量拆成简单随机变量之和」。令

$$T=T_0+T_1+\cdots+T_{n-1},$$

其中 $T_i$ 是「从已收集 $i$ 种，到收集第 $i+1$ 种」所需的份数。

已收集 $i$ 种时，下一份报纸带来新优惠券的概率是

$$p_i=\frac{n-i}{n},$$

因为 $n$ 种中有 $n-i$ 种还没见过。每一次尝试都是独立的，所以 $T_i$ 服从成功概率 $p_i$ 的几何分布，由上一讲的结论

$$\mathbb{E}[T_i]=\frac1{p_i}=\frac{n}{n-i}.$$

求和

$$\mathbb{E}[T]=\sum_{i=0}^{n-1}\frac{n}{n-i} =n\left(\frac1n+\frac1{n-1}+\cdots+\frac11\right) =nH_n,$$

其中 $H_n=\sum_{k=1}^{n}1/k$ 是第 $n$ 个调和数。取 $n=365$：

$$H_{365}\approx6.47, \qquad \mathbb{E}[T]\approx6.47\times365\approx2361 .$$

也就是说，要问大约 $2361$ 个学生，才能覆盖所有 $365$ 个生日——约为天数的 $6.5$ 倍。

渐近形式

由 $H_n\approx\ln n+\gamma$（$\gamma\approx0.577$ 为欧拉常数），

$$\mathbb{E}[T]=nH_n\approx n\ln n .$$

所以「覆盖 $n$ 种需要 $n\log n$ 次」是一个很好用的经验法则。它的直觉来源是：当还剩 $k$ 种没收集时，每次命中的概率只有 $k/n$，需要 $n/k$ 次；把 $k=1,\dots,n$ 累加就得到 $nH_n$。

随机变量的独立性

上一讲定义了事件的独立性，现在推广到随机变量。

定义。 随机变量 $f,g$ 独立，若对任意实数 $\alpha,\beta$，事件

$$\{x:f(x)=\alpha\}, \qquad \{x:g(x)=\beta\}$$

都独立，即

$$P(f=\alpha,\ g=\beta)=P(f=\alpha)\,P(g=\beta).$$

注意这里有一个对所有 $\alpha,\beta$ 成立的量词，所以验证起来比事件独立麻烦得多。

一致性检查：取 $f=\mathbf{1}_A$、$g=\mathbf{1}_B$，此时 $\alpha,\beta$ 只需取 $0,1$，定义退化为「事件 $A$ 与 $B$ 独立」。所以随机变量的独立性确实是事件独立性的推广。

引理：独立随机变量的乘积期望

引理。 若 $f,g$ 独立，则

$$\mathbb{E}[fg]=\mathbb{E}[f]\,\mathbb{E}[g].$$

证明。 按定义展开，并按 $f,g$ 的取值把样本空间分块：

$$\mathbb{E}[fg]=\sum_{x}p(x)f(x)g(x) =\sum_{\alpha,\beta}\alpha\beta\sum_{x:\,f(x)=\alpha,\,g(x)=\beta}p(x).$$

内层和正是 $P(f=\alpha,\ g=\beta)$。由独立性，

$$\mathbb{E}[fg] =\sum_{\alpha,\beta}\alpha\beta\,P(f=\alpha)P(g=\beta) =\left(\sum_{\alpha}\alpha P(f=\alpha)\right) \left(\sum_{\beta}\beta P(g=\beta)\right) =\mathbb{E}[f]\,\mathbb{E}[g].$$

最后一步是把双重和拆成两个独立求和，并认出它们分别是期望的另一种写法（按取值分组求和）。$\square$

独立性不可省

取 $f=\mathbf{1}_A$、$g=\mathbf{1}_{A^{c}}$，其中 $0<P(A)<1$。两者显然不独立。此时

$$fg=\mathbf{1}_{A}\mathbf{1}_{A^{c}}=0 \quad\Longrightarrow\quad \mathbb{E}[fg]=0,$$

但

$$\mathbb{E}[f]\,\mathbb{E}[g]=P(A)\,(1-P(A))>0 .$$

所以没有独立性，引理不成立。这个反例也提醒：证明中用到独立性的一步，正是把联合概率拆成乘积的那一步。

方差

定义

随机变量 $f$ 的方差是

$$\operatorname{Var}(f)=\mathbb{E}\left[\bigl(f(x)-\mathbb{E}[f]\bigr)^2\right].$$

它先减去均值，把分布平移到中心为 $0$，再对偏离量的平方取期望。方差衡量的是随机变量有多分散，是一个粗粒度的指标。

两种等价写法

展开平方并用线性性：

$$\begin{aligned} \operatorname{Var}(f) &=\mathbb{E}\left[f^2-2f\,\mathbb{E}[f]+(\mathbb{E}[f])^2\right]\\ &=\mathbb{E}[f^2]-2\mathbb{E}[f]\,\mathbb{E}[f]+(\mathbb{E}[f])^2\\ &=\mathbb{E}[f^2]-(\mathbb{E}[f])^2 . \end{aligned}$$

第二行用到关键一点：$\mathbb{E}[f]$ 是常数，不是随机变量，所以可以从期望里提出来。两种写法各有方便之处，视情况选用。

两条基本性质

• 非负性：$\operatorname{Var}(f)\ge0$，因为它是一个非负随机变量的期望。
• 为零即常数：$\operatorname{Var}(f)=0$ 当且仅当 $f$ 取常数值。若方差为零，则 $(f-\mathbb{E}[f])^2$ 的期望为零；由于它非负，只能处处为零，故 $f=\mathbb{E}[f]$ 恒成立。

独立随机变量的方差可加

定理。 若 $f,g$ 独立，则

$$\operatorname{Var}(f+g)=\operatorname{Var}(f)+\operatorname{Var}(g).$$

证明。 记 $\mu_f=\mathbb{E}[f]$、$\mu_g=\mathbb{E}[g]$。由定义并利用期望的线性性，

$$\begin{aligned} \operatorname{Var}(f+g) &=\mathbb{E}\left[\bigl((f-\mu_f)+(g-\mu_g)\bigr)^2\right]\\ &=\mathbb{E}\left[(f-\mu_f)^2\right] +2\,\mathbb{E}\left[(f-\mu_f)(g-\mu_g)\right] +\mathbb{E}\left[(g-\mu_g)^2\right]\\ &=\operatorname{Var}(f)+\operatorname{Var}(g) +2\,\mathbb{E}\left[(f-\mu_f)(g-\mu_g)\right]. \end{aligned}$$

剩下的是交叉项。由独立性，$f-\mu_f$ 与 $g-\mu_g$ 也独立，于是乘积的期望等于期望的乘积：

$$\mathbb{E}\left[(f-\mu_f)(g-\mu_g)\right] =\mathbb{E}[f-\mu_f]\,\mathbb{E}[g-\mu_g]=0\cdot0=0 .$$

交叉项消失，结论成立。$\square$

这次线性性不够用了：如果 $f,g$ 不独立，交叉项一般不为零，方差就不一定可加。这正是课程反复强调的对比——期望的线性性无条件成立，方差的可加性需要独立性。

这些工具通向哪里

方差可加是后面「集中不等式」的起点。设想做民意调查：随机抽取 $n$ 个人，每人以概率 $p$ 支持某候选人，用 $\hat p$ 表示样本中的支持比例，

$$\hat p=\frac1n\sum_{i=1}^{n}\mathbf{1}_{A_i}.$$

每个 $\mathbf{1}_{A_i}$ 的方差是 $p(1-p)$；由独立性，$\hat p$ 的方差是

$$\operatorname{Var}(\hat p)=\frac{1}{n^2}\cdot n\,p(1-p)=\frac{p(1-p)}{n}.$$

方差按 $1/n$ 衰减，标准差按 $1/\sqrt n$ 衰减——这就是「样本量翻四倍，误差减半」的来源。下一阶段的课程会用尾界把这个结论变成严格的置信区间。

本节结论

• 容斥公式：并的概率等于「单事件和 − 两两交和 + 三重交和 − …」，符号交替。
• 符号交替的原因：恰好属于 $r$ 个事件的结果被计数 $\sum_{k=1}^r(-1)^{k+1}\binom rk=1$ 次。
• 错排问题：$P(\text{无人拿对})=\sum_{r=0}^{n}(-1)^r/r!\to1/e$。
• 二项式系数 $\binom nr=\frac{n(n-1)\cdots(n-r+1)}{r!}$ 用来数 $r$ 重交的项数。
• 期望线性性无需独立性：拿到自己作业的人数期望恒为 $1$。
• 优惠券收集：把总时间拆成阶段，$\mathbb{E}[T]=nH_n\approx n\ln n$；$n=365$ 时约为 $2361$。
• 独立随机变量满足 $\mathbb{E}[fg]=\mathbb{E}[f]\mathbb{E}[g]$；不独立时可能失败（如 $\mathbf{1}_A$ 与 $\mathbf{1}_{A^c}$）。
• 方差 $\operatorname{Var}(f)=\mathbb{E}[(f-\mathbb{E}f)^2]=\mathbb{E}[f^2]-(\mathbb{E}f)^2\ge0$，为零当且仅当 $f$ 为常数。
• 独立随机变量的方差可加；没有独立性时交叉项一般不为零。

理解检验

1. $n=2$ 时，为什么 $P(A_1\cap A_2)=1/2$ 而不是 $1/4$？

参考答案：样本空间是两名学生的全部排列，只有 $2$ 个：两人各自拿到自己的作业，或两人互换。事件 $A_1\cap A_2$「两人都拿到自己的作业」只包含第一个排列，所以概率是 $1/2$。若误用独立性写成 $P(A_1)P(A_2)=1/2\cdot1/2=1/4$，就错了：一旦第一个人拿到自己的作业，剩下的作业只剩一份，第二个人必然也拿到自己的，两者高度相关。一般地，$P(A_i\cap A_j)=1/(n(n-1))$，而不是 $1/n^2$。

2. 写出容斥公式，并解释为什么符号必须交替。

参考答案：

$$P\!\left(\bigcup_{i=1}^n A_i\right)=\sum_i P(A_i)-\sum_{i<j}P(A_i\cap A_j)+\sum_{i<j<k}P(A_i\cap A_j\cap A_k)-\cdots+(-1)^{n+1}P(A_1\cap\cdots\cap A_n).$$

设某结果恰好属于 $r$ 个事件。它在「单事件和」里被计 $\binom r1$ 次，在「两两交和」里被计 $\binom r2$ 次，依此类推，总次数为

$$\binom r1-\binom r2+\binom r3-\cdots+(-1)^{r-1}\binom rr=1-(1-1)^r=1.$$

所以每个结果恰好被计一次。若符号不交替，这个和就不可能恒为 $1$：多计或少计都取决于 $r$，无法统一修正。

3. 用容斥计算 $n=4$ 时「无人拿对」的概率。

参考答案：

$$P(\text{至少一人拿对})=\binom41\frac14-\binom42\frac{1}{4\cdot3}+\binom43\frac{1}{4\cdot3\cdot2}-\frac{1}{4!} =1-\frac{6}{12}+\frac{4}{24}-\frac{1}{24} =1-\frac12+\frac16-\frac1{24}.$$

于是

$$P(\text{无人拿对})=\frac12-\frac16+\frac1{24}=\frac{12-4+1}{24}=\frac{9}{24}=\frac38=0.375 .$$

与错排数 $D_4=9$、总排列数 $4!=24$ 一致。

4. 为什么「拿到自己作业的人数期望为 $1$」不需要利用 $A_i$ 之间的独立性？优惠券收集问题在哪里用了同一招？

参考答案：期望的线性性对任意随机变量成立：

$$\mathbb{E}\Bigl[\sum_i \mathbf{1}_{A_i}\Bigr]=\sum_i \mathbb{E}[\mathbf{1}_{A_i}]=\sum_i P(A_i),$$

推导只用到「和的期望等于期望的和」，与 $A_i$ 是否独立无关。$P(A_i)=1/n$ 对每个 $i$ 都成立，求和得 $n\cdot(1/n)=1$。优惠券收集问题同样把总时间拆成阶段 $T=\sum_{i=0}^{n-1}T_i$，每个 $T_i$ 是成功概率 $(n-i)/n$ 的几何分布，期望 $n/(n-i)$；相加得 $nH_n$。拆分的合法性只依赖线性性，不依赖各阶段之间的相关性。

5. 举一个反例说明 $\mathbb{E}[fg]=\mathbb{E}[f]\mathbb{E}[g]$ 在没有独立性时不成立。

参考答案：取 $f=\mathbf{1}_A$、$g=\mathbf{1}_{A^{c}}$，其中 $0<P(A)<1$。因为一个结果不可能同时在 $A$ 与 $A^c$ 中，所以 $fg\equiv0$，故 $\mathbb{E}[fg]=0$。但

$$\mathbb{E}[f]\mathbb{E}[g]=P(A)\,(1-P(A))>0 .$$

两者不等。这两个随机变量显然不独立（知道 $f$ 的值就完全确定了 $g$），说明引理中的独立性条件不可省。

6. 方差可加为什么需要独立性？请指出证明中哪一步失效。

参考答案：展开

$$\operatorname{Var}(f+g)=\operatorname{Var}(f)+\operatorname{Var}(g)+2\,\mathbb{E}[(f-\mu_f)(g-\mu_g)].$$

证明独立时交叉项为零，依据是「独立随机变量的乘积期望等于期望的乘积」：

$$\mathbb{E}[(f-\mu_f)(g-\mu_g)]=\mathbb{E}[f-\mu_f]\,\mathbb{E}[g-\mu_g]=0.$$

若 $f,g$ 不独立，这一步不能做，交叉项一般不为零，方差也就不可加。反例：取 $g=f$，则 $\operatorname{Var}(f+g)=\operatorname{Var}(2f)=4\operatorname{Var}(f)$，而 $\operatorname{Var}(f)+\operatorname{Var}(g)=2\operatorname{Var}(f)$，两者相差一倍，交叉项为 $2\operatorname{Var}(f)$。

与前后课的关系

这一讲把概率的三件工具串了起来：容斥负责「至少一个事件」的精确计数，期望线性性负责绕开依赖关系，方差可加性则预告了集中不等式。下一讲正式进入计数单元，系统处理排列、组合与二项式系数；之后生成函数会把这里出现的 $1/e$、$nH_n$ 与 $\binom nr$ 放进同一个代数框架里。

一句话概括这一讲：只要会「先过计再修正」，并，就变成了和；只要会用指示函数，计数就变成了期望。

A problem about handing back problem sets

A class of $n$ students submits one problem set each. After grading, the sets are handed back at random — equivalently, a uniformly random permutation of the $n$ sets is chosen.

What is the probability that nobody receives their own problem set?

This is the classical derangement problem. Intuitively, when $n$ is large the probability should settle near some constant — and that constant turns out to be $1/e\approx0.368$.

The tool that produces the answer is inclusion–exclusion. Its idea is as plain as can be: count in the crudest possible way, notice that you over-counted, subtract the excess, notice that you subtracted too much, add something back, and keep correcting until the count is exact.

Timeline

Writing the problem in terms of events

Let $A_i$ be the event that student $i$ receives their own problem set. We want

$$P(\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_n}).$$

This intersection is hard to compute directly, but its complement is easy to describe: at least one student receives their own set. By De Morgan,

$$\overline{\overline{A_1}\cap\cdots\cap\overline{A_n}}=A_1\cup A_2\cup\cdots\cup A_n .$$

Hence

$$P(\text{nobody correct})=1-P(A_1\cup\cdots\cup A_n).$$

The problem reduces to computing the probability of a union of $n$ events.

Inclusion–exclusion: over-count, then correct

Figure：The n=3 derangement example: Venn counts, the correction ladder, the general formula。

The case $n=2$

Draw two overlapping disks $A_1$ and $A_2$. The crudest estimate is

$$P(A_1)+P(A_2).$$

Under this count the intersection $A_1\cap A_2$ is counted twice, so subtract one copy:

$$P(A_1\cup A_2)=P(A_1)+P(A_2)-P(A_1\cap A_2).$$

That is inclusion–exclusion in embryo.

For our problem with $n=2$: the only permutations of two students are "both correct" and "they swap". Therefore

$$P(A_1)=\frac12,\quad P(A_2)=\frac12,\quad P(A_1\cap A_2)=\frac12,$$

since the only outcome satisfying both is the identity permutation. Thus

$$P(A_1\cup A_2)=\frac12+\frac12-\frac12=\frac12, \qquad P(\text{nobody correct})=1-\frac12=\frac12 .$$

Note that $P(A_1\cap A_2)=1/2\ne1/4$: the events are not independent. Once the first student receives their own set, the remaining set is forced, so the second student is automatically correct. This is exactly why the problem cannot be handled by naive multiplication.

The case $n=3$

Adding the three single events over-counts the pairwise overlaps; subtracting the three pairwise intersections over-corrects the common centre $A_1\cap A_2\cap A_3$, which was added three times and subtracted three times — net count zero. So add it back once:

$$P(A_1\cup A_2\cup A_3) =P(A_1)+P(A_2)+P(A_3) -P(A_1\cap A_2)-P(A_1\cap A_3)-P(A_2\cap A_3) +P(A_1\cap A_2\cap A_3).$$

Plug in: $P(A_i)=1/3$; if two students are correct, the third has no choice, so $P(A_i\cap A_j)=1/6$; and the triple intersection is again only the identity, $P(A_1\cap A_2\cap A_3)=1/6$. Hence

$$P(\text{at least one correct})=3\cdot\frac13-3\cdot\frac16+\frac16 =1-\frac12+\frac16=\frac23,$$ $$P(\text{nobody correct})=1-\frac23=\frac13 .$$

This matches $D_3/3!=2/6=1/3$, where $D_3$ is the number of derangements.

The general formula

For arbitrary events $A_1,\dots,A_n$,

$$P\!\left(\bigcup_{i=1}^{n}A_i\right) =\sum_{i}P(A_i) -\sum_{i<j}P(A_i\cap A_j) +\sum_{i<j<k}P(A_i\cap A_j\cap A_k) -\cdots +(-1)^{n+1}P(A_1\cap\cdots\cap A_n).$$

In words: singles add, pairs subtract, triples add, quadruples subtract, signs alternating up to the $n$-fold intersection.

Why must the signs alternate? Consider an outcome lying in exactly $r$ of the events. It is counted

$$\binom{r}{1}-\binom{r}{2}+\binom{r}{3}-\cdots+(-1)^{r+1}\binom{r}{r} =1-(1-1)^r=1$$

times, since the binomial expansion gives $(1-1)^r=0$ for $r\ge1$. Every outcome is therefore counted exactly once.

Back to the original problem

The individual probabilities

Handing back the sets is a uniformly random choice among the $n!$ permutations. For any $i$,

$$P(A_i)=\frac{(n-1)!}{n!}=\frac1n .$$

For $r$ specified students all to be correct, the other $n-r$ sets can be permuted freely, so

$$P(A_{i_1}\cap\cdots\cap A_{i_r}) =\frac{(n-r)!}{n!} =\frac{1}{n(n-1)\cdots(n-r+1)} .$$

This is the conditional-probability reading: the first student is correct with probability $1/n$; given that, the second is correct with probability $1/(n-1)$; and so on.

Counting the terms: binomial coefficients

In the inclusion–exclusion formula there are $\binom{n}{r}$ terms at level $r$, where

$$\binom{n}{r}=\frac{n(n-1)\cdots(n-r+1)}{r!}=\frac{n!}{r!\,(n-r)!}.$$

It counts the ways to choose $r$ objects from $n$. The numerator chooses them in order — $n$ choices, then $n-1$, and so on — but that counts each set $r!$ times, hence the division. In particular

$$\binom{n}{2}=\frac{n(n-1)}{2}.$$

Summing

Multiply the number of terms by the value of each term:

$$P\!\left(\bigcup_i A_i\right) =\binom{n}{1}\frac{1}{n} -\binom{n}{2}\frac{1}{n(n-1)} +\binom{n}{3}\frac{1}{n(n-1)(n-2)} -\cdots$$

Enormous cancellation occurs. For the second term,

$$\binom{n}{2}\cdot\frac{1}{n(n-1)} =\frac{n(n-1)}{2}\cdot\frac{1}{n(n-1)} =\frac{1}{2!},$$

and in general the $r$-th term equals $1/r!$. Therefore

$$P(\text{at least one correct}) =1-\frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!}+\cdots+(-1)^{n+1}\frac{1}{n!}.$$

So

$$P(\text{nobody correct}) =1-P(\text{at least one correct}) =\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^{n}\frac{1}{n!}.$$

Padding with the cancelling first two terms $1-1=0$, this is

$$P(\text{nobody correct})=\sum_{r=0}^{n}\frac{(-1)^r}{r!}.$$

As $n\to\infty$,

$$\sum_{r=0}^{\infty}\frac{(-1)^r}{r!}=\frac1e\approx0.3679 .$$

The number $e$ emerges from a pure permutation-counting problem. Numerically: $1/2$ for $n=2$, $1/3$ for $n=3$, $9/24=0.375$ for $n=4$, after which the values oscillate around $1/e$ and converge quickly.

A useful heuristic

Strictly, the $A_i$ are not independent. But for large $n$ they are "almost independent": whether the first student is correct changes the second student's chance by only about $1/n$. So the loose calculation

$$P(\text{nobody correct})\approx\prod_{i=1}^{n}\left(1-\frac1n\right) =\left(1-\frac1n\right)^{n}\xrightarrow[n\to\infty]{}\frac1e$$

gives the right answer. This is not a proof — independence fails — but inclusion–exclusion is exactly what turns the "almost independent" intuition into a theorem.

Inductive proof of inclusion–exclusion

Theorem. The formula above holds for all events $A_1,\dots,A_n$.

Proof. Induct on $n$. The case $n=2$ is the Venn-diagram identity.

Assume the formula holds for $n$, and set $C=A_1\cup\cdots\cup A_n$. Consider the formula for $n+1$ events and split its terms into those not containing $A_{n+1}$ and those containing $A_{n+1}$.

The terms not containing $A_{n+1}$ are precisely the inclusion–exclusion formula for the first $n$ events, so by the induction hypothesis they sum to $P(C)$.

The terms containing $A_{n+1}$ have the opposite sign to their counterparts in the $n$-event formula. Define helper events

$$B_i=A_i\cap A_{n+1}\qquad(i=1,\dots,n).$$

Then that group of terms is $-1$ times the inclusion–exclusion formula applied to $B_1,\dots,B_n$, because

$$B_i\cap B_j=(A_i\cap A_{n+1})\cap(A_j\cap A_{n+1})=A_i\cap A_j\cap A_{n+1}$$

(intersecting twice with $A_{n+1}$ is the same as once). By the induction hypothesis the group equals

$$-P(B_1\cup\cdots\cup B_n) =-P\bigl((A_1\cup\cdots\cup A_n)\cap A_{n+1}\bigr) =-P(C\cap A_{n+1}).$$

Adding the two groups gives

$$P(C)+P(A_{n+1})-P(C\cap A_{n+1}),$$

which is the $n=2$ identity applied to $C$ and $A_{n+1}$, hence equals $P(C\cup A_{n+1})=P(A_1\cup\cdots\cup A_{n+1})$. This completes the induction. $\square$

What matters here is not the algebra but the structure: split the $n+1$ expression into "the old formula" and "minus the old formula", then reinterpret the latter in terms of new helper events. Designing the reader's path through a proof matters more than checking it line by line.

One line with linearity of expectation

Inclusion–exclusion took a whole lecture to get "nobody correct". Now ask a neighbouring question: what is the expected number of students who receive their own set?

Define

$$X=\sum_{i=1}^{n}\mathbf{1}_{A_i},$$

the number of correct returns. By linearity of expectation, with no independence assumption whatsoever,

$$\mathbb{E}[X]=\sum_{i=1}^{n}\mathbb{E}[\mathbf{1}_{A_i}] =\sum_{i=1}^{n}P(A_i) =\sum_{i=1}^{n}\frac1n=1 .$$

The expectation is exactly one, independent of $n$.

This is where linearity earns its keep: it sidesteps dependence entirely. The $A_i$ are highly correlated — one correct return drastically changes everyone else's chances — yet additivity of expectation does not care. The lecture stresses the contrast: this works for expectations, but not for products of expectations, and not for variances.

The coupon collector problem

The question

Each newspaper comes with one of $n$ coupons, uniformly and independently. How many newspapers must be bought on average to collect all $n$? With $n=365$, this is "how many students must be asked to see every birthday".

Split into stages

The key trick is again to decompose a complicated random variable into simple ones. Let

$$T=T_0+T_1+\cdots+T_{n-1},$$

where $T_i$ is the number of newspapers needed to go from $i$ distinct coupons to $i+1$.

Having collected $i$ kinds, the probability that the next paper brings a new one is

$$p_i=\frac{n-i}{n},$$

since $n-i$ of the $n$ kinds are still unseen. Attempts are independent, so $T_i$ is geometric with success probability $p_i$, and by the previous lecture

$$\mathbb{E}[T_i]=\frac1{p_i}=\frac{n}{n-i}.$$

Summing

$$\mathbb{E}[T]=\sum_{i=0}^{n-1}\frac{n}{n-i} =n\left(\frac1n+\frac1{n-1}+\cdots+\frac11\right) =nH_n,$$

where $H_n=\sum_{k=1}^{n}1/k$ is the $n$-th harmonic number. For $n=365$,

$$H_{365}\approx6.47, \qquad \mathbb{E}[T]\approx6.47\times365\approx2361 .$$

So about $2361$ students must be asked to cover all $365$ birthdays — roughly $6.5$ times the number of days.

Asymptotics

Since $H_n\approx\ln n+\gamma$ with $\gamma\approx0.577$,

$$\mathbb{E}[T]=nH_n\approx n\ln n .$$

The rule of thumb "covering $n$ kinds takes $n\log n$ draws" follows. Intuition: with $k$ kinds still missing, each draw hits a new one with probability $k/n$, so waiting takes $n/k$ draws; summing $k=1,\dots,n$ gives $nH_n$.

Independence of random variables

The previous lecture defined independence for events; now extend it to random variables.

Definition. Random variables $f,g$ are independent if for all real $\alpha,\beta$ the events

$$\{x:f(x)=\alpha\}, \qquad \{x:g(x)=\beta\}$$

are independent:

$$P(f=\alpha,\ g=\beta)=P(f=\alpha)\,P(g=\beta).$$

Note the quantifier "for all $\alpha,\beta$", which makes verification much harder than for events.

Consistency check: take $f=\mathbf{1}_A$ and $g=\mathbf{1}_B$; then $\alpha,\beta$ need only range over $0,1$ and the definition collapses to independence of the events $A$ and $B$. So independence of random variables genuinely extends independence of events.

Lemma: the product rule for independent variables

Lemma. If $f,g$ are independent, then

$$\mathbb{E}[fg]=\mathbb{E}[f]\,\mathbb{E}[g].$$

Proof. Expand the definition and partition the sample space according to the values taken:

$$\mathbb{E}[fg]=\sum_{x}p(x)f(x)g(x) =\sum_{\alpha,\beta}\alpha\beta\sum_{x:\,f(x)=\alpha,\,g(x)=\beta}p(x).$$

The inner sum is $P(f=\alpha,\ g=\beta)$. By independence,

$$\mathbb{E}[fg] =\sum_{\alpha,\beta}\alpha\beta\,P(f=\alpha)P(g=\beta) =\left(\sum_{\alpha}\alpha P(f=\alpha)\right) \left(\sum_{\beta}\beta P(g=\beta)\right) =\mathbb{E}[f]\,\mathbb{E}[g].$$

The last step factors the double sum and recognises each factor as the expectation written by grouping equal values. $\square$

Independence cannot be dropped

Take $f=\mathbf{1}_A$ and $g=\mathbf{1}_{A^{c}}$ with $0<P(A)<1$. They are clearly dependent. Then

$$fg=\mathbf{1}_{A}\mathbf{1}_{A^{c}}=0 \quad\Longrightarrow\quad \mathbb{E}[fg]=0,$$

yet

$$\mathbb{E}[f]\,\mathbb{E}[g]=P(A)\,(1-P(A))>0 .$$

So without independence the lemma fails. The counterexample also pinpoints the step where independence is used: splitting the joint probability into a product.

Variance

Definition

The variance of a random variable $f$ is

$$\operatorname{Var}(f)=\mathbb{E}\left[\bigl(f(x)-\mathbb{E}[f]\bigr)^2\right].$$

It shifts the distribution so its centre is $0$, then averages the squared deviations. Variance is a coarse measure of how spread out the random variable is.

Two equivalent formulas

Expand the square and use linearity:

$$\begin{aligned} \operatorname{Var}(f) &=\mathbb{E}\left[f^2-2f\,\mathbb{E}[f]+(\mathbb{E}[f])^2\right]\\ &=\mathbb{E}[f^2]-2\mathbb{E}[f]\,\mathbb{E}[f]+(\mathbb{E}[f])^2\\ &=\mathbb{E}[f^2]-(\mathbb{E}[f])^2 . \end{aligned}$$

The middle line uses one key fact: $\mathbb{E}[f]$ is a constant, not a random variable, so it factors out of the expectation. Both forms are useful in different situations.

Two basic properties

• Non-negativity: $\operatorname{Var}(f)\ge0$, since it is the expectation of a non-negative random variable.
• Zero means constant: $\operatorname{Var}(f)=0$ if and only if $f$ is constant. If the variance is zero, the expectation of $(f-\mathbb{E}[f])^2$ is zero; being non-negative, it must vanish identically, so $f=\mathbb{E}[f]$ everywhere.

Variances add for independent variables

Theorem. If $f,g$ are independent, then

$$\operatorname{Var}(f+g)=\operatorname{Var}(f)+\operatorname{Var}(g).$$

Proof. Write $\mu_f=\mathbb{E}[f]$, $\mu_g=\mathbb{E}[g]$. By definition and linearity,

$$\begin{aligned} \operatorname{Var}(f+g) &=\mathbb{E}\left[\bigl((f-\mu_f)+(g-\mu_g)\bigr)^2\right]\\ &=\mathbb{E}\left[(f-\mu_f)^2\right] +2\,\mathbb{E}\left[(f-\mu_f)(g-\mu_g)\right] +\mathbb{E}\left[(g-\mu_g)^2\right]\\ &=\operatorname{Var}(f)+\operatorname{Var}(g) +2\,\mathbb{E}\left[(f-\mu_f)(g-\mu_g)\right]. \end{aligned}$$

Only the cross term remains. By independence, $f-\mu_f$ and $g-\mu_g$ are independent, so the expectation of the product is the product of expectations:

$$\mathbb{E}\left[(f-\mu_f)(g-\mu_g)\right] =\mathbb{E}[f-\mu_f]\,\mathbb{E}[g-\mu_g]=0\cdot0=0 .$$

The cross term vanishes, proving the claim. $\square$

Linearity alone is not enough here: without independence the cross term is generally nonzero and variances do not add. This is the contrast the lecture keeps emphasising — linearity of expectation is unconditional; additivity of variance requires independence.

Where these tools lead

Additivity of variance is the seed of the concentration inequalities later in the course. Consider polling: sample $n$ people, each supporting a candidate with probability $p$, and let $\hat p$ be the sample proportion,

$$\hat p=\frac1n\sum_{i=1}^{n}\mathbf{1}_{A_i}.$$

Each indicator has variance $p(1-p)$; by independence,

$$\operatorname{Var}(\hat p)=\frac{1}{n^2}\cdot n\,p(1-p)=\frac{p(1-p)}{n}.$$

The variance decays like $1/n$, so the standard deviation decays like $1/\sqrt n$ — the origin of "quadruple the sample, halve the error". Later lectures turn this into rigorous confidence intervals via tail bounds.

What this lecture establishes

• Inclusion–exclusion: the probability of a union equals "singles − pairs + triples − …", with alternating signs.
• Why signs alternate: an outcome in exactly $r$ events is counted $\sum_{k=1}^r(-1)^{k+1}\binom rk=1$ time.
• Derangements: $P(\text{nobody correct})=\sum_{r=0}^{n}(-1)^r/r!\to1/e$.
• Binomial coefficients $\binom nr=\frac{n(n-1)\cdots(n-r+1)}{r!}$ count the terms at level $r$.
• Linearity of expectation needs no independence: the expected number of correct returns is always $1$.
• Coupon collector: split into stages to get $\mathbb{E}[T]=nH_n\approx n\ln n$; about $2361$ for $n=365$.
• Independent random variables satisfy $\mathbb{E}[fg]=\mathbb{E}[f]\mathbb{E}[g]$; without independence it can fail ($\mathbf{1}_A$ and $\mathbf{1}_{A^c}$).
• Variance $\operatorname{Var}(f)=\mathbb{E}[(f-\mathbb{E}f)^2]=\mathbb{E}[f^2]-(\mathbb{E}f)^2\ge0$, zero exactly for constants.
• Variances of independent random variables add; without independence the cross term is generally nonzero.

Comprehension check

1. For $n=2$, why is $P(A_1\cap A_2)=1/2$ rather than $1/4$?

Reference answer: The sample space is the set of all permutations of two students, of which there are only two: both correct, or they swap. The event $A_1\cap A_2$ contains only the first, so its probability is $1/2$. Using independence to write $P(A_1)P(A_2)=1/2\cdot1/2=1/4$ is wrong: once the first student receives their own set, only one set remains, so the second must also be correct. In general $P(A_i\cap A_j)=1/(n(n-1))$, not $1/n^2$.

2. State inclusion–exclusion and explain why the signs must alternate.

Reference answer:

$$P\!\left(\bigcup_{i=1}^n A_i\right)=\sum_i P(A_i)-\sum_{i<j}P(A_i\cap A_j)+\sum_{i<j<k}P(A_i\cap A_j\cap A_k)-\cdots+(-1)^{n+1}P(A_1\cap\cdots\cap A_n).$$

An outcome lying in exactly $r$ events is counted

$$\binom r1-\binom r2+\binom r3-\cdots+(-1)^{r-1}\binom rr=1-(1-1)^r=1$$

times, so every outcome is counted once. Without alternating signs this total would depend on $r$ and could not equal $1$ uniformly.

3. Use inclusion–exclusion to compute the probability that nobody is correct for $n=4$.

Reference answer:

$$P(\text{at least one correct})=\binom41\frac14-\binom42\frac{1}{4\cdot3}+\binom43\frac{1}{4\cdot3\cdot2}-\frac{1}{4!} =1-\frac{6}{12}+\frac{4}{24}-\frac{1}{24} =1-\frac12+\frac16-\frac1{24}.$$

Hence

$$P(\text{nobody correct})=\frac12-\frac16+\frac1{24}=\frac{12-4+1}{24}=\frac{9}{24}=\frac38=0.375,$$

consistent with $D_4=9$ derangements out of $4!=24$.

4. Why does "the expected number of correct returns is $1$" need no independence? Where does the coupon collector use the same trick?

Reference answer: Linearity of expectation holds for arbitrary random variables:

$$\mathbb{E}\Bigl[\sum_i \mathbf{1}_{A_i}\Bigr]=\sum_i \mathbb{E}[\mathbf{1}_{A_i}]=\sum_i P(A_i),$$

using only "expectation of a sum is the sum of expectations", with no independence. Since $P(A_i)=1/n$ for every $i$, the sum is $n\cdot(1/n)=1$. The coupon collector splits $T=\sum_{i=0}^{n-1}T_i$ into stages; each $T_i$ is geometric with success probability $(n-i)/n$ and expectation $n/(n-i)$; summing gives $nH_n$. The splitting is justified by linearity alone, regardless of dependence between stages.

5. Give a counterexample showing $\mathbb{E}[fg]=\mathbb{E}[f]\mathbb{E}[g]$ fails without independence.

Reference answer: Take $f=\mathbf{1}_A$, $g=\mathbf{1}_{A^{c}}$ with $0<P(A)<1$. No outcome lies in both $A$ and $A^c$, so $fg\equiv0$ and $\mathbb{E}[fg]=0$. But

$$\mathbb{E}[f]\mathbb{E}[g]=P(A)(1-P(A))>0 .$$

They differ. These variables are clearly dependent — knowing $f$ determines $g$ — showing that the independence hypothesis is essential.

6. Why does additivity of variance require independence? Which step fails otherwise?

Reference answer: Expanding gives

$$\operatorname{Var}(f+g)=\operatorname{Var}(f)+\operatorname{Var}(g)+2\,\mathbb{E}[(f-\mu_f)(g-\mu_g)].$$

Under independence the cross term is zero because the product rule applies:

$$\mathbb{E}[(f-\mu_f)(g-\mu_g)]=\mathbb{E}[f-\mu_f]\,\mathbb{E}[g-\mu_g]=0.$$

Without independence that step is invalid and the cross term is generally nonzero, so variances do not add. Counterexample: $g=f$ gives $\operatorname{Var}(f+g)=\operatorname{Var}(2f)=4\operatorname{Var}(f)$, while $\operatorname{Var}(f)+\operatorname{Var}(g)=2\operatorname{Var}(f)$; the cross term contributes the missing $2\operatorname{Var}(f)$.

Relation to neighbouring lectures

This lecture links three tools: inclusion–exclusion for exact counts of "at least one event", linearity of expectation for bypassing dependence, and additivity of variance as a preview of concentration. The next lecture begins the counting unit — permutations, combinations and binomial coefficients — and generating functions later place $1/e$, $nH_n$ and $\binom nr$ inside one algebraic framework.

One sentence to keep: once you can over-count and then correct, a union becomes a sum; once you can use indicators, counting becomes expectation.