一百万人重新洗牌，平均只有一顶帽子拿对

错排比例 ≈ 1/e，与 n 无关

English（原书原文）

Let $Y$ be the number of fixed points in a random permutation of the set $\{a, b, c\}$. To find the expected value of $Y$, it is helpful to consider the basic random variable associated with this experiment, namely the random variable $X$ which represents the random permutation. There are six possible outcomes of $X$, and we assign to each of them the probability $1/6$. Then we can calculate $E(Y)$ as

$$3\Bigl(\frac{1}{6}\Bigr) + 1\Bigl(\frac{1}{6}\Bigr) + 1\Bigl(\frac{1}{6}\Bigr) + 0\Bigl(\frac{1}{6}\Bigr) + 0\Bigl(\frac{1}{6}\Bigr) + 1\Bigl(\frac{1}{6}\Bigr) = 1.$$

We now give a very quick way to calculate the average number of fixed points in a random permutation of the set $\{1, 2, 3, \ldots, n\}$. Let $Z$ denote the random permutation. For each $i$, $1 \le i \le n$, let $X_i$ equal 1 if $Z$ fixes $i$, and 0 otherwise. So if we let $F$ denote the number of fixed points in $Z$, then

$$F = X_1 + X_2 + \cdots + X_n.$$

Therefore we have

$$E(F) = E(X_1) + E(X_2) + \cdots + E(X_n).$$

But it is easy to see that for each $i$, $E(X_i) = \frac{1}{n}$, so

$$E(F) = 1.$$

This method of calculation of the expected value is frequently very useful. It applies whenever the random variable in question can be written as a sum of simpler random variables. We emphasize again that it is not necessary that the summands be mutually independent.

一个醉汉和一家衣帽间

剧场散场，衣帽间的服务员今晚喝多了。

他把 $n$ 顶帽子一股脑搅乱，然后随便递出去——第 1 位客人拿到第 1 顶的概率跟其他人完全一样，谁也占不到便宜。

问：平均有几顶帽子，恰好回到了主人头上？

三个人、三顶帽子的时候，这道题能在黑板前数完。

六个可能的结果，每个概率都是 $1/6$：

交换结果	谁拿对了	拿对人数
1→1, 2→2, 3→3	三个人全拿对	3
1→1, 2→3, 3→2	只有第 1 人	1
1→2, 2→1, 3→3	只有第 3 人	1
1→2, 2→3, 3→1	没人	0
1→3, 2→1, 3→2	没人	0
1→3, 2→2, 3→1	只有第 2 人	1

平均一下：

$$3\cdot\frac16 + 1\cdot\frac16 + 1\cdot\frac16 + 0\cdot\frac16 + 0\cdot\frac16 + 1\cdot\frac16 = 1.$$

三个人，平均一顶拿对。

现在把问题放大：一百万个人，一百万顶帽子。 平均几顶拿对？

先让学生猜。绝大多数人会往大猜——人越多，排列越多，总能碰上几个吧；也有人往小猜——一百万顶里撞对一顶，机会总该微乎其微吧。

正确答案是 1。

不是"接近 1"，不是"大约 1"。一百万人、一亿人、无论多少人，只要搅得够随机，平均恰好 1 顶拿对。

这道题在问什么

这道题问的是一个平均数，可它真正要打碎的是一样东西：你对"规模"的直觉。

学生的直觉是这样的链条：$n$ 越大 → 越难撞对 → 平均值该随 $n$ 变。

这个链条看起来天经地义。而它错得很彻底。

原书写得很冷静：先老老实实数 $n=3$ 的六种情况，然后话锋一转，说"我们 now give a very quick way"——给出一个不数的方法。

这个方法的思想只有一句话：

别去数"总共几个人拿对"。一个一个单独看。

算一下

第一步：$n=3$ 已经数出来了，答案是 1。

上表已经做完。这一步的作用是让学生相信 1 这个数——它不是什么近似，就是六种情形如实平均的结果。

第二步：现在问 $n=10$。数不动了。

$10! = 3628800$ 种排列。你可以写程序穷举，可以手算，但课堂上不可能列一张三百六十万行的表。

更糟的是，穷举这条路对 $n$ 没有任何推广性——每换一个 $n$ 都得重数一遍。

到这里学生自己会问：有没有不数的方法？

第三步：把"总共几个人拿对"拆成 n 个小问题。

这是全篇的转折。引入一列小变量：

$$X_i = \begin{cases} 1 & \text{若第 } i \text{ 顶帽子恰好回到第 } i \text{ 人手中} \\ 0 & \text{否则} \end{cases}$$

那么总共拿对的人数，就是把这些小变量加起来：

$$F = X_1 + X_2 + \cdots + X_n.$$

第四步：单个来看，每个人拿对的概率是多少？

第 $i$ 顶帽子，在 $n$ 顶帽子的随机排列中，落在第 $i$ 个人手里——就是 $n$ 个位置里挑中那一个：

