生日问题的算法

这个例子演示了一个解决广义生日问题的算法的实现和应用--确定一个群体中匹配一定数量的人的生日的概率超过给定的人的最小数量。

导言

什么是"生日挑战"？

"生日问题"是概率论中的一个经典问题，其表述如下：一个群体中至少有两个人拥有相同生日的概率是多少？

通常，该任务是针对对此概率超过50％的最小数量感兴趣的人群进行研究的。然而，它可以扩展：您可以搜索，例如，最小数量的人匹配的生日三，四等。

原始问题在密码学和随机性测试中有重要的应用，在那里它被用来评估碰撞的可能性。

主要部分

用于计算一组的概率的函数 groupsize 一个人至少 sharers 一个人有相同的生日。使用重复次数的蒙特卡洛方法。 nrep.

function equalbirthdays(sharers::Int, groupsize::Int; nrep::Int = 10000)
    eq = 0 # 找到所需匹配的情况下的计数器。
    for _ in 1:nrep
        # 为组中的所有人生成随机生日
        group = rand(1:365, groupsize)
        # 将数组转换为集合以删除重复
        grset = Set(group)
        # 条件：必须有足够的重复
        # 至少这个人的"共享者"的生日是一样的
        if groupsize - length(grset) ≥ sharers - 1 &&
            any(count(x -> x == d, group) ≥ sharers for d in grset)
            eq += 1
        end
    end
    return eq / nrep # 返回成功率
end

equalbirthdays

我们从一组2人开始，假设最小尺寸

gsizes = [2]

# 对于每个数量的人谁必须有相同的生日
for sh in (2, 3, 4, 5)
    local gsize = gsizes[end] # 初始近似
    local freq # 用于存储事件频率的变量

    # 第一阶段：粗略搜索（快速评估的迭代次数较少）
    while equalbirthdays(sh, gsize; nrep = 100) < 0.5
        gsize += 1
    end

    # 第二阶段：在小范围内进行更精确的搜索
    for gsize in trunc(Int, gsize - (gsize - gsizes[end]) / 4):(gsize + 999)
        if equalbirthdays(sh, gsize; nrep = 250) > 0.5
            break
        end
    end

    # 第三阶段：高精度精确计数
    for gsize in (gsize - 1):(gsize + 999)
        freq = equalbirthdays(sh, gsize; nrep = 50000)
        if freq > 0.5
            break
        end
    end

    # 保存找到的人数
    push!(gsizes, gsize)

    # 结果的输出
    @printf("%s组中的%i有一个共同的生日，概率为%5.3f\n", sh, gsize, freq)
end

2 людей в группе из 22 имеют общий день рождения с вероятностью 0.511
3 людей в группе из 86 имеют общий день рождения с вероятностью 0.501
4 людей в группе из 181 имеют общий день рождения с вероятностью 0.504
5 людей в группе из 305 имеют общий день рождения с вероятностью 0.502

结论

我们已经考虑了解决广义生日问题的算法的实现：计算具有给定概率（在这种情况下，超过50％）匹配生日所需的最小数量。 k 人类。

该算法使用蒙特卡洛方法进行统计概率估计，这使得它适用于复杂或分析上难以计算公式的情况。

这种方法不仅在概率论中有用，而且在评估巧合或碰撞可能性很重要的其他领域也有用（例如，在散列中）。

该示例是使用[Rosetta代码]的材料开发的（https://rosettacode.org/wiki/Birthday_problem ）