随机淘汰竞赛轮次预期值与Python模拟不符问题排查

问题描述 #

我要组织一场有2500万参与者的竞赛，规则是每轮随机淘汰剩余参与者中的若干人，目标是求剩余参与者≤5人时的预期轮次。
理论计算中，2500万除以2的22次方约等于5.96，是略大于5的最接近值，因此预期轮次为22轮。但用Python代码模拟后，结果分布集中在15-16轮，和理论值差距很大，怀疑代码有错误，求排查。

原模拟代码 #

import random

lst=list()
for j in range(1,10000):
    i=0
    X=25000000
    while X > 5:
        i = i+1
        elim=(random.randint(0,X))
        X = X - elim
    lst.append(i)
    
for i in range(1,33):
    print( i, "appears", lst.count(i), "times")

print("22 appears", lst.count(22)*100/len(lst), "% of the time")
print("15 appears", lst.count(15)*100/len(lst), "% of the time")

错误分析 #

• 核心逻辑偏差：原代码用random.randint(0,X)随机生成淘汰人数，这个范围包含了0（完全不淘汰）和X（直接淘汰所有剩余参与者）。这种淘汰模型和你理论计算时假设的「每轮参与者数量近似减半」完全不符——原模型中经常出现一轮淘汰大半甚至全部参与者的情况，自然会让轮次远低于理论值。
• 你的理论计算基于「每轮期望剩余人数为上一轮的1/2」，对应应该是每个参与者独立有50%概率被淘汰，而非随机选择0到X的淘汰数。

修正后的代码 #

如果要匹配你的理论假设，可修改淘汰逻辑为每轮每个参与者有50%概率留存，高效实现方式如下：

import random
from scipy.stats import binom

lst = []
for _ in range(10000):
    rounds = 0
    remaining = 25000000
    while remaining > 5:
        rounds += 1
        # 用二项分布直接生成剩余人数：n为当前人数，p为留存概率0.5
        remaining = binom.rvs(n=remaining, p=0.5)
    lst.append(rounds)

# 统计各轮次出现次数
for i in range(1, 33):
    print(f"{i} 出现 {lst.count(i)} 次")

print(f"22轮出现占比: {lst.count(22)*100/len(lst):.2f}%")
print(f"15轮出现占比: {lst.count(15)*100/len(lst):.2f}%")

如果不想依赖scipy，也可以用基础实现（注意：2500万次循环会较慢，建议减少模拟次数或用批量处理）：

import random

lst = []
for _ in range(1000):  # 减少模拟次数提升速度
    rounds = 0
    remaining = 25000000
    while remaining > 5:
        rounds += 1
        # 每轮每个参与者50%概率留存
        remaining = sum(1 for _ in range(remaining) if random.random() > 0.5)
    lst.append(rounds)

# 统计输出
for i in range(1, 33):
    print(f"{i} 出现 {lst.count(i)} 次")

print(f"22轮出现占比: {lst.count(22)*100/len(lst):.2f}%")
print(f"15轮出现占比: {lst.count(15)*100/len(lst):.2f}%")

补充说明 #

修正后的代码符合你理论计算的模型，模拟结果会集中在22轮左右，和预期一致。原代码的问题本质是淘汰规则和理论假设不匹配，导致模拟结果偏离。

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