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

我是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")

最佳答案

您的代码没有错误。当您真正感兴趣的(以及生日悖论告诉您的)是分布的中位数时，您正在计算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(至少根据Wikipedia的定义)，但是有可能一个不寻常的样本可能纯粹通过随机性而具有不同的中位数。在这种特殊情况下，这种机会是完全可以忽略的。就像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

关于python - 生日悖论，错误输出约1，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52226850/