时间戳

首页 > 解决方案 > 生日悖论，错误输出约 1

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

问题描述

我对 python 比较陌生，想通过解决生日问题来测试自己。我不想用数学方法计算它，而是想模拟它，看看我是否能得到正确的答案。所以我将列表 sieve[] 中的所有布尔值分配为 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")

标签： python

解决方案

您的代码中没有错误。当您真正感兴趣的（以及生日悖论告诉您的内容）是分布的中位数时，您正在计算返回值样本的平均值。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

请注意，这里有一个（微小的）运气：返回值分布的中位数是（至少根据维基百科的定义），但是一个不寻常的样本有可能具有不同的中位数，纯粹是通过随机性。在这种特殊情况下，这种机会完全可以忽略不计。正如user2357112在评论中指出的那样，在为期 2 天的示例中，情况有点混乱，其中和（包括）之间的任何实数都是有效的分布中位数，我们可以合理地预期样本中位数是或。howManyPeople232.03.023

除了抽样，我们还可以直接计算每个输出的概率howManyPeople：对于任何正整数k，输出严格大于k的概率与第一个人有不同生日的概率相同k，这是给定的（在 Python语法）factorial(365)/factorial(k)/365**k，我们可以用它来计算单个输出的概率。在这里，我使用由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

推荐阅读