$$P(X_i = 1) = \frac{1}{n}, \qquad\text{所以}\qquad E(X_i) = \frac{1}{n}.$$

第五步：加起来。

$$E(F) = E(X_1) + E(X_2) + \cdots + E(X_n) = \underbrace{\frac1n + \frac1n + \cdots + \frac1n}_{n\text{ 个}} = n \cdot \frac{1}{n} = 1.$$

出来一个不依赖 $n$ 的数。 而且这一步的计算量跟 $n$ 完全无关——一百万人用五行字，三个人也用五行字。

为什么"越大越难"的直觉错了

算完了，但学生心里那个疙瘩还在：一百万顶帽子，怎么平均也是 1？

因为"越大越难"这句话只讲了对一半。

真相是这样的：当 $n$ 变大时，同时发生了两件事——

1. 每一顶帽子拿对的概率在变小，从 $1/3$ 掉到 $1/1000000$；
2. 参与这件事的帽子数在变多，从 3 顶涨到 1000000 顶。

一个变小，一个变大，正好抵消。

$$\underbrace{\frac{1}{n}}_{\text{单个机会变小}} \times \underbrace{n}_{\text{机会个数变多}} = 1$$

这就是为什么平均值像被钉死了一样。它不是巧合，是两个反向效应的精确平衡。

可以给学生一个感性的对照：$n=3$ 时，平均 1 顶拿对，而总共只有 3 顶——相当于三分之一的帽子有主。$n=1000000$ 时，平均还是 1 顶，但只相当于百万分之一的帽子有主。牌子（平均值）没变，但"大部分人都在换错帽子"这个事实，早就天差地别了。

原书那句斜体强调的话，才是本篇真正的伏笔

原书在结尾特别加了一句重话（本文前面英文原文里加粗的部分）：

it is not necessary that the summands be mutually independent （不要求各个被加项相互独立）

这句话在讲什么？它在说一件跟我们直觉相悖的事：期望可以随便相加，哪怕这些变量彼此纠缠。

而在我们这个例子里，这些 $X_i$ 确实彼此纠缠——而且纠缠得很明显：

第 1 顶帽子如果回到了第 1 人手里，那第 2 顶帽子回到第 2 人手里的机会就变了（剩下的 $n-1$ 个位置里挑一个）。$X_1$ 和 $X_2$ 显然不独立。

可 $E(F) = E(X_1) + \cdots + E(X_n)$ 照样成立。

为什么？因为期望的线性性质（$E(X+Y) = E(X) + E(Y)$）对任何两个随机变量都成立，独立不独立跟它毫无关系。独立是乘法公式的要求（$P(A \cap B) = P(A)P(B)$ 才需要），不是加法公式的要求。

这一条是高中课本几乎不提、但往后学统计学处处要用的工具。很多学生到了大学还以为"期望相加要求独立"，那个负担本来没必要背。

顺带留一个钩子：方差就没这么便宜了。$n\ge 2$ 时这个例子里 $\mathrm{Var}(F) = 1$，也是个不随 $n$ 变的常数——但证明它要用到错排公式，那是另一门课的事。

在课堂上怎么办

这个例子的课堂部分几乎不用备课，带一副扑克就能上。

用扑克牌的五张（A, 2, 3, 4, 5）当五顶帽子。让学生洗乱，然后翻开第一张——"是 A 吗？"第二张——"是 2 吗？"一路数下去，记下这一轮有几张"翻对"。

重复十来轮，把每一轮的翻对数写在黑板上。然后问："猜猜这十来轮的平均数是多少？"

会有学生说 2、说 3、说 0.5。等他们把累加一除，发现差不多是 1 的时候，这个数是他们自己洗出来的，不是你讲的。

接着把牌数加到十张再洗几轮，平均值还是 1。这时候再抛出前十张和一百万张的比较，学生就愿意听"为什么"了。

最后让他们算一个东西：n 张牌全洗错（错排）的概率。 从 $n=3$ 开始：$2/6 \approx 0.333$；$n=4$：$9/24 = 0.375$；$n=5$：$44/120 \approx 0.367$；$n=6$：$265/720 \approx 0.368$。

这四个数一路爬向 $1/e \approx 0.3679$。洗得再乱，也有大约 $36.8\%$ 的概率一张都对不上。 这个 $e$ 从一副洗乱的牌里冒出来，是这节课最好的收尾。

学生最容易栽在哪

课堂提问

1. $n$ 张牌洗乱，平均翻对 1 张。那把 $n$ 改成 2、改成 1000000，这个平均数会变吗？先说答案再解释。
2. 既然 $E(F)=1$，那 $P(\text{一顶都没拿对})$ 是多少？从 $n=3$ 开始算起，看看它往哪个数跑。提示：这个数跟 $e$ 有关。
3. 这道题里 $\mathrm{Var}(F)=1$ 也是个不随 $n$ 变的常数。可你刚刚看到 $n=1$ 时方差是 0、$n=2$ 时是 1。$n=1$ 是怎么回事？（提示：一副牌只有一张时，"洗乱"是什么意思？）