经典生日问题为什么不够用
经典生日问题假设每个生日出现的概率相同,并询问一个群体中任意两人同一天生日的概率。这个假设很方便,但往往不现实。当生日并非等概率时——比如某些日期更常见——匹配的概率可能升高也可能降低,取决于你关注的是哪些配对[3]。因此,推广解法必须同时说明生日的分布以及哪些匹配才算数。
另一种常见变体问的是两个群体之间而非一个群体内部的匹配。例如,如果你有两个人数不同的班级,第一个班级中至少有一名学生与第二个班级中至少有一名学生同一天生日的概率是多少?这有时被称为双型生日问题,它有自己的推广解法[5]。
生日不均匀,或只有特定配对才重要时
有一类工作直接处理非均匀的生日分布。研究者借助图论方法——具体来说是与色多项式相关的界——展示了当生日并非等概率、且你关心的是特定配对而非任意配对时,如何计算匹配概率[3]。关键直觉是:不均匀性可能提高也可能降低整体匹配概率,取决于常见的生日是否恰好落在你关注的配对上。
这对真实数据很重要。例如,如果你在检查两个数据集是否包含相同的个体,“生日”可能是若干变量的组合,而这些组合很少是均匀的。推广的碰撞模型可以告诉你,观测到的匹配数量何时高于随机预期——这正是经典生日问题以最简单形式回答的那类问题[1]。
可能的生日数量变得很大时会发生什么
另一种推广关注的是当可能的类别(生日)数量变得非常大时的极限行为。研究者利用点过程理论的工具——本质上是一种描述新对象随机到达的方式——证明了某些与生日相关的过程在极限下收敛于泊松过程[4]。这为该模型的许多特征给出了分布极限定理,而不只是基本的匹配概率。
一种相关方法研究稀疏化的多级点过程,其中“稀疏化”指的是随机移除一些点,以便关注不同的完成层级。这给出了在随机时刻有多少类别达到较低完成层级的联合极限分布[2]。这些结果偏技术性,但实际意义在于:推广的生日问题可以用与其他占位和碰撞问题相同的渐近工具来分析。
本文引用的文献
碰撞何时过多?生日问题的变体
该论文讨论了用于检测数据集中碰撞或近碰撞数量何时超出随机水平的统计与概率方法,并将这些方法与生日问题和占位问题联系起来。
广义生日问题中稀疏化多级点过程的渐近行为
该论文证明了在广义生日问题中,稀疏化多级点过程弱收敛于各层级独立的极限泊松过程,并推导出在随机时刻有多少类别达到较低完成层级的联合极限分布。
生日问题的一个推广与色多项式
该论文将生日问题推广到非均匀生日分布和特定匹配配对的情形,利用色多项式根的界来判断不均匀性会提高还是降低匹配配对出现的概率。
广义生日问题中的极限定理
该论文通过在实数线可数副本构成的度量空间上定义点过程,并证明当类别数趋于无穷时该过程弱收敛于泊松点过程,从而为广义生日问题的各种特征建立了极限定理。
共同祖先与生日问题
该论文利用人口模型和双型生日问题估计,对于大约1960—1965年出生的随机选取的两名非裔美国人,他们至少共享一位被强行运往北美的非洲祖先的概率约为19%—31%。
