查看“︁生日問題”︁的源代码

{{Copy edit|date=2018年4月}}
{{for|新加坡及亞洲學校數學奧林匹克的題目|謝麗爾的生日}}
{{NoteTA
| G1 = IT
| G2 = Math
| 1 = zh-hans:算法; zh-hant:算法;
}}'''生日問題'''是一個[[概率论|機率論]]中的問題，它的敘述是：「需要多少人聚在一起，才能讓其中至少有兩人同一天生日的機率超過一半？」

答案令人意外，只需要23人。這個問題有時被稱為「'''生日悖論'''」，不過這其實並不是真正的[[悖论]]，只是因為結果違反了一般人的直覺。大多数人会认为23人中兩人同生日的[[機率]]應該遠小於50%。它衍生出的數學理論被用於設計一種名為「'''[[生日攻击]]'''」的密碼破解方法。

== 解释 ==

生日問題可理解成盲射打靶问题。首先計算：23人皆不同生日的概率是多少？可想像一間有23人進入的房間，這23人依次進入，每個進入的人的生日都與房裏其他人的生日不同的概率依次是1、<math display="inline">\frac{364}{365}</math>、<math display="inline">\frac{363}{365}</math>、<math display="inline">\frac{362}{365}</math>、<math display="inline">\frac{361}{365}</math>等。先入房的人的生日皆不同的概率很高，前五个是1×<math display="inline">\frac{364}{365}</math>×<math display="inline">\frac{363}{365}</math>×<math display="inline">\frac{362}{365}</math>×<math display="inline">\frac{361}{365}</math>=97.3%；而最后入房的几人就完全不同，他們入房且找不到同生日者的概率是<math display="inline">\frac{345}{365}</math>、<math display="inline">\frac{344}{365}</math>、<math display="inline">\frac{343}{365}</math>。这种概率可看成对靶的盲射：靶有365格，其中17个左右黑格，其余白格。假设每枪必中靶并且分布符合[[几何概型]]的话，连射12枪左右任何一发都没有击中黑格的概率（投射于房间里的人生日皆不同）十分微小。

理解生日問題的关键在于考虑上述“依次入房”模型中最后几个入房的人“全都没碰到同生日的人”概率多少。

简言之，大多数人之所以会认为23人中兩人同生日的概率应该远远小于50%，是因为将问题理解为“其他22人与''你''同生日的概率”，而非问题真諦“23人中两两之间存在生日相同”。如果有考虑这点，直觉上会将原来的概率乘以23''（注意：此算法并不正确）''，则会意识到概率很大。

== 概率估计 ==

假設有''n''個人在房內，如果要計算兩人同生日的機率，在不考慮特殊因素如[[閏年]]、[[雙胞胎]]的前提下，假設一年365日出生概率平均分佈（現實的出生機率不是平均分佈）。

計算概率的方法是，首先找出<u style="text-decoration:overline">p</u>''（''n''）''表示''n''人中，每人生日都不同的概率。假如''n'' > 365，根據[[鴿巢原理]]其概率為0，假设''n'' ≤ 365，则概率为

:<math>\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{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365}</math>
[[File:Birthday Paradox.svg|thumb|290px|该图片显示特定人数对应的2个人生日一样的概率]]
因为第二人不能跟第一人同生日（概率是364/365），第三人不能跟前两人同生日（概率是363/365），依此类推。用[[阶乘]]可写成如下形式

:<math>{ 365! \over 365^n (365-n)! }</math>

