含n个玩家的博弈问题（二）：i≤j时的获胜概率问询

嘿，我来帮你拆解这个玩家对战的概率问题，先把规则理清楚，再讲讲怎么求解核心的概率问题：

场景规则梳理 #

• 有n名玩家，编号从1到n；
• 任意两名玩家i和j对战时，i获胜的概率是 i/(i+j)，没有平局；
• 对战流程是随机轮次挑战：
  1. 先随机抽两名不同的玩家i₁和i₂对战，决出胜者；
  2. 接着随机抽一名没参战过的玩家i₃，让上一轮的胜者和i₃对战；
  3. 重复这个过程直到所有玩家都参与过，一共会打n-1场比赛；
• 已知条件：i ≤ j。

核心问题：求指定玩家最终获胜的概率 #

这是这个场景下最常问的问题，我们可以通过数学归纳法或者利用概率的对称性来推导：

小例子验证 #

先从n=2的简单情况看：

• 玩家1和2对战，1获胜的概率是 1/(1+2)=1/3，2获胜的概率是 2/(1+2)=2/3，符合直观。

对于n=3的情况，枚举所有6种可能的出场排列（因为每次随机抽取等价于所有玩家的出场顺序是随机排列），计算后可以得到：

• 玩家1最终获胜的概率是 1/10
• 玩家2最终获胜的概率是 23/60
• 玩家3最终获胜的概率是 31/60
  （三者相加等于1，符合概率的基本性质）

通项公式推导 #

通过归纳法可以证明，玩家k最终获胜的概率可以表示为：
$$
P(k) = \sum_{m=k}^n (-1)^{m-k} \binom{m-1}{k-1} \frac{1}{m+1}
$$
或者换一种更简洁的形式，用调和数表示（调和数$H_n = 1 + 1/2 + 1/3 + ... + 1/n$）：
$$
P(k) = \frac{1}{k} \sum_{i=1}^k \frac{(-1)^{i-1}}{i} \binom{k}{i} H_{n+i}
$$
如果只是需要近似或者理解核心逻辑，也可以通过递归的方式计算：比如玩家k要最终获胜，需要在他出场后击败所有后续挑战的玩家，同时前面对战产生的最终胜者能被他击败——不过递归的计算量会随着n增大而快速增加。

其他衍生问题 #

除了最终获胜概率，还可以求解比如：

• 某两名玩家在对战中相遇的概率；
• 第m场对战由哪两名玩家参与的概率；
  这些问题都可以通过排列组合结合概率的乘法法则来推导。

内容的提问来源于stack exchange，提问作者user207096