n个水平相同的人参加大逃杀游戏,最后赢家所消灭玩家数的期望值是多少?

记X为每局最后胜利者在本局游戏中所击杀的玩家数,求X的期望。

在以上条件下X的期望可求吗?如果不可求,那么至少要补充什么条件?

在X期望可求的条件下,“玩家水平相同”的严格定义是什么呢?

我的回答

如果只建个相对简单的模型还是可以分析的(至于真实情况分析起来可能要麻烦不少,比如说你杀了别人舔包增强你的装备补给会提升胜率,但是和别人交火中受伤之类的又会降低胜率,如果要建立合理的模型恐怕是比较复杂的了)。

$k$ 个玩家水平相同,到游戏结束只剩 $1$ 人,那么中间过程有 $k-1$ 步,每一步都是从剩下的所有人中随机选择两人,让第一个人消灭掉第二个人即可。

现在来考虑期望问题,我们用符号 $E_k$ 表示只有 $k$ 个玩家时最后赢家消灭玩家数的期望,不难得到如下递推式:

\[E_{k}=\frac{1}{k-1} \cdot (E_{k-1}+1)+\frac{k-2}{k-1} \cdot E_{k-1}\]

这个递推式可以这样理解:当有 $k$ 个玩家时,我们从最后赢家的角度考虑,在接下来的一步中首先要选出一个被害者,只能在其余的 $k-1$ 个人中挑一个,接着才是挑选杀人者,赢家被挑中的机会是 $1/(k-1)$,就有了上述公式。将公式整理一下得到:

\[E_{k}=\frac{1}{k-1} + E_{k-1}\]

结合边界条件不难求得:

\[E_{n} = \sum_{i=1}^{n-1}{\frac{1}{i}}\]

最后跑了个模拟和理论的对比图做了下验证:

# -*- coding:utf-8 -*-
from random import randrange
import matplotlib.pyplot as plt

def simulate(n):
    y, count = 0, 500
    for _ in range(count):
        player = [0] * n
        for m in range(n, 1, -1):
            killer = randrange(0,     m)
            victim = randrange(0, m - 1)
            if victim >= killer:
                victim = victim + 1
            player[killer] += 1
            del player[victim]
        y += player[0] / count
    return y

def harmonic(n):
    y = 0
    for i in range(1, n):
        y = y + 1 / i
    return y

if __name__ == '__main__':
    x = range(1, 100)
    y_s = list(map(simulate, x))
    y_h = list(map(harmonic, x))
    plt.scatter(x, y_s, label='simulate', c='r')
    plt.plot(x, y_h, label='harmonic', c='g')
    plt.xlabel('player number')
    plt.ylabel('winner kills')
    plt.title("PUBG")
    plt.legend()
    plt.show()