''p''(''n''）表示''n''个人中至少兩人同生日的概率

:<math> p (n) = 1 - \bar p (n)=1 - { 365! \over 365^n (365-n)! }</math>

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

''n''是23時概率约0.507。其他人數的概率用上面算法可得出：
{| class="wikitable"
!''n''!!''p''（''n''）
|-
|10 || 12%
|-
|20 || 41%
|-
|30 || 70%
|-
|50 || 97%
|-
|100 || 99.99996%
|-
|200 || 99.9999999999999999999999999998%
|-
|300 || 1 −（7×10<sup>−73</sup>）
|-
|350 || 1 −（3×10<sup>−131</sup>）
|-
|≥366 || 100%
|}

[[File:Birthday paradox.svg|thumb|290px|比较p (n) = 任意两人同生日的概率；q (n) =和某人同生日的概率]]
注意所有人都是随机选出：作为对比，''q''(''n'')表示房间中有''n+1''人，當中与特定人（比如你）同生日的概率：

: <math> q (n+1) = 1- \left( \frac{364}{365} \right)^n </math>

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

== 数学论证（非数字方法） ==

[[保羅·哈爾莫斯|保羅·哈莫斯]]在自传中认为生日問題只用计算数值来解释是种悲哀，所以给出了一种概念数学方法的解释（尽管这方法有一定的误差）：乘积

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

等于1－''p''（''n''），因此关注第一个''n''，欲使乘积小于1/2。由[[平均数不等式]]可知：

:<math>\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)</math>

再用已知的1到''n''－1所有整数和等于''n''（''n''－1）/2，然后用不等式1－''x'' < ''e''<sup>−x</sup>，可得到：
:<math>\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}</math>

:<math>=\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^2-n)/730}</math>

如果仅当

:<math>n^2-n>730\log_e 2\cong 505.997\dots</math>

最后一條表达式的值会小于0.5。其中log<sub>''e''</sub>表示[[自然对数]]，'''略小于'''506，如果取''n''<sup>2</sup>－''n''=506就得到''n''＝23。

在推导中，哈莫斯写道：

{{quote|这推論是基于数学系学生必须掌握的重要工具。生日问题曾是用来演示纯思维如何胜过机械计算的绝妙例子：这些不等式一两分钟就写得出，但乘法运算就要更多时间且更易出错，无论使用的工具是铅笔还是老式电脑。计算器不能提供的是理解力、数学才能、或产生更高级、普适化理论的坚实基础。<ref>原文：The reasoning is based on important tools that all students of mathematics should have ready access to.  The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What [[calculator]]s do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories</ref>}}

然而哈莫斯的推論只显示'''至少'''超過23人就能保证平等机会下的生日匹配。因为不知道给出的不等式有多強（嚴格、清晰），因此無法藉此計算過程確定n＝22是否能讓機率過半；相反，現在任何人都可用Microsoft Excel等個人電腦程式在幾分鐘內把整幅機率分佈圖畫出來，對問題答案很快就有通盤掌握，一目了然。

== 泛化和逼近 ==
[[File:Birthday paradox approximation.svg|thumb|right|300px|用公式<math>p (n)\sim 1-1/\exp(n^2/(2N))</math>（紅綫）與真實概率（黑綫）的比較]]
生日問題可以推广一下：假设有''n''人，每人都随机从''N''个特定的数中选一个数出来（N可能是365或其他正整数）。

''p''（''n''）表示有两个人选择了同样的数字，这概率多大?

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

:<math>p (n)\sim 1-1/\exp(n^2/(2N))</math>。

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

类似的结果可以根据上面的推导得出。
:<math>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}</math>
:<math>p(n;d) \approx 1 - e^{-(n(n-1))/2d}</math>　　　　　　　　　　　　　
:<math>n(p;d)\approx \sqrt{2d\ln\left({1 \over 1-p}\right)}+{1 \over 2}</math>　　　　　　　　　　
:<math>p(n;d) = 1 - \left( \frac{d-1}{d} \right)^n </math>

== 反算问题 ==

反算问题可能是：

:对于确定的概率'''p'''…

:…找出最大的''n''（''p''）满足所有的概率''p''（''n''）都小于给出的''p''，或者

:…找出最小的''n''（''p''）满足所有的概率''p''（''n''）都大于指定的''p''。

这问题有如下逼近公式：

