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