Featured image of post 100名囚犯问题：为什么顺着号码找能把0.0000000000000000000000000000008%的生还率提升到31.18%？
数学

100名囚犯问题：为什么顺着号码找能把0.0000000000000000000000000000008%的生还率提升到31.18%？

从彼得·布罗·米尔特森（2003）提出的100名囚犯问题出发，严密解析置换群的不相交轮换分解、长度为ℓ>50长轮换的计数定理 1/ℓ、调和数推导出的 1 - ln 2 ≈ 31.18% 奇迹生还率，以及零通信下的风险耦合机制。

引言：概率论中最反直觉的奇迹

2003年，丹麦计算机科学家彼得·布罗·米尔特森（Peter Bro Miltersen）提出了一个轰动数学界的智力谜题——100名囚犯问题（100 Prisoners Problem）：

  • 监狱里有编号为 $1$ 到 $100$ 的 $100$ 名死刑犯。典狱长在一个密室里放了 $100$ 个抽屉（箱子），箱子外侧贴着 $1$ 到 $100$ 的编号；箱子内部随机放入了写有 $1$ 到 $100$ 号码的纸条（每个箱子一张，构成 $1$ 到 $100$ 的随机排列）。
  • 规则：每名囚犯依次独自进入密室，最多可以打开 $50$ 个箱子寻找写有自己编号的纸条。离开时必须将所有箱子恢复原状，且一旦游戏开始，囚犯之间绝对禁止任何形式的信息传递或暗示（但在游戏开始前可以共同商定策略）。
  • 生死判定：只有当 全部 $100$ 名囚犯都找到自己的号码 时，所有人才能被无罪释放；哪怕只有 $1$ 人失败，全体 $100$ 人立即处决。

如果每名囚犯都各自随机打开 $50$ 个箱子（独立随机策略），单人成功率为 $50/100 = 1/2$。由于各人成败相互独立，全体生还的概率是令人绝望的：

$$\mathbb{P}(\text{全体生还})_{\text{独立}} = \left(\frac{1}{2}\right)^{100} = \frac{1}{1,\!267,\!650,\!600,\!228,\!229,\!401,\!496,\!703,\!205,\!376} \approx 7.89 \times 10^{-31}$$

然而，米尔特森的同事斯文·斯카이姆（Sven Skyum）发现了一个极为简单的指针追踪策略（Pointer-Following Strategy），在不传递任何1比特信息的前提下，将全体生还率一举提升到了 $31.18\%$（超过三分之一）！

第一章：指针追踪策略与置换群的轮换分解

斯文·斯카이姆提出的策略只有三步（设囚犯自己的编号为 $k \in \{1, \dots, 100\}$）：

  1. 第1步：进入密室后，首先打开外侧标有自己编号的 第 $k$ 号箱子。
  2. 第2步：若箱内纸条号码 $x_1 = k$，则成功；若 $x_1 \neq k$，下一步就去打开 第 $x_1$ 号箱子。
  3. 第3步：读取新箱子里的号码 $x_2$，再去打开第 $x_2$ 号箱子……以此类推，沿着链条 $k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots$ 追踪，直到找到号码 $k$ 或用完 $50$ 次机会。
  flowchart TD
    Start["囚犯 k 进入密室 (最多 50 次机会)"]
    Step1["第 1 步: 打开第 k 号箱子，读取纸条号码 x = σ(k)"]
    Check{"纸条号码 x == k ?"}
    Win["成功找到自己的号码 k !"]
    Limit{"已开箱次数 < 50 ?"}
    Next["下一步: 将指针更新为第 x 号箱子并打开 (x ← σ(x))"]
    Lose["超过 50 次仍未回到 k: 任务失败 (全体处决)"]
    Start --> Step1 --> Check
    Check -- "是" --> Win
    Check -- "否" --> Limit
    Limit -- "是" --> Next --> Check
    Limit -- "否 (所在轮换长度 ℓ > 50)" --> Lose

为什么这个动作能创造奇迹？在代数学中，箱子编号与内部纸条的对应关系是 $2n = 100$ 元对称群 $S_{2n}$ 中的一个双射置换 $\sigma$。由群论基本定理，任意有限置换 $\sigma \in S_{2n}$ 都可以唯一地分解为若干个不相交轮换（Disjoint Cycles）的乘积：

$$\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100$$

因为 $\sigma$ 是双射，从箱子 $k$ 出发沿着指针追踪，绝不会陷入旁支死胡同，而必定沿着包含 $k$ 的唯一闭合轮换绕行一周，最终必然回到起点箱子 $k$（因为指向箱子 $k$ 的那张写有号码 $k$ 的纸条正是轮换中 $k$ 的前驱 $\sigma^{-1}(k)$）！因此：

  • 囚犯 $k$ 能否在 $50$ 步内找到号码 $k$，等价于包含 $k$ 的那个轮换的长度 $\ell$ 是否满足 $\ell \le 50$。
  • 全体 $100$ 名囚犯全部生还，当且仅当置换 $\sigma \in S_{100}$ 的轮换分解中没有任何一个轮换的长度超过 $50$（即最大轮换长度 $L_{\max}(\sigma) \le 50$）！

