进化论问题
进化论问题
\(n\) 个人玩一个团建游戏，游戏开始时，所有玩家等级均为 \(0\)，每个玩家的最高等级为 \(m\)，最低等级为 \(0\)，且 \(n \geq m\)。每回合依次进行如下步骤：
- 将所有玩家根据其等级分为 \(m + 1\) 个集合 \(S_0, \dots, S_m\)。
- 对每个集合 \(S_j\)，若 \(j \neq m\)，其中所有玩家随机两两进行剪刀石头布，胜利者等级 +1，失败者等级 -1，平局无变化。如果某集合人数为奇数，则随机有一人轮空。
当无法再进行剪刀石头布对局时，游戏结束。
- 对某个玩家，求其最终能够升到最高等级的概率。
- 求直到游戏结束，共进行的剪刀石头布对局次数的数学期望。
- 若 \(n \gg m\)，某个玩家能升到最高等级，求其到达最高等级所经历的剪刀石头布对局次数的数学期望。
解答
定义势函数
\[ F=\sum_{\text{玩家 }i}f(X_i), \qquad f(j)=\frac{j(j+1)}2, \]
其中 \(X_i\) 是玩家 \(i\) 当前的等级。
设每次剪刀石头布中，胜、负、平三种结果的概率均为 \(1/3\)，不同对局相互独立。
把一次非平局对局称为一次“有效对局”。
1
忽略平局，因为平局不改变任何状态。一次出现胜负的对局，可以看作一次“操作”：
- 在等级 \(0\)：两人变成等级 \(0,1\) 各一人；
- 在等级 \(1\le j<m\)：两人变成等级 \(j-1,j+1\) 各一人。
这是路径 \(0,1,\ldots,m\) 上的稳定化过程，其中等级 \(m\) 是吸收点。从 \(n\) 个人全部位于等级 \(0\) 出发，不断对人数至少为 \(2\) 的非最高等级进行上述操作，最终稳定状态唯一，为
\[ |S_j|=1\quad(0\le j<m),\qquad |S_m|=n-m. \]
简要证明如下。
对每名玩家赋予势能 \(f(j)\)。一次出现胜负的操作总使总势能增加 \(1\)：
- 当 \(j=0\) 时，
\[ f(1)+f(0)-2f(0)=1; \]
- 当 \(1\le j<m\) 时，
\[ f(j+1)+f(j-1)-2f(j)=1. \]
总势能不超过 \(nf(m)\)，所以出现胜负的操作不可能无限进行。
另一方面，不同等级上的操作彼此交换，即先在哪个等级操作不影响稳定化结果；如果两个等级同时可以操作，先操作其中任一个都不会使另一个变得不可操作。因此由交换性和终止性，稳定状态唯一。对人数 \(n\) 作归纳即可得到稳定形状：
\[ (1,1,\ldots,1,n-m). \]
也可以将其理解为：每加入一名等级 \(0\) 的玩家并重新稳定化，若尚未铺满 \(0,\ldots,m-1\)，稳定阶梯向右延长一级；若已经铺满，则新增的一人最终进入等级 \(m\)。所以终局为
\[ {|S_0|=\cdots=|S_{m-1}|=1,\qquad |S_m|=n-m.} \]
每次对局成为有效对局的概率为 \(2/3\)，所以只要某等级仍有至少两人，就几乎必然最终会出现有效对局。因此上述结论以概率 \(1\) 成立。所有玩家在游戏开始时完全对称，而最终恰有 \(n-m\) 人到达等级 \(m\)。因此对任意指定玩家 \(A\)，有
\[ {P(A\text{ 最终到达最高等级})=\frac{n-m}{n}.} \]
2
对 \(1\leq j<m\)，
\[ f(j-1)+f(j+1)-2f(j)=1. \]
而在等级 \(0\)，
\[ f(0)+f(1)-2f(0)=1. \]
所以每发生一次有效对局，\(F\) 恰好增加 \(1\)。平局不改变 \(F\)。
开始时 \(F=0\)。游戏结束时，
\[ F_{\rm end} = \sum_{j=0}^{m-1}\frac{j(j+1)}2 +(n-m)\frac{m(m+1)}2. \]
利用 \(\sum_{j=0}^{m-1}j(j+1)=\frac{m(m-1)(m+1)}3\) 得到
\[ F_{\rm end} = \frac{m(m+1)(3n-2m-1)}6. \]
因此有效对局总数不是随机量，而恒为 \(\frac{m(m+1)(3n-2m-1)}6\)。每场普通对局成为有效对局的概率为 \(2/3\)，所以产生一次有效对局所需普通对局次数的期望为 \(3/2\)。于是总对局次数 \(T\) 满足 \(E[T]=\frac32 F_{\rm end}\)。故
\[ { E[T] = \frac{m(m+1)(3n-2m-1)}4 }. \]
3
因为 \(P(\text{该玩家最终成功})=1-\frac mn\)，当 \(n\gg m\) 时，该概率接近 \(1\)。在到达等级 \(m\) 之前，该玩家的等级近似为一个在 \(0\) 处反射、在 \(m\) 处吸收的惰性对称随机游走：
- 在 \(1\leq j<m\)，\(j\to j+1,\ j,\ j-1\) 的概率各为 \(1/3\)；
- 在 \(j=0\)：\(0\to 1\) 的概率为 \(1/3\)，停留在 \(0\) 的概率为 \(2/3\)。
设从等级 \(j\) 到达 \(m\) 还需要的个人对局次数期望为 \(H_j\)。则 \(H_m=0\) 且
\[ H_0=1+\frac23H_0+\frac13H_1, \]
以及对 \(1\leq j<m\)，
\[ H_j = 1+\frac13H_{j-1}+\frac13H_j+\frac13H_{j+1}. \]
解上述方程组得所求数学期望
\[ H_0 = \frac{3m(m+1)}2. \]
作为核对，所有玩家平均参与的对局次数恰为
\[ \frac{2E[T]}n = \frac{m(m+1)(3n-2m-1)}{2n} \longrightarrow \frac{3m(m+1)}2 \qquad(n/m\to\infty), \]
与上述结果一致。