《生日问题的简单近似公式》由会员分享，可在线阅读，更多相关《生日问题的简单近似公式（3页珍藏版）》请在金锄头文库上搜索。
1、生日问题的简单近似公式 Matthias Arnold、verner Glab 摘要在不考虑闰年，并假设每一天都是等可能性的情形，我们求得n个人中至 少 ：2或3个人有相同生日概率的近似虽然在文献中有可用的确切公式，但 在课堂上用这些公式的一个可能的缺点是它们太复杂作为一种不同的方法， 我们建议一个容易计算的近似，它仍然提供接近的答案此外，这个近似对于 需要多少人，使得他们中至少2或3人有相同生日概率超过给定值的问题有一 个方便的答案 著名的生日问题与在一个随机选取的人群中有相同生日的概率有关大多数学生惊 奇地了解到，在超过22人的情形，其中至少2人有相同生日的概率大于05一些作者 把生日问题
2、推广到多于2人有相同生日61确定数目的人有相同生日4生日在不同日 子5】在相邻的d天里有2个或多个生日(7，或每两个生日至少相距d天1等情形2 对这些文献都有介绍，并且包含了大多数所得到的公式本文提出一些容易计算的近似 公式 令pk(n)表示在几个人中至少 人有相同生日的概率不考虑闰年，并假设生日是 等分布的，那么对于k：2和k：3，这些概率为 p2(n)=1一(365 -n )1365， (1) p2【nJ l一， (1) 一 研 ， (2) )=卜 ， (2) 其中表示下取整(floor)函数(2，公式(2)特别地，p3(n)的求值相当复杂，因为他 需要大约n2项的计算对于大的 ，计算更复
3、杂 作为一个替代，我们提出下述近似： p (礼)1-exp(一0438695n2，和ps(n)1-exp(01336854 n3 (3) 这些公式完全不需要任何求和，并且它们比(2)中任何一项都易于计算 这些近似式由3中的公式(75)所启发，该公式展示了，对于一般的c个不同类的 情形，在同一类中有 个或更多人的概率P所需要的人数n可以通过关于n解方程 ： n( ) c(岛+1) 译自：The AmerMathMonthly，Vo1120(2013)，No7，p645648，Simple Approximation Formulas for the Birthday Problem，Matthi
4、as Arnold and Werner Glat3，figure number 1Copyright2014 the Mathematical Association of AmericaReprinted with permissionAll rights reserved美国数 学协会授予译文出版许可 Matthias Arnold的邮箱地址是arnoldstatistiktu-dortmundde 287 而得到近似注葸，对于固定的后和佗我们有 唧(一 ) 和 lira( 一 ) 这样，如果我们用几代替(4)的左端，那么关于Pk(n)求解(4)就得到 p )1一p(一 ) 对于C：36
5、5，如果我们分别用0489和01384代替常数12 1和13 1，那么这些近似式还 可以进一步改进我们使得绝对逼近误差极小化来确定这些常数 图1精确值和近似值p2(n)(左)，p3(n)(右) 且不计其简单，这些近似也是相当好的图l的左图对于 ：2比较了真实概率(用 (1)计算，画以实线)与近似公式(画以虚线)右图对于七=3展示了相应的结果这些 近似是如此地有效，以致几乎看不出任何差别绝对逼近误差一致地小，对于k=2 小于0009，对于k：3小于0007 除了近似程度之高，公式(3)还有两个主要的贡献：(i)极容易计算，(ii)可以解析地 解出礼第2点可以对下述问题给出一个简单的答案：需要多少
6、人才能使其中至少七人 有相同生日的概率大于p?为了用精确公式回答这个问题，要逼近正确值，我们必须对不 同的n对(1)或(2)求值，对于k=3，每次求值需要对大约n2项做计算而用(3)来 做就大为容易了令(3)的右端等于P并对n求解，直接得到 (一 ) ，和 p (一 ) 。， 以致如果佗分别大于22和87，那么至少2人和3人有相同生日的概率超过P=05对 于其他情形概率的计算同样也很简单 我们得到结论：所提出的公式对于精确地概率提供了一个上佳的近似，而它又易于 计算，因此在实践中它是有用的 致谢 (略) 参考文献 MAbramson，W0JMoser，More birthday surpris
7、es，AmerMathMonthly 77 (1970)856858，available at http：dxdoiorglO23072317022 (下转257页) 288 11】 12 【13】 14】 17 18 A primitive trinomial of degree 6972593，MathComp74(2005)，10011002 RPBrent and PZimmermann A multilevel blocking distinctdegree factorization algorithm，Finite Fields and Applications：Contempo
8、rary Mathematics 461(2008)， 47 58 Ten new primitive binary trinomials，MathComp78(2009)，1197-1199 Jvon zur Gathen and JGerhard，Modern Computer Algebra，Cambridge UnivPress， 】999 2008，146-155 TKumada，HLeeb，YKurita，and MMatsumoto，New primitive t-nomials(t：3，5) over GF(2)whose degree is a Mersenne expone
9、nt，MathComp69(2000)，81i-814 Corrigenda：ibid 71 f2002)，1337_1338 TNicely，A new error analysis for Bruns constant，Virginia Journal of Science 52 (2001)，45-55 AEPelletSur la d6composition dune fonction entire en facteurs irr6ductibles suiv ant an module premier P，Comptes Rendus de lAcad6mie des Science
10、s Paris 86(1878)， 1071 1072 JMPollard，A Monte Carlo method for factorization，BIT 15(1975)，331-334 ASchSnhage，Schnelle Multiplikation von Polynomen fiber K6rpern der Charakteristik 2，Acta Informatica 7 f 1977)，395-398 VShoup，NTL：A library for doing number theoryhttp：wwwshoupnetntl LStickelberger，Uber
11、 eine neue Eigenschaft der Diskriminanten algebraischer ZahlkSrper， Verhandlungen des ersten Internationalen MathematikerKongresses，Zfirich，1897，182 193 RGSwan Factorization of polynomials over finite fields，Pacific JMath12(1962)， 1099-1 106 SWagstaffJr，The Cunningham Projecthttp-homesceriaspurdueed
12、usswcun Gwl0ltman et a1GIMPs，The Great Internet Mersenne Prime Search，http：wwwmer senneorg (韩伟谌稳固译 谌稳固校) 木木木木木木木丰爿()lc)lc木术 木木木丰木木水木木丰木木 木术爿c爿c木水水术木丰爿(爿(木木木木丰术爿c：Ic木丰：1c：Ic术木木木丰木爿c爿(木丰木爿c木丰木木木木半半木水 木 (上接288页) 21 ADasGupta，The matching birthday and the strong birthday problem：a contemporary review JS
13、tatistPlannInference 130(2005)377_389，available at http：dxdoi orgl10101611spi200311015 31 PDiaconis，FMosteller，Methods for studing coincidences，JAmetStatistASSOC17 f19891 853-861，available at http：dxdoiorg101O8OO1621459198910478847 f4RLHocking，NCSchwertman，An extension of the birthday problem to exa
14、ctly后 matching，College MathJ17(1986)315321，available at http：dxdoiorg10 23O7268628O 5WKnight，DMBloom，A birthday problem，AmerMath 11411142available at http：dxdoiorg1023072318556 6EHMcKinney，Generalized birthday problem，Amer：Math 385 387available at http：dxdoiorglO23072315408 7JINaus，An extension of the birthday problem，AmerStatist Monthly 80(1973) Monthly 73(1966) 22(1968)27 29 (陆柱家译 陈凌宇校) 257 5 6 7 8 9 加
