Table of Contents
题目
一百万枚磁性的"Susans"（苏珊·B·安东尼一美元硬币）按如下方式抛入两个罐子：两个罐子各以一枚硬币开始，剩下的 \(999{,}998\) 枚硬币一枚一枚地被抛入空中。如果第一个罐子中有 \(x\) 枚硬币、第二个罐子中有 \(y\) 枚硬币，磁性吸引会使下一枚硬币以概率 \(\frac{x}{x+y}\) 落入第一个罐子，以概率 \(\frac{y}{x+y}\) 落入第二个罐子。
你愿意预先付出多少钱，来换取最终硬币数较少的那个罐子里的全部硬币？
分析
关键洞察：这是一个波利亚罐子（Pólya's urn）问题，而波利亚罐子有一个著名的性质：最终罐子1中的硬币数在所有可能取值上均匀分布。抓住这一点，剩下的就只是算术。
一、均匀分布
设最终硬币总数为 \(N=1{,}000{,}000\)，记 \(X\) 为过程结束后罐子1中的硬币数。硬币只会被加入罐子、从不减少，而且两个罐子都从一枚硬币开始：罐子1始终至少保留自己那枚初始硬币，所以 \(X\ge1\)；罐子2也要始终保留它的那枚初始硬币，所以 \(X\le N-1\)。因此 \(X\) 只可能取 \(1,2,\ldots,N-1\) 这些值。
先看小情形找规律。从 \((1,1)\) 出发：
- 抛完第 \(1\) 枚硬币后：罐子1有 \(1\) 枚或 \(2\) 枚，概率各为 \(\frac{1}{2}\)；
- 抛完第 \(2\) 枚硬币后：罐子1有 \(1,2,3\) 枚，概率各为 \(\frac{1}{3}\)；
- 抛完第 \(3\) 枚硬币后：罐子1有 \(1,2,3,4\) 枚，概率各为 \(\frac{1}{4}\)。
规律是：总共 \(t\) 枚硬币时，罐子1的硬币数在 \(\{1,2,\ldots,t-1\}\) 上均匀分布。用归纳法证明。
设总共 \(t\) 枚硬币时罐子1有 \(j\) 枚的概率为 \(\frac{1}{t-1}\)。抛入下一枚硬币后共 \(t+1\) 枚，罐子1变为 \(k\) 枚有两条路径：要么原来有 \(k-1\) 枚且新硬币落入罐子1（概率 \(\frac{k-1}{t}\)），要么原来有 \(k\) 枚且新硬币落入罐子2（概率 \(\frac{t-k}{t}\)）。因此
\[ \Pr(X_{t+1}=k)=\frac{1}{t-1}\cdot\frac{k-1}{t}+\frac{1}{t-1}\cdot\frac{t-k}{t} =\frac{1}{t-1}\cdot\frac{t-1}{t}=\frac{1}{t}.\]
于是罐子1的每个取值 \(k=1,\ldots,t\) 概率都为 \(\frac{1}{t}\)，即在 \(\{1,\ldots,t\}\) 上均匀，归纳完成。最终 \(t=N\) 时得到
\[ \Pr(X=k)=\frac{1}{N-1},\qquad k=1,2,\ldots,N-1.\]
（不用归纳也能看出这一点：任意一条“新硬币各归哪罐”的完整历史，其概率的分子乘积只由两个罐子的最终硬币数决定，而分母乘积对相同长度的所有历史完全一样，逐项求和后每种最终分配的概率都相等。）
二、计算“较少的罐子”的期望
较少罐子中的硬币数是 \(\min(X,\,N-X)\)。\(N=1{,}000{,}000\) 为偶数，记 \(m=N/2=500{,}000\)。对每个 \(v=1,\ldots,m-1\)，等式 \(\min(X,N-X)=v\) 恰好对应 \(X=v\) 或 \(X=N-v\) 两种取值；而 \(\min(X,N-X)=m\) 只在 \(X=m\) 时出现，对应一种取值。由于 \(X\) 在 \(\{1,\ldots,N-1\}\) 上均匀，每种取值概率都是 \(\frac{1}{N-1}\)，所以
\[ \mathbb{E}\,[\min(X,\,N-X)] =\frac{2(1+2+\cdots+(m-1))+m}{N-1} =\frac{(m-1)m+m}{N-1} =\frac{m^{2}}{N-1} =\frac{N^{2}}{4(N-1)}.\]
代入 \(N=1{,}000{,}000\)：
\[ \mathbb{E}=\frac{1{,}000{,}000^{2}}{4\times 999{,}999} =250{,}000+\frac{250{,}000}{999{,}999} \approx 250{,}000.25.\]
三、答案
最公平的预先定价就是它的期望值：约 \(250{,}000.25\) 美元，即略多于四分之一百万美元。精确值是
\[ 250{,}000+\frac{250{,}000}{999{,}999}\approx 250{,}000.25\ \text{美元}.\]
（不少地方把这个问题的答案写成“四分之一百万美元”即恰好 \(250{,}000\) 美元：那相当于把分布近似看成在 \(\{1,2,\ldots,N\}\) 上均匀，得到 \(\frac{N}{4}\)。与本题的精确值只差约 \(0.25\) 美元——一枚初始硬币引起的 \(O(1)\) 修正，在 \(N=1{,}000{,}000\) 的规模下无足轻重。）