第二章：长轮换计数定理与调和数 $1 - \ln 2$ 的严密推导

设总人数为 $2n$（此处 $2n = 100, n = 50$）。如果一个置换 $\sigma \in S_{2n}$ 含有长度严格大于 $n$ 的长轮换（$\ell \in \{n+1, \dots, 2n\}$），由于两个长度都大于 $n$ 的不相交轮换之和至少为 $(n+1)+(n+1) = 2n+2 > 2n$，在同一个置换中，长度 $\ell > n$ 的长轮换最多只能存在唯一一个！

这意味着事件 $E_\ell := \{\text{置换 }\sigma\text{ 含有长度为 }\ell\text{ 的轮换}\}$ 对 $\ell = n+1, n+2, \dots, 2n$ 是两两互斥（Mutually Exclusive）的！我们来精确计算满足 $E_\ell$ 的置换个数：

  1. 从 $2n$ 个元素中选出构成该长轮换的 $\ell$ 个元素，共有 $\binom{2n}{\ell}$ 种选法；
  2. 将这 $\ell$ 个元素排成一个单一的闭合圆周轮换，共有 $(\ell - 1)!$ 种排法（圆排列）；
  3. 剩下的 $2n - \ell$ 个元素可以任意排列，共有 $(2n - \ell)!$ 种排法。

将三者相乘，阶乘发生惊人的约分：

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

除以总排列数 $|S_{2n}| = (2n)!$，得到含有长度为 $\ell > n$ 的轮换的精确概率仅为 $\mathbb{P}(E_\ell) = \frac{1}{\ell}$！利用互斥事件的可加性与调和数（Harmonic Number） $H_N = \sum_{k=1}^N \frac{1}{k}$，全体生还概率为：

$$\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30.685\%}$$

对 $2n = 100, n = 50$，精确生还率为 $P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx 1 - 0.688172 = \mathbf{31.1828\%}$！

第三章：为什么没有传递信息却能逆天改命？——风险的完美耦合

为什么单人成功率明明始终是 $50\%$（成功人数的数学期望在两种策略下完全相同：$\mathbb{E}[\sum I_k] = 100 \times 0.5 = 50$），全体生还率却暴涨了 $3.95 \times 10^{29}$ 倍？

  flowchart TD
    Pool["总失败风险池固定: 期望失败人数 E[失败] = 50 人"]
    Indep["独立随机策略: 100 人成败相互独立 (风险分散在几乎所有平行宇宙)"]
    Cycle["指针追踪策略: 100 人命运绑定于同一个置换 σ 的轮换结构 (风险极端耦合)"]
    ResI["99.99999999999999999999999999992% 的宇宙至少死 1 人 → 全体生还率 ≈ 7.89×10⁻³¹"]
    ResC["68.82% 的宇宙(含 ℓ>50 长轮换)多人团灭；31.18% 的宇宙(全短轮换) 100 人全员生还!"]
    Pool --> Indep --> ResI
    Pool --> Cycle --> ResC
比较维度① 独立随机策略② 指针追踪（轮换）策略
单人成功概率 $\mathbb{P}(A_k)$$50.00\%$$50.00\%$（完全不变）
期望成功人数 $\mathbb{E}[X]$$50$ 人$50$ 人（完全不变）
囚犯间相关性零相关（相互独立）通过共享环境 $\sigma$ 的轮换结构强正相关
$100$ 人全体生还率$(1/2)^{100} \approx 7.89 \times 10^{-31}$$1 - (H_{100} - H_{50}) \approx 31.18\%$
$n \to \infty$ 渐近下界$0$（指数级归零）$1 - \ln 2 \approx 30.685\%$（恒定正常数）
  1. 概率论中的耦合（Coupling）与团灭换生机：在规则“哪怕1人失败即全员处决”下，失败1人和失败51人的惩罚完全相同。独立策略把失败风险均匀撒在所有样本路径上，导致几乎每条路径都有约50人失败；而指针追踪策略将所有人的命运耦合（Coupled）在同一个置换 $\sigma$ 的拓扑结构上——把所有的失败高度浓缩进那 $68.82\%$ 含有 $\ell > 50$ 长轮换的排列里（一旦失败至少51人一起失败），从而把整整 $31.18\%$ 的样本空间彻底清空为“零失败净土”！
  2. 如果典狱长恶意排布纸条怎么办？ 如果典狱长故意把纸条排成一个长度为 $100$ 的大轮换，生还率将降为 $0$。但囚犯们只需在进场前秘密商定一个随机的重命名双射 $\tau \in S_{100}$，将箱子 $x$ 视为 $\tau(x)$，則新置换 $\tau \sigma \tau^{-1}$ 的轮换结构被完全随机化，无论典狱长如何做手脚，生还率依然严格保持 $31.18\%$！
comments powered by Disqus