`
jian0487
  • 浏览: 97079 次
  • 性别: Icon_minigender_1
  • 来自: 宁德
社区版块
存档分类
最新评论

生日悖论

阅读更多

生日悖论是指,如果一个房间裡有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中,存在两人生日相同的可能性更高。对于60或者更多的人,这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论,从这个数学事实与一般直觉相抵触的意义上,它才称得上是一个悖论。大多数人会认为,23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题, 在这个问题之后的数学理论已被用于设计著名的密码攻击方法:生日攻击

 

目录

<script type="text/javascript"></script>

 

对此悖论的解释

理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如在前面所提到的例子,23个人可以产生C(23,2)= 23 × 22/2 = 253 种不同的搭配,而这每一种搭配都有成功相等的可能。从这样的角度看,在253种搭配中产生一对成功的配对也并不是那样的不可思议。

换一个角度,如果你进入了一个有着22个人的房间,房间裡的人中会和你有相同生日的概率便不是50:50了,而是变得非常低。原因是这时候只能产生22种不同的搭配。生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少。

概率估计

假設有 n 個人在同一房間內,如果要計算有兩個人在同一日出生的機率,在不考慮特殊因素的前提下,例如閏年雙胞胎,假設一年365日出生概率是平均分佈的(現實生活中,出生機率不是平均分佈的)。

計算機率的方法是,首先找出p(n)表示 n 個人中,每個人的生日日期都不同的概率。假如n > 365,根據鴿巢原理其概率為0,假设 n ≤ 365,则概率为

\bar p(n) = 1 \cdot \left(1-\frac{1}{365}\right) \cdot \left(1-\frac{2}{365}\right)  \cdots \left(1-\frac{n-1}{365}\right) =\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365}
该图片显示特定人数对应的2个人生日一样的概率

因为第二个人不能跟第一个人有相同的生日(概率是364/365), 第三个人不能跟前两个人生日相同(概率为363/365),依此类推。用阶乘可以写成如下形式

{ 365! \over 365^n (365-n)! }

p(n)表示 n个人中至少2人生日相同的概率

 p(n) = 1 - \bar p(n)=1 - { 365! \over 365^n (365-n)! }

n≤365,根据鸽巢原理, n大于365时概率为1。

n=23发生的概率大约是0.507。其他数字的概率用上面的算法可以近似的得出来:

 

np(n)
10 12%
20 41%
30 70%
50 97%
100 99.99996%
200 99.9999999999999999999999999998%
300 1 − (7 × 10−73)
350 1 − (3 × 10−131)
≥366 100%

 

比较 p(n) = 任意两个人生日相同概率 q(n) =和某人生日相同的概率

注意所有人都是随机选出的:作为对比,q(n)表示房间中 n个其他人中与特定人(比如你)有相同生日的概率:

 q(n) = 1- \left( \frac{364}{365} \right)^n

n = 22时概率只有大约0.059,约高于十七分之一。如果n个人中有50%概率存在某人跟有相同生日, n至少要达到253 。注意这个数字大大高于365/2 = 182.5: 究其原因是因为房间内可能有些人生日相同。

数学论证(非数字方法)

Paul Halmos 的自传中,他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此,Paul Halmos给出了一种概念数学方法的解释,下面就是这种方法(尽管这个方法包含一定的误差)。 乘积

\prod_{k=1}^{n-1}\left(1-{k \over 365}\right)}-

等于 1-p(n), 因此我们关注第一个n,使得乘积小于1/2,这样我们得到

\sqrt[n-1]{\prod_{k=1}^{n-1}\left(1-{k \over 365}\right)}
<{1 \over n-1}\sum_{k=1}^{n-1}\left(1-{k \over 365}\right)}-

平均数不等式得:

\prod_{k=1}^{n-1}\left(1-{k \over 365}\right)
<\left({1 \over n-1}\sum_{k=1}^{n-1}\left(1-{k \over 365}\right)\right)^{n-1}
=\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^2-n)/730}.
}-

(我们首先利用已知的1到n-1所有整数和等于 n(n-1)/2, 然后利用不等式不等式 1-x < e−x.) 如果仅当

n^2-n>730\log_e 2\cong 505.997\dots

最后一个表达式的值会小于0.5。 其中"loge"表示自然对数。这个数略微小于506,运气稍微好一点点就可以达到506,等于n2n,我们就得到n=23。

在推导中,Halmos写道:

这个推导是基于一些数学系学生必须掌握的重要工具。生日问题曾经是一个绝妙的例子,用来演示纯思维是如何胜过机械计算:一两分钟就可以写出这些不等式,而乘法运算则需要更多时间,并更易出错,无论使用的工具是一只铅笔还是一台老式电脑。计算器不能提供的是理解力,或数学才能,或产生更高级、普适化理论的坚实基础。[1]

然而Halmos的推导只显示至少需要23人保证平等机会下的生日匹配;因为我们不知道给出的不等式有多清晰,因此n=22能够正切的可能也无法确定。

泛化和逼近

生日悖论可以推广一下:假设有n 个,每一个人都随机地从1和特定的N个数中选择出来一个数(N可能是365或者其他的大于0的整数)。

p(n)表示有两个人选择了同样的数字,这个概率有多大?

下面的逼近公式可以回答这个问题

p(n)\sim 1-1/\exp(n^2/(2N)).\,

 N=365的结果

File:050329-birthday2.png

泛化

下面我们泛化生日问题: 给定从符合离散均匀分布的区间[1,d]随机取出n个整数, 至少2个数字相同的概率p(n;d) 有多大?

类似的结果可以根据上面的推导得出。

p(n;d) = \begin{cases} 1-\prod_{k=1}^{n-1}\left(1-{k \over d}\right) & n\le d \\ 1 & n > d \end{cases}
p(n;d) \approx 1 - e^{-(n(n-1))/2d}
q(n;d) = 1 - \left( \frac{d-1}{d} \right)^n
n(p;d)\approx \sqrt{2d\ln\left({1 \over 1-p}\right)}}-

反算问题

反算问题可能是:

对于确定的概率 p ...
... 找出最大的 n(p)满足所有的概率p(n)都小于给出的p,或者
... 找出最小的n(p) 满足所有的概率p(n)都大于给定的p

对这个问题有如下逼近公式:

n(p)\approx \sqrt{2\cdot 365\ln\left({1 \over 1-p}\right)}.

举例

 

逼近 估计N :=365
p n 推广 n <N :=365 n p(n↓) n p(n↑)
0.01
0.14178 √N
2.70864
2 0.00274 3
0.00820
0.05 0.32029 √N 6.11916 6 0.04046 7 0.05624
0.1
0.45904 √N
8.77002
8 0.07434 9
0.09462
0.2
0.66805 √N
12.76302
12 0.16702 13
0.19441
0.3 0.84460 √N 16.13607 16 0.28360 17 0.31501
0.5 1.17741 √N 22.49439 22 0.47570 23 0.50730
0.7 1.55176 √N 29.64625 29 0.68097 30 0.70632
0.8 1.79412 √N 34.27666 34 0.79532 35 0.81438
0.9 2.14597 √N 40.99862 40 0.89123 41 0.90315
0.95 2.44775 √N 46.76414 46 0.94825 47 0.95477
0.99
3.03485 √N
57.98081
57
0.99012
58 0.99166

 

注意:某些值被着色,说明逼近 总是正确。

经验性测试

生日悖论可以用计算机代码经验性模拟

days := 365;
numPeople := 1;
prob := 0.0;
while prob < 0.5 begin
    numPeople := numPeople + 1;
    prob := 1 - ((1-prob) * (days-(numPeople-1)) / days);
    print "Number of people: " + numPeople;
    print "Prob. of same birthday: " + prob;
end;

应用

生日悖论普遍的应用于检测哈希函数:N-长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解密码学散列函数生日攻击中。

生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用,来估计湖里鱼的数量。

不平衡概率

就像上面提到的,真实世界的人口出生日期并不是平均分布的。这种非均衡生日概率问题也已经被解决。[Klamkin 1967]

近似匹配

此问题另外一个范化就是求得要在随机选取多少人中才能找到2个人生日相同,相差1天,2天等的概率大于50% 。这是个更难的问题需要用到容斥原理。结果(假设生日依然按照平均分布)正像在标准生日问题中那样令人吃惊:

 

2人生日相差k天 #需要的人数
0   23
1   14
2   11
3    9
4    8
5    7
7    6

 

只需要随机抽取6个人,找到两个人生日相差一周以内的概率就会超过50%。

参考

  • Zoe Emily Schnabel: "The estimation of the total fish population of a lake"(某湖中鱼类总量估计), 美国数学月刊 45 (1938年), 348-352页
  • M. Klamkin,D. Newman: "Extensions of the birthday surprise"(生日惊喜的扩充), Journal of Combinatorial Theory 3 (1967年),279-282页。
  • D. Blom: "a birthday problem"生日问题, 美国数学月刊 80 (1973年),1141-1142页。这一论文证明了当生日按照平均分布,两个生日相同的概率最小。
分享到:
评论
1 楼 idning 2010-09-14  
ding

相关推荐

    python实现生日悖论分析

    生日悖论是一个经典的概率问题,它指出在一个房间里只要有23人,就存在至少两人拥有相同生日的概率超过50%。这个悖论揭示了小概率事件在大样本下的可能性。通过Python编程,我们可以模拟这个现象来验证这个理论。 ...

    生日悖论图:绘制至少一对同学出生日期相同的概率图,相对于班级人口。-matlab开发

    生日悖论,也被称为生日问题,是一个在统计学中经常被提及的概念,它涉及到计算在一组随机选取的人中,至少有两人拥有相同生日的概率。这个概率比直觉上要高得多,通常在23人时,这个概率就已经超过了50%。在MATLAB...

    10000以内50%生日问题的全解

    一个房间有23个人,会有两个人生日相同吗?答案是有50%的概率。这就是所谓的生日问题birthday problem)或生日悖论(birthday paradox)。本文回答的问题是,当人数众多时,生日相同的概率达到50%,有多少人。

    蒙特 猜数字 公约倍 羊车门 凯撒 文本进度条 基本统计量 三国演义Halemt 8串密码 统计字符 生日悖论

    可以

    生日冲突:生日悖论的互动演示

    生日悖论的互动演示 要求 需要来安装依赖项并通过npm运行脚本。 可用命令 命令 描述 npm install 安装项目依赖项 npm start 构建项目并打开运行Web服务器的项目 npm run build 使用生产设置(最小化,丑化等)...

    生日问题编程仿真

    从引起逻辑矛盾的角度来说生日悖论并不是一种悖论,从这个数学事实与一般直觉相抵触的意义上,它才称得上是一个悖论。大多数人会认为,23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题...

    VB实例,综合应用,生日计算题

    这个实例旨在帮助开发者掌握如何在VB环境中实现这些功能,同时理解生日悖论的基本概念。 生日悖论是一个概率理论,它指出在一个房间里,只需要大约23人,就有可能有两个人的生日是同一天。在VB中,我们可以模拟这个...

    小学数学数学故事同一天过生日的概率

    这个问题,也被称为“生日悖论”或者“生日问题”。看似简单,却往往能引发人们对概率直观理解的疑惑。这里我们将详细探讨这个问题,并通过实例解释为什么在一个50人的婚礼中,有两人同一天生日的概率实际上高达97%...

    蓝桥杯学习资料大全-题目参考代码-生日相同概率.zip

    这个问题通常被称为“生日悖论”,因为直觉上人们往往低估了这个概率。 生日悖论的核心是理解在365天的一年中,如果有n个人,他们生日都不相同的概率是如何随n变化的。首先,第一个人的生日可以是任何一天,所以...

    matlab开发-GroupBirthdays

    3. **概率计算**:根据“生日悖论”(也称为“生日问题”),计算至少两个人在同一组人中生日相同的概率。生日悖论指出,在一个有23人以上的群体中,有超过50%的概率存在至少两人同一天生日。 4. **可视化**:可能...

    matlab开发-Birthdayprobabilitysolution

    在本项目"matlab开发-Birthdayprobabilitysolution"中,我们主要关注的是著名的“生日悖论”问题,这是一个概率论的经典问题。在这个问题中,我们探讨的是在一个房间里需要多少人,才能使得至少有两个人的生日相同的...

    2020六年级数学下册5数学广角__鸽巢问题比较简单的鸽巢原理课时练习新人教版

    生日悖论是概率论中的一个经典问题,它指出在一个小群体中找到两个生日相同的概率比人们直觉上认为的要高。对于任意367人,由于一年最多有366天(非闰年),根据鸽巢原理,至少会有两人在同一天过生日。因为如果...

    第二学期人教版六年级数学课课练及答案全册24精选.doc

    根据生日悖论,如果有多于366个人,那么在随机选择的情况下,至少会有两个人在同一天过生日,这是因为考虑到闰年可能有366天。这里367人超过了这个数字,所以一定会存在至少一对同一天生日的学生。 3. 不均匀分配...

    北科数理统计与Matlab上机报告4.pdf

    通过公式计算和模拟计算两种方法,理解并验证了“生日悖论”的概念,即在一个小群体中找到共享生日的概率比直觉上更高。 2. **随机游走曲线**:练习6_02涉及到随机数生成和随机游走理论,通过在每个随机间隔点上生成...

    初中趣味数学选修课PPT课件.pptx

    课件列出了一系列日期,可能是为了讨论著名的“生日悖论”,即在一个房间里,需要多少人在一起才有可能至少有两个人生日相同,这个悖论帮助学生理解概率的基本概念和实际应用。 其他章节如“只赢不输的游戏”、...

    2015-2016(2)概率论与数理统计-信计(A)_参考答案1

    第五部分涉及生日悖论,这是一个经典的概率问题。在30人的班级中,至少有两位同学生日相同的概率可以通过计算互补事件(所有人生日都不相同)的概率来得到。利用鸽巢原理,可以推算至少两人同月生日的概率。 6. ...

    算法导论_(美)

    目录 · · · · · · 出版者的话 专家指导委员会 译者序 前言 第一部分 基础知识 引言 第1章 算法在计算中的作用 1.1 算法 1.2 作为一种技术的算法 ...5.4.1 生日悖论 5.4.2 球与盒子 5.4.3 序列

    计算机实习题目及要求.doc

    - **背景**:通过模拟实验探讨生日悖论,即在一群随机选取的人中至少两个人生日相同的概率问题。 - **实现方法**: - **随机生日生成**:使用随机数生成函数模拟随机生日。 - **比较生日**:通过循环比较随机生成...

    课标实验教材六年级下册 第四、五单元【新课标人教版】精选.doc

    5. **生日悖论**:第9题中提到至少有两人生日相同的概率,这是著名的生日悖论的一个实例,表明在一个相对小的群体中,找到两个人生日相同的概率比直觉要高得多。 6. **逻辑推理**:在选择题部分,如第2题和第4题,...

Global site tag (gtag.js) - Google Analytics