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()