python - 生日悖论，输出错误约 1

Question

我是 python 的新手，想通过解决生日问题来测试自己。我不想用数学方法计算它，而是想模拟它，看看我是否能得到正确的答案。所以我将列表 sieve[] 中的所有 bool 值都分配为 False，然后随机选择一个从 0 到 364 的值并将其更改为 True，如果它已经是 True，那么它输出它必须迭代多少次作为答案。

出于某种原因，每次运行代码时，我都会得到一个介于 24.5 和 24.8 之间的值

50% 的预期结果是 23 人，那么为什么我的结果比应有的高 6%？我的代码有错误吗？

import random

def howManyPeople():
    sieve = [False] * 365
    count = 1
    while True:
        newBirthday = random.randint(0,364)
        if sieve[newBirthday]:
            return count
        else:
            sieve[newBirthday] = True
            count += 1

def multipleRun():
    global timesToRun
    results = []
    for i in range(timesToRun):
        results.append(howManyPeople())
    finalResultAverage = sum(results)
    return (finalResultAverage / timesToRun)

timesToRun = int(input("How many times would you like to run this code?"))

print("Average of all solutions = " + str(multipleRun()) + " people")

Answer 1

您的代码没有错误。您正在计算 howManyPeople 样本的均值返回值，当您真正感兴趣的(以及生日悖论告诉您的内容)是分布的中位数时。

也就是说，您有一个随机过程，在这个过程中，您逐渐将人添加到一个集合中，然后在第一个生日碰撞时报告该集合中的总人数。生日悖论意味着至少有 50% 的时间，你的集合将有 23 人或更少的人。这与说集合中的预期人数为 23.0 或更少不是一回事。

这是我从您的 howManyPeople 的一百万个样本中看到的结果功能。

In [4]: sample = [howManyPeople() for _ in range(1000000)]

In [5]: import numpy as np

In [6]: np.median(sample)
Out[6]: 23.0

In [7]: np.mean(sample)
Out[7]: 24.617082

In [8]: np.mean([x <= 23 for x in sample])
Out[8]: 0.506978

请注意，这里有(微小的)运气因素:howManyPeople 的分布的中位数。返回值为 23 (至少根据维基百科的定义)，但不寻常的样本有可能具有不同的中位数，这完全是随机的。在这种特殊情况下，这种机会完全可以忽略不计。而作为 user2357112在评论中指出，在为期 2 天的年份示例中，情况有点困惑，其中 2.0 之间的任何实数和 3.0 (包括) 是一个有效的分布中位数，我们可以合理地期望样本中位数是 2或 3 .

除了抽样，我们还可以计算 howManyPeople 的每个输出的概率直接:对于任何正整数 k , 输出严格大于 k 的概率与第一个k的概率相同人们有不同的生日，由 factorial(365)/factorial(k)/365**k 给出(在 Python 语法中) ，我们可以用它来计算单个输出的概率。我在这里使用名称 X对于 howManyPeople 表示的随机变量.一些低效的代码:

from math import factorial

def prob_X_greater_than(k):
    """Probability that the output of howManyPeople is > k."""
    if k <= 0:
        return 1.0
    elif k > 365:
        return 0.0
    else:
        return factorial(365) / factorial(365 - k) / 365**k

def prob_X_equals(k):
    """Probability that the output of howManyPeople is == k."""
    return prob_x_greater_than(k-1) - prob_x_greater_than(k)

有了这个，我们可以得到准确的(嗯，好吧，准确到数字错误)均值并验证它与我们从样本中得到的大致匹配:

In [18]: sum(k*prob_x_equals(k) for k in range(1, 366))
Out[18]: 24.616585894598863

这种情况下的生日悖论应该告诉我们 k <= 23 的概率之和大于 0.5 :

In [19]: sum(prob_x_equals(k) for k in range(1, 24))
Out[19]: 0.5072972343239854