- 浏览: 97079 次
- 性别:
- 来自: 宁德
最新评论
-
oudoud:
非常不错,没见收藏按钮
240多个jQuery插件 -
idning:
ding
生日悖论 -
java之渴望:
<%@ page contentType="& ...
将网页数据导出到Excel(以最简单的方式呈现) -
zhoujiabin810812:
简介明了!
黑莓(BlackBerry)是什么 -
WiseNeuron:
谢谢。标记一下
240多个jQuery插件
生日悖论是指,如果一个房间裡有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,则概率为
因为第二个人不能跟第一个人有相同的生日(概率是364/365), 第三个人不能跟前两个人生日相同(概率为363/365),依此类推。用阶乘可以写成如下形式
p(n)表示 n个人中至少2人生日相同的概率
n≤365,根据鸽巢原理, n大于365时概率为1。
当 n=23发生的概率大约是0.507。其他数字的概率用上面的算法可以近似的得出来:
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% |
注意所有人都是随机选出的:作为对比,q(n)表示房间中 n个其他人中与特定人(比如你)有相同生日的概率:
当n = 22时概率只有大约0.059,约高于十七分之一。如果n个人中有50%概率存在某人跟你有相同生日, n至少要达到253 。注意这个数字大大高于365/2 = 182.5: 究其原因是因为房间内可能有些人生日相同。
数学论证(非数字方法)
在 Paul Halmos 的自传中,他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此,Paul Halmos给出了一种概念数学方法的解释,下面就是这种方法(尽管这个方法包含一定的误差)。 乘积
等于 1-p(n), 因此我们关注第一个n,使得乘积小于1/2,这样我们得到
由平均数不等式得:
(我们首先利用已知的1到n-1所有整数和等于 n(n-1)/2, 然后利用不等式不等式 1-x < e−x.) 如果仅当
最后一个表达式的值会小于0.5。 其中"loge"表示自然对数。这个数略微小于506,运气稍微好一点点就可以达到506,等于n2-n,我们就得到n=23。
在推导中,Halmos写道:
这个推导是基于一些数学系学生必须掌握的重要工具。生日问题曾经是一个绝妙的例子,用来演示纯思维是如何胜过机械计算:一两分钟就可以写出这些不等式,而乘法运算则需要更多时间,并更易出错,无论使用的工具是一只铅笔还是一台老式电脑。计算器不能提供的是理解力,或数学才能,或产生更高级、普适化理论的坚实基础。[1]。
然而Halmos的推导只显示至少需要23人保证平等机会下的生日匹配;因为我们不知道给出的不等式有多清晰,因此n=22能够正切的可能也无法确定。
泛化和逼近
生日悖论可以推广一下:假设有n 个,每一个人都随机地从1和特定的N个数中选择出来一个数(N可能是365或者其他的大于0的整数)。
p(n)表示有两个人选择了同样的数字,这个概率有多大?
下面的逼近公式可以回答这个问题
N=365的结果
泛化
下面我们泛化生日问题: 给定从符合离散均匀分布的区间[1,d]随机取出n个整数, 至少2个数字相同的概率p(n;d) 有多大?
类似的结果可以根据上面的推导得出。
反算问题
反算问题可能是:
对这个问题有如下逼近公式:
举例
逼近 | 估计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% 。这是个更难的问题需要用到容斥原理。结果(假设生日依然按照平均分布)正像在标准生日问题中那样令人吃惊:
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页。这一论文证明了当生日按照平均分布,两个生日相同的概率最小。
发表评论
-
你想知道您的那个端口号被那个程序占用了吗?
2009-09-14 18:24 2565以下文章主要以80端口号为例,如果想知道其他的端口号也可以使用 ... -
在电话接入时处理音频播放
2009-08-11 00:56 985通话是手机最重要的功能,手机来电会抑制正在运行的MIDlet运 ... -
单向陷门函数
2009-08-11 00:55 2715单向陷门函数(One-way Trapdoor Functio ... -
RSA加密算法
2009-08-11 00:54 27681. 密钥的产生① 选两个 ... -
数据加密标准DES
2009-08-11 00:54 1494数据加密标准DES 数据加密算法(Data Encryp ... -
Java做一个最简单的Socket通话程序
2009-08-11 00:53 1117Java中的网络编程是一个很重要的部分,也是其编程优越性的地方 ... -
C/S模式中的远程方法调用
2009-08-11 00:52 2072摘要 基于C/S设计模式, ... -
Java加密和数字签名编程快速入门
2009-08-11 00:51 680文/jwsh1984 本文主要谈一下密码学中的加密和 ... -
Vigenere密码与Playfair密码 收
2009-08-11 00:50 3998维吉尼亚(vigenere)密码,美国南北战争期间联军广泛 ... -
java实现DES加密算法
2009-08-11 00:49 2410一、java实现DES加密算法 为了实现一对密钥对整个项目所有 ... -
DES算法理论
2009-08-11 00:48 1415DES算法理论 本世纪五 ... -
欧拉函数
2009-08-11 00:47 1607当n为1至1000的整数时的值 ... -
悖论概念
2009-08-11 00:47 792其定义可以这样表述:由一个被承认是真的命题为前提,设为B,进行 ... -
TCP/IP端口基础常识大全
2009-08-11 00:44 780端口可分为3大类: 1) 公认端口(Well Known Po ... -
嵌入式处理器的基本概念
2009-08-11 00:42 1070嵌入式系统的核心部件是各种类型的嵌入式处理器,目前全世界嵌入式 ... -
嵌入式实时操作系统的现状和未来
2009-08-11 00:42 1237内容摘要:从RTOS(嵌入式实时操作系统)发展的历史、RTOS ... -
网络编程--WININET
2009-08-11 00:40 1592一个Internet客户端程序的目的是通过Interne ... -
Mod运算
2009-08-11 00:37 1703模p运算 给定一个正整数p,任意一个整数n,一定存在等式 ... -
欧拉定理 (数论)
2009-08-11 00:36 1645在数论中欧拉定理(也称费马-欧拉定理或欧拉函数定理: 若m,a ... -
数字签名和加密
2009-08-11 00:36 3852具体步骤如下。Alice与Bob互换公钥。Alice用自己的私 ...
相关推荐
生日悖论是一个经典的概率问题,它指出在一个房间里只要有23人,就存在至少两人拥有相同生日的概率超过50%。这个悖论揭示了小概率事件在大样本下的可能性。通过Python编程,我们可以模拟这个现象来验证这个理论。 ...
生日悖论,也被称为生日问题,是一个在统计学中经常被提及的概念,它涉及到计算在一组随机选取的人中,至少有两人拥有相同生日的概率。这个概率比直觉上要高得多,通常在23人时,这个概率就已经超过了50%。在MATLAB...
一个房间有23个人,会有两个人生日相同吗?答案是有50%的概率。这就是所谓的生日问题birthday problem)或生日悖论(birthday paradox)。本文回答的问题是,当人数众多时,生日相同的概率达到50%,有多少人。
可以
生日悖论的互动演示 要求 需要来安装依赖项并通过npm运行脚本。 可用命令 命令 描述 npm install 安装项目依赖项 npm start 构建项目并打开运行Web服务器的项目 npm run build 使用生产设置(最小化,丑化等)...
从引起逻辑矛盾的角度来说生日悖论并不是一种悖论,从这个数学事实与一般直觉相抵触的意义上,它才称得上是一个悖论。大多数人会认为,23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题...
这个实例旨在帮助开发者掌握如何在VB环境中实现这些功能,同时理解生日悖论的基本概念。 生日悖论是一个概率理论,它指出在一个房间里,只需要大约23人,就有可能有两个人的生日是同一天。在VB中,我们可以模拟这个...
这个问题,也被称为“生日悖论”或者“生日问题”。看似简单,却往往能引发人们对概率直观理解的疑惑。这里我们将详细探讨这个问题,并通过实例解释为什么在一个50人的婚礼中,有两人同一天生日的概率实际上高达97%...
这个问题通常被称为“生日悖论”,因为直觉上人们往往低估了这个概率。 生日悖论的核心是理解在365天的一年中,如果有n个人,他们生日都不相同的概率是如何随n变化的。首先,第一个人的生日可以是任何一天,所以...
3. **概率计算**:根据“生日悖论”(也称为“生日问题”),计算至少两个人在同一组人中生日相同的概率。生日悖论指出,在一个有23人以上的群体中,有超过50%的概率存在至少两人同一天生日。 4. **可视化**:可能...
在本项目"matlab开发-Birthdayprobabilitysolution"中,我们主要关注的是著名的“生日悖论”问题,这是一个概率论的经典问题。在这个问题中,我们探讨的是在一个房间里需要多少人,才能使得至少有两个人的生日相同的...
生日悖论是概率论中的一个经典问题,它指出在一个小群体中找到两个生日相同的概率比人们直觉上认为的要高。对于任意367人,由于一年最多有366天(非闰年),根据鸽巢原理,至少会有两人在同一天过生日。因为如果...
根据生日悖论,如果有多于366个人,那么在随机选择的情况下,至少会有两个人在同一天过生日,这是因为考虑到闰年可能有366天。这里367人超过了这个数字,所以一定会存在至少一对同一天生日的学生。 3. 不均匀分配...
通过公式计算和模拟计算两种方法,理解并验证了“生日悖论”的概念,即在一个小群体中找到共享生日的概率比直觉上更高。 2. **随机游走曲线**:练习6_02涉及到随机数生成和随机游走理论,通过在每个随机间隔点上生成...
课件列出了一系列日期,可能是为了讨论著名的“生日悖论”,即在一个房间里,需要多少人在一起才有可能至少有两个人生日相同,这个悖论帮助学生理解概率的基本概念和实际应用。 其他章节如“只赢不输的游戏”、...
第五部分涉及生日悖论,这是一个经典的概率问题。在30人的班级中,至少有两位同学生日相同的概率可以通过计算互补事件(所有人生日都不相同)的概率来得到。利用鸽巢原理,可以推算至少两人同月生日的概率。 6. ...
目录 · · · · · · 出版者的话 专家指导委员会 译者序 前言 第一部分 基础知识 引言 第1章 算法在计算中的作用 1.1 算法 1.2 作为一种技术的算法 ...5.4.1 生日悖论 5.4.2 球与盒子 5.4.3 序列
- **背景**:通过模拟实验探讨生日悖论,即在一群随机选取的人中至少两个人生日相同的概率问题。 - **实现方法**: - **随机生日生成**:使用随机数生成函数模拟随机生日。 - **比较生日**:通过循环比较随机生成...
5. **生日悖论**:第9题中提到至少有两人生日相同的概率,这是著名的生日悖论的一个实例,表明在一个相对小的群体中,找到两个人生日相同的概率比直觉要高得多。 6. **逻辑推理**:在选择题部分,如第2题和第4题,...