生日悖论原理与计算

房间内需要有多少人，才能保证 100% 的概率让至少两人生日相同？

答案：367人（因为有 366 个可能的生日，包括 2 月 29 日）。

上面的这个问题很简单。请尝试自己回答下面这个问题。

房间内需要有多少人，才能让至少两人生日相同的概率达到 50%？

答案：23人

这个数字出奇地低。事实上，我们只需要 70 人就能让概率达到 99.9%。

让我们来讨论一下通用公式。

在 n 个人中，有两人生日相同的概率是多少？

假设在一个有 n 个人的房间里，两人生日相同的概率为 P(same)。我们可以通过 P(different) 来轻松评估 P(same)，其中 P(different) 是指所有人生日都不相同的概率。

P(same) = 1 – P(different)

P(different) 可以写成 1 x (364/365) x (363/365) x (362/365) x …. x (1 – (n-1)/365)

我们是如何得到上述表达式的？

为了使所有生日都不相同，从第一个人到最后一个人可以按以下顺序获得生日：

第一个人可以在 365 天中的任意一天过生日

第二个人的生日不能与第一个人相同

第三个人的生日不能与前两个人相同

…………….

……………

第 n 个人的生日不能与之前考虑的 (n-1) 个人中的任何一个相同。

上述表达式的近似

我们可以使用泰勒级数来近似上述表达式。

e^{x}=1+x+\frac{x^{2}}{2!}+…

提供了 e^x 在 x << 1 时的一阶近似：

e^{x}\approx 1+x

为了将此近似应用于最初推导的 p(different) 表达式，设 x = -a / 365。因此，

\Large{e^{\frac{-a}{365}}\approx 1-\frac {a}{365}}

之前为 p(different) 推导的表达式可以写成

1 x (1 – 1/365) x (1 – 2/365) x (1 – 3/365) x …. x (1 – (n-1)/365)

通过将 1 – a/365 的值代入为 e-a/365，我们得到如下结果。

\approx 1\times e^{\frac{-1}{365}}\times e^{\frac{-2}{365}}…\times e^{\frac{-(n-1)}{365}}

\approx 1\times e^{\frac{-(1+2+…+(n-1))}{365}}

\approx 1\times e^{\frac {-(n(n-1))/2}{365}}

因此，

p(same) = 1- p(different)

\approx 1-e^{-n(n-1)/(2 \times 365)}

一个更粗略的近似由下式给出

p(same)

\approx 1-e^{-n^{2}/(2 \times 365)}

通过两边取对数，我们得到了反向公式。

n \approx \sqrt{2 \times 365 ln\left ( \frac{1}{1-p(same)} \right )}

利用上述近似公式，我们可以估算给定概率下所需的人数。例如，下面的 C++ 函数 find() 返回的是使概率大于给定 p 的最小 n 值。

近似公式的实现。

下面的程序用于估算给定概率下所需的人数。

C++

// C++ program to approximate number of people in Birthday Paradox 
// problem
#include 
#include 
using namespace std;

// Returns approximate number of people for a given probability
int find(double p)
{
    return ceil(sqrt(2*365*log(1/(1-p))));
}

int main()
{
   cout << find(0.70);
}

Java

// Java program to approximate number
// of people in Birthday Paradox problem
class GFG {
    
    // Returns approximate number of people 
    // for a given probability
    static double find(double p) {
        
        return Math.ceil(Math.sqrt(2 * 
            365 * Math.log(1 / (1 - p))));
    }
    
    // Driver code
    public static void main(String[] args) 
    {
        
        System.out.println(find(0.70)); 
    }
}

// This code is contributed by Anant Agarwal.

Python3

# Python3 code to approximate number
# of people in Birthday Paradox problem
import math

# Returns approximate number of 
# people for a given probability
def find( p ):
    return math.ceil(math.sqrt(2 * 365 *
                     math.log(1/(1-p))));

# Driver Code
print(find(0.70))

# This code is contributed by "Sharad_Bhardwaj".

C#

// C# program to approximate number
// of people in Birthday Paradox problem.
using System;

class GFG {
     
    // Returns approximate number of people 
    // for a given probability
    static double find(double p) {
         
        return Math.Ceiling(Math.Sqrt(2 * 
            365 * Math.Log(1 / (1 - p))));
    }
     
    // Driver code
    public static void Main() 
    {         
    Console.Write(find(0.70)); 
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to approximate 
// number of people in Birthday
// Paradox problem

// Returns approximate number 
// of people for a given probability
function find( $p)
{
    return ceil(sqrt(2 * 365 *