:<math>n (p)\approx \sqrt{2\cdot 365\ln\left({1 \over 1-p}\right)}+{1 \over 2}</math>。

=== 举例 ===

{| class="wikitable"
|-----
| colspan="3" | 逼近　|| colspan="4" |　估计''N'' =365
|-----
| ''p'' || 　 ''n''推广||    n<''N'' =365
|　 ''n''↓ || ''p''（''n''↓） ||　''n''↑||''p''（''n''↑）
|-----
| 0.01 || 　（0.14178 √''N''）+0.5　 ||  3.20864
| align="right" |3 || 0.00820 || align="right" | 4 || 0.01636
|-----
| 0.05 || 　（0.32029 √''N''）+0.5　 ||  6.61916
| align="right" | 6 || 0.04046 || align="right" | 7 || 0.05624
|-----
| 0.1 || 　（0.45904 √''N''）+0.5　 ||  9.27002
| align="right" | 9 || 0.09462 || align="right" | 10 || 0.11695
|-----
| 0.2 || 　（0.66805 √''N''）+0.5　 ||  13.26302
| align="right" | 13 || 0.19441 || align="right" | 14 || 0.22310
|-----
| 0.3 || 　（0.84460 √''N''）+0.5　 || 16.63607
| align="right" | 16 || 0.28360 || align="right" | 17 || 0.31501
|-----
| 0.5 || 　（1.17741 √''N''）+0.5　 || 22.99439
| align="right" | 22 || 0.47570 || align="right" | 23 || 0.50730
|-----
| <div style="color:magenta">0.7</div>
| 　（1.55176 √''N''）+0.5
| <div style="color:magenta">30.14625</div>
| align="right" | 30
| <div style="color:magenta">0.70632</div>
| align="right" | 31 || 0.73045　　　（正確值：n↓=29, n↑=30）
|-----
| 0.8 || 　（1.79412 √''N''）+0.5　 || 34.77666
| align="right" | 34 || 0.79532 || align="right" | 35 || 0.81438
|-----
| <div style="color:magenta">0.9</div>
| 　（2.14597 √''N''）+0.5
| <div style="color:magenta">41.49862</div>
| align="right" | 41
| <div style="color:magenta">0.90315</div>
| align="right" | 42 || 0.91403　　　（正確值：n↓=40, n↑=41）
|-----
| <div style="color:magenta">0.95</div>
| 　（2.44775 √''N''）+0.5
| <div style="color:magenta">47.26414</div>
| align="right" | 47
| <div style="color:magenta">0.95477</div>
| align="right" | 48 || 0.96060　　　（正確值：n↓=46, n↑=47）
|-----
| <div style="color:magenta">0.99</div>
| 　（3.03485 √''N''）+0.5
| <div style="color:magenta">58.48081</div>
| align="right" | 58
| <div style="color:magenta">0.99166</div>
| align="right" | 59 || 0.99299　　　（正確值：n↓=56, n↑=57）
|}

注意：某些值<span style="color:magenta">有色</span>，说明逼近'''不'''总是正确。

== 经验性测试 ==

生日問題可以用计算机代码经验性模拟

<syntaxhighlight lang="pascal">
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;
</syntaxhighlight>

生日問題也可以用Microsoft Excel Spreadsheet模拟
<table border="1" >
<th></th>
<th>人数</th>
<th>人数对应的生日相同的概率</th>
<tr>
<td><center> 1 </center></td>
<td>&nbsp;  1 </td>
<td> &nbsp; =1-PERMUT(365,A1)/POWER(365,A1)</td>
</tr>
<tr>
<td> <center> 2 </center> </td>
<td>&nbsp; =A1+1</td>
<td>&nbsp; =1-PERMUT(365,A2)/POWER(365,A2)</td>
</tr>
<tr>
<td> <center> 3 </center> </td>
<td>&nbsp;  =A2+1</td>
<td>&nbsp;  =1-PERMUT(365,A3)/POWER(365,A3)</td>
</tr>
</TABLE>

