- 在线时间
- 2 小时
- 最后登录
- 2017-8-7
- 注册时间
- 2009-6-14
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 13 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 7
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 6
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   2.11% 该用户从未签到
|
本帖最后由 商与儒 于 2009-6-14 15:29 编辑 & d( j4 K; z Y
/ U! P& t9 O- C" G ^0 ^
《生日悖论》是个有名的根据《概率理论》得出的结论。
8 E0 `! Z# F. O+ ] ~先把百度百科的相关内容转摘如下:
7 p8 P* p: Y. z0 _生日悖论是指,如果一个房间里有23个或23个以上的人,那幺至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中,存在两人生日相同的可能性更高。对于60或者更多的人,这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论,从这个数学事实与一般直觉相抵触的意义上,它才称得上是一个悖论。大多数人会认为,23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题,在这个问题之后的数学理论已被用于设计着名的密码攻击方法:生日攻击。
/ V+ j1 _' M9 `2 b( k
1 J z* `2 l/ k! q# J生日悖论是这样描述的:0 O' I% t. L i( O4 S% E, f0 k2 T
不计特殊的年月,如闰二月。
7 c) a! y. C0 `3 r7 R* `先计算房间里所有人的生日都不相同的概率,那么
$ R/ ]/ E% J& Z/ p1 t* S0 }第一个人的生日是 365选365 X& w. t, m J- O% R: |$ k. ^8 ^. w
第二个人的生日是 365选364
6 h0 g* z4 S# c第三个人的生日是 365选363+ k/ ^/ C' D% ]6 W) X7 W) _: u! I. A. S
:2 f9 Y' Z3 \# l! r+ @! |
第n个人的生日是 365选365-(n-1)
0 n, T. k$ T* k' X. V所以所有人生日都不相同的概率是:
- n1 V) I& T9 Y# e# z& T(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365)
* M! m9 F( t9 r! q那幺,n个人中有至少两个人生日相同的概率就是:/ `. H$ B, ~. l- N
1-(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365)
3 d4 w e1 ]1 Z$ a# R所以当n=23的时候,概率为0.507! Q, U, M h7 b+ ^7 t
当n=100的时候,概率为0.9999996 K# C" R2 Z( u
真是不算不知道,一算吓一跳。
4 n2 g1 g4 {* ~* |! `/ g【理解生日悖论】
0 M% u1 v$ [7 [9 t) J3 q1 r 理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如在前面所提到的例子,23个人可以产生23 × 22/2 = 253种不同的搭配,而这每一种搭配都有成功相等的可能。从这样的角度看,在253种搭配中产生一对成功的配对也并不是那样的不可思议。 4 k) N! F/ Z, f7 w3 c4 Z5 b
于是我开始在网上查,看看有没有人提出过这个论断是错的,结果不但没有找到有人说它错,还看到了这些数据:* M# g5 F) B# a3 M
当:
" b) _0 m' B& z3 oN=50,概率为96.3%,
7 J1 b2 K0 m e" Y- n7 x% s( [# lN=60, 概率已经大于99%;
( n/ y$ t4 S% U. p, WN=100,概率为99.99996%; v" l$ u+ c |1 P# u! A
N=200时,居然为0后面29个9!- r9 T$ }& D; x; T, [8 f
: O7 q) _+ t0 ]# g! Y+ z5 O
我也看到了描述这个结论的曲线——N过了60人之后,概率已经大于99%,曲线就像一根渐近线,以几乎平行的方式接近概率等于1的直线,最终在N=366处达到1。
% x' h( F! p, J% _( Q _; M$ G. @还找到Paul Halmos (1916-2006)用数学论证(非数字方法)对这个论断的证明,Halmos还写了这样一段话:
9 C% O! o2 s4 h& i$ B% [! M“这个推导是基于一些数学系学生必须掌握的重要工具。生日问题曾经是一个绝妙的例子,用来演示纯思维是如何胜过机械计算:一两分钟就可以写出这些不等式,而乘法运算则需要更多时间,并更易出错,无论使用的工具是一只铅笔还是一台老式电脑。计算器不能提供的是理解力,或数学才能,或产生更高级、普适化理论的坚实基础。”' u& U G% l. b' a' L
同一篇文章中还有这样的说明:生日悖论普遍的应用于检测哈希函数:N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解cryptographic hash function的生日攻击中。生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用,来估计湖里鱼的数量。9 j) G: ^' P4 O- V5 [7 G
还有不少国外的数学家,用其他一些方法,也得出了生日悖论的结果;甚至还有很多如何用各种程序产生随机数来检验这个悖论正确的例子!我在网上查到的概率学,不管国内外,无一例外将它作为教材;我还查到很多用生日悖论作为直观靠不住的例子的文章和书,很多还是科学家写的书……
) ]; V. o7 L2 D% k7 z* W, ~$ b* m
! K, k! m+ e( p《生日悖论》难道真的是如此神奇而正确的吗?! e( m' }! i a. b8 g
( \1 c6 c2 U3 o, \+ O: s
我用两个办法来检验一下:
4 b, j3 E% J2 H) `$ B一个就是,直接计算“发生两个人以上生日相同的概率”,而不是先算发生生日不同的概率,再用1去减。
! g/ x: V4 V0 h- u9 h由于每个人只能在365天里的某一天出生,所以每个人的生日取值就是全部生日的1/365。6 ^0 w: T4 Q1 j# i, B
N=1 时,不可能发生生日相同的事件,概率: P=0;
$ B* ^( Y2 B# V, ?+ hN=2 时,“任意两个人生日相同”的概率: P=1/365;
1 ~8 a0 h% I( \/ tN=3;时,设3人为A,B,C;
, K; e4 T0 v) G8 G三个人之间有三个“任意两个人生日相同”的可能(三人及三人以上生日都相同的不是基本事件,被排除):
, T5 e& Q0 \2 H% t/ I5 ]AB,AC,BC;8 I ^$ Z' S: [) y! g+ H
因为“任意两个人生日相同”的概率为 1/365;所以三人之间发生两两生日相同的概率为3*(1/365)=3/365;. Z/ z6 b2 w- T$ q
N=4 ;A,B,C,D
% B9 O" t* {# NAB,AC,AD;
. U/ ~+ S( W& ^# O/ B. YBC,BD;) Y" M, n1 o% r. M5 \* e
CD
& d" z$ ^& Z* Q$ d. z& B这里有六个“任意两人生日相同”的可能,所以P=6/365;
! A' c6 R0 ?2 ?# d" Z& i. }- lN=5; A,B,C,D,E; x# p* o1 E+ M6 ~* A4 c( r( ^
AB,AC,AD,AE
1 U# n7 W. {: e* A3 u3 K3 dBC,BD,BE
/ ]; M. l" W, {1 ^2 j9 WCD,CE
! k# ? `: H3 ?. ]DE
: ]' f7 e' A3 ?% ]% I8 I这里有10个“任意两个人生日相同”的可能,所以P=10/365;
) m( p, B0 Y% s' V+ u% Y: {8 D显然,这是个等差级数,等差级数求和的公式为 N(N-1)/2/ Z/ Y/ C, S; W8 u* H7 r$ ?
(写到这里我们明白了,取样23个人的时候,比对“两人生日相同”的次数有253个,就是这样算出来的:23*(23-1)/2=253; )
( k7 e& g$ a9 Q$ i4 F- G& ^则,N个人生日相同的概率P=[N*(N-1)] /(2*365)1 \0 v4 ]. t' d+ I: x0 {
但是,
, s% j' F- M) \+ U% R9 t) Q8 S: K- P5 `当N=20时,有两个人生日相同的概率为 52%,已经超过50%。, X( X6 a! k1 d
当N=27时,有两个人生日相同的概率为 96%4 m4 X6 ~% M3 ~" G+ r
N=28时,有两个人生日相同的概率为 103%!
: [ d# l- u% f% p2 |- A算到这里显然看出这个公式错了!因为概率是不能大于1 的!
[) O0 l \* t% w/ [6 o/ Y: m# e7 a但是从逻辑上、计算上看,我们完全遵循了《概率理论》,这里并没有任何错啊?!4 N; w' F' t! E; y
问题在哪里呢?我们后面再分析。
- f A1 Z+ _( f/ U5 {! q! {% c5 F2 k* g7 L+ A: V
6 n6 B% J& c5 F
我用了第二种方式——扩大它的标度。根据题目的设定,我们知道这个《生日悖论》的结论可以适用于任何标度。假定1年有1000天、10000天、100000天……1 X( @( C% f" q( A$ z
按《生日悖论》的算法,我计算出1-1000中,只要随机取38个数,其中两个数相同的概率就达到50%;在1-10000中,只要随机取118个数,其中两个数相同的概率就达到50%;在1-100000中,只要随机取363个数,其中两个数相同的概率就达到50%。
# o+ K- F: L. X2 e! Z2 \ 如果计算1-100000个数中,取多少数就能使发生两个相同数的概率超过99.999%, 我估计不会超过5%,将它画成曲线,我们一定会看到这根曲线离开0点后,会很快“直冲云霄”(接近1),这时离开“终点(100000)还有十万八千里!后面的数字却早就全部没有意义了,只有那个100001候补守门员在场外守候,因为最后确定概率为1 非它出场不可!
1 `6 c1 E7 k5 F$ Q. L我相信这里一定出问题了!也就是说,我们在365个数字中,只要随机取占总数6.5%个数——23个;在1-1000个数中,只要随机取占总数3.8% 的数——38个;在1-10000中,只要随机取占总数1.18%个数——118个,在1-100000中,只要随机取占总数0.36%个数——363个,则取出的这些数中有两个相同数的概率就都达到了50%!( l8 y% l) s4 j' r, A3 n$ D
如果我们把数字扩大到1亿,我相信这个比例会小于万分之一!在1亿个数里随机的取出不到万分之一的数,却能使这些取出的数里有两个相同数的概率大于50%——这绝对是个不符合事实的结论,与之相悖的不是直观,而是事实!
# S1 p7 e7 y6 @* f( W/ ?; i因为根据对题目的分析,我们知道,这个被取样的系统,是设定为一个最分布最均衡的系统,也就是熵为最大的系统。那就是说,无论你如何取样,无论你取样后如何计算,都不可能改变原系统的熵值,也不应该改变原系统的熵值;同样,无论你怎样取样、取样多少,被取样的群体,也应该是熵为最大的系统、与原系统是一致的。但是《生日悖论》的结论却等于告诉我们,只要一取样,被取样部分的“熵值”就变小了!而且这个变小与原系统的标度有关,标度越大的系统,被取样部分的熵值越低!这与题目给出的先决条件显然是相悖的。所以从熵的角度,我们很容易得出《生日悖论》是个谬误的结论!
6 p6 l. W% [4 e5 f! e% H我们还可以这样来考察《生日悖论》的结论:假定我们对这个熵最大的系统随机取样24人,尽管每次取样的分布都不会一样,但是根据统计学原理,无数次取样的结果应该是线性分布的(因为熵最大、随机取样),那么他们平均分布在12个月的概率应该是最大,也就是平均一个月分布两个人的概率应该是最大的。常识告诉我们,发生两个人生日相同的前提条件,是两个人至少在同一个月里出生,不在同一个月出生的人之间虽然也可以互相比对生日,但是这个比对的结果是确定的概率为0事件(不可能发生的事件),不能列入基本事件。所以23个人虽然有253次比对生日的机会,实际上其中绝大多数是概率为0 的事件,正是由于大量的非基本事件参与了计算,才会得出那么离谱的结论。 |
|