从排列与组合的python实现到”生日问题”的解释
首先定义我们的记号（notation），用整数 i=1,2,…,k 来对房间里的人进行编号，其中 k 是房间里的总人数。不考虑闰年，所有的年份都是 n=365 ，令 b i 表示第 i 个人的生日。我们假设每个人的生日是独立的（这是一个重要假设），则 i 和 j 生日落在同一天 r 的概率为：
Pr{b i =r,b j =r}=Pr{b i =r}Pr{b j =r}=1n 2
他们的生日落在同一天的概率为：
∑ r=1 n Pr{b i =r,b j =r}=∑ r=1 n Pr{b i =r}Pr{b j =r}=n⋅1n 2 =1n
所以这有一个结论，如果两个人生日彼此独立的话，一个人生日在某一天的概率为 1n ，两个人生日在同一天的概率也为 1n 。
再来看，至少两人生日在同一天的概率：
1−A k n n k === 1−n!(n−k)! n k 1−n(n−1)⋯(n−k+1)n k 1−1⋅n−1n n−2n ⋯n−k+1n
又由 e x 的泰勒展开为：
e x =∑ n=0 ∞ x n n! =1+x+x 2 2 +⋯
也即
1+x≤e x
所以如果要求至少有两人生日在同一天的概率 ≥1 ，也即 1−A k n n k ≥12 ，也即：
1⋅n−1n n−2n ⋯n−k+1n ≤12
又由于
1+x≤e x ，所以，
1⋅n−1n n−2n ⋯n−k+1n ≤e −1/n e −2/n ⋯e −(k−1)/n =e −k(k−1)/2n ≤1/2
求解得
k≥(1+1+(8ln2)n − − − − − − − − − − √ )/2 ，当
n=365 时，必须有
k≥23 。
>>> from math import sqrt, log
>>> (1+sqrt(1+8*log(2)*365))/222.99994315123396也即，如果至少有23个人主宰一个房间里，那么至少有两人生日相同的概率至少为1/2 。
在火星上，一年有669个火星日，也即 n=669 ，
>>> (1+sqrt(1+8*log(2)*669))/2
30.957854940707936则在火星上要达到同样的效果，必须有31个火星人。
利用指示器随机变量进行近似分析
利用指示器随机变量（Indicator Random Variable），可以给生日悖论一个简单而近似的分析。对房间中 k 个人中的每一对 (i,j) ，1≤i<j≤k ，定义指示器随机变量 X ij 如下：
X ij =1 i,j生日相同 ={1,0, 如果i,j生日相同否则
又知两个人生日在同一天的概率为
1/n ，所以有：
E[X ij ]=Pr{i,j生日相同}=1n
令
X 表示计数具有相同生日的两人对出现的数目的随机变量：
X=∑ i=1 k ∑ j=i+1 k X ij
对两边取期望并应用
期望的线性性质，得到：
E(X)=∑ i=1 k ∑ j=i+1 k E(X ij )=(k2)1n
因此当 k(k−1)≥2n 时，有相同数目的两人对的期望数目大于1。当 n=365 时，k=28 。