100囚犯问题模拟：无偏随机排列生成的实现与偏误问询

你担心random.shuffle()会给100囚犯问题的模拟引入偏误，这个顾虑非常合理——官方文档里提到的点确实会影响排列的概率均匀性。下面我就详细拆解这个偏误的根源，再给你一个能严格保证「每种排列概率相等」的实现方案。

一、random.shuffle()的偏误到底来自哪里？ #

random.shuffle()本身基于的Fisher-Yates洗牌算法是无偏的，但问题出在它依赖的默认随机数生成器（Mersenne Twister，简称MT19937）：

• 确定性周期限制：MT19937是伪随机数生成器，它的输出完全由初始种子决定，并且会进入一个极大但有限的循环（周期约2^{19937）。虽然这个周期看起来大到离谱，但官方文档的提示点在于：当序列长度n足够大时，n!（排列总数）会逼近甚至超过PRNG的周期，导致大量排列永远无法被生成——比如旧版的小周期PRNG（如周期2}32），n=20时20!就已经远超这个数了。
• 精度损失问题：random.shuffle()默认用random()生成[0.0,1.0)的浮点数来计算随机索引，而双精度浮点数只有53位精度。当n超过2^53时，无法精确表示所有整数，会导致索引选择的不均匀，但n=100远小于这个阈值，所以这个问题对你的场景影响不大。

不过即使n=100时MT19937的周期足够覆盖所有排列，它的确定性本质还是会导致：只要种子固定，生成的排列序列就是固定的，无法做到真正的“所有排列等概率”——这对于需要严格随机性的模拟来说，还是个潜在问题。

二、满足严格等概率要求的抽屉初始化实现 #

要确保每种排列的概率完全相等，我们需要用密码学安全的随机数源（避免伪随机的确定性限制），并正确实现Fisher-Yates洗牌。Python的secrets模块提供了操作系统级别的真随机数，完美适配这个需求：

import secrets

def arrange_event(n_prisoners=100):
    if n_prisoners % 2 != 0 or n_prisoners <= 0:
        raise ValueError("Number of prisoners must be a positive and even number.")
    drawer = list(range(n_prisoners))
    # 手动实现Fisher-Yates洗牌，用安全随机数生成索引
    for i in range(n_prisoners - 1, 0, -1):
        # 生成0到i（包含）的均匀随机整数
        j = secrets.randbelow(i + 1)
        drawer[i], drawer[j] = drawer[j], drawer[i]
    return drawer

为什么这个实现能保证等概率？ #

1. Fisher-Yates的数学无偏性：这个算法每一步都从剩余未洗牌的元素中随机选一个交换到当前位置，数学上可以严格证明，它能生成所有n!种排列，且每种排列出现的概率都是1/n!。
2. 真随机数的均匀性：secrets.randbelow()调用的是操作系统提供的真随机数源（比如Linux的/dev/urandom、Windows的CryptGenRandom），熵来自硬件噪声等真实随机事件，不存在伪随机数的周期和确定性问题，能真正均匀地生成随机索引。

三、补充：关于random.shuffle()的实际使用场景 #

如果你的模拟只是做一般性的演示，不需要严格的学术级随机性，random.shuffle()在n=100的场景下其实已经足够好用——MT19937的周期极大，生成的排列分布非常均匀，偏误小到可以忽略不计。但如果你的实验需要绝对严格的随机性验证，那上面基于secrets的实现就是更可靠的选择。

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