当行数达到23（即人数），可看到概率结果开始過半。

== 应用 ==

生日問題普遍的应用于检测[[哈希函数]]：''N''-[[位]]长度的哈希表可能发生碰撞测试次数不是2<sup>''N''</sup>次而是只有2<sup>''N''/2</sup>次，这结论用在破解[[密码学散列函数]]的[[生日攻击]]中。

生日问题隐含的理论已经在[Schnabel 1938]名字叫做[[捉放法]]（capture-recapture）的统计试验得到应用，来估计湖的鱼数。

== 不平衡概率 ==

就像上面提到的，現实世界人口的生日并非平均分佈，这种非均衡生日概率问题也已解决。{{Citation needed||date=2016年9月}}

== 近似匹配 ==

此问题的另外一个泛化是求在{{mvar|n}}人中有两人的生日同在{{mvar|k}}日历天内的概率。假设有{{mvar|m}}个同等可能的生日。<ref name="abramson">M. Abramson and W. O. J. Moser (1970) ''More Birthday Surprises'', [[American Mathematical Monthly]] '''77''', 856–858</ref>

:<math> \begin{align} p(n,k,m) &= 1 - \frac{ (m - nk -1)! }{ m^{n-1} \bigl(m - n(k+1)\bigr)!}\end{align} </math>

能找到两个人生日相差{{mvar|k}}天或更少的概率高于50%所需要的人数：

:{| class="wikitable" style="text-align: center"
! {{mvar|''k''}} !! {{mvar|n}}<br>for {{math|''m'' {{=}} 365}}
|-
|0 || 23
|-
|1 || 14
|-
|2 || 11
|-
|3 || 9
|-
|4 || 8
|-
|5 || 8
|-
|6 || 7
|-
|7 || 7
|}

只須随机抽取7人，找到两人生日相差一周内的概率就会過半。<ref name="abramson"/>

==其它相關生日錯覺機率問題==

星期二男孩問題：一個兩孩家庭有一個男孩，他是星期二出生的，那麼另一個孩子也是男孩的機率是多少？答：13/27<ref>{{cite web |author1=Jesper Juul |title=Tuesday Changes Everything (a Mathematical Puzzle) |url=https://www.jesperjuul.net/ludologist/2010/06/08/tuesday-changes-everything-a-mathematical-puzzle/ |website=The Ludologist |access-date=2022-05-01 |archive-date=2022-01-24 |archive-url=https://web.archive.org/web/20220124044739/https://www.jesperjuul.net/ludologist/2010/06/08/tuesday-changes-everything-a-mathematical-puzzle/ }}</ref>

== 参考 ==
* 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页。这一论文证明了当生日按照平均分布，两个生日相同的概率最小。

== 相关条目 ==
* [[概率论]]
* [[生日]]
* [[生日攻击]]
* [[哈希函数]]

== 參考文獻 ==
{{reflist}}

== 外部链接 ==
* http://www.efgh.com/math/birthday.htm {{Wayback|url=http://www.efgh.com/math/birthday.htm |date=20210309210135 }}
* http://www.teamten.com/lawrence/puzzles/birthday_paradox.html {{Wayback|url=http://www.teamten.com/lawrence/puzzles/birthday_paradox.html |date=20210125055411 }}
* http://science.howstuffworks.com/question261.htm {{Wayback|url=http://science.howstuffworks.com/question261.htm |date=20080522125530 }}
* http://mathworld.wolfram.com/BirthdayProblem.html {{Wayback|url=http://mathworld.wolfram.com/BirthdayProblem.html |date=20210308175928 }}
* http://www.atriumtech.com/pongskorn/birthdayparadox/birthdayparadox.htm {{Wayback|url=http://www.atriumtech.com/pongskorn/birthdayparadox/birthdayparadox.htm |date=20160304123412 }}

[[Category:概率论悖论]]
[[Category:概率与统计|Sheng]]
[[Category:生日]]