计算大数的生日概率

Question

在满是 n 个人的房间里，两个人生日相同的概率是 1-p。其中：

p = 365! / 365^n(365 - n)!

显然数字太大无法求解这个方程，有什么创造性的方法可以解决这个问题？

我已经使用模拟以不同的方式解决了这个问题，但我认为公式可能更优雅。

Answer 1

您不想计算全阶乘。相反，计算每一项并乘以结果。

你生日不同的概率：

1 人：364/365
2 人：364/365 * 363/365
3人：364/365 * 363/365 * 362/365
...

鉴于此，您计算 p 如下。

int n = 30;
int i;
double p = 1;
for (i = 1; i < n; i++) {
    p *= (365 - i) / 365.0;
    printf("i=%d, p=%f\n", i, 1-p);
}

Answer 2

我会编写一个如下所示的函数：

double p(int n){
    double res = 1;
    while (n>0){
        res *= (365 - (n--))/365.0;
    }
    return res;
}

Answer 3

另一个解决方案（近似值）：

任意两个人生日不同的概率是364/365。在一个有 n 个人的房间里，有 C(n, 2) = n(n − 1)/2 对人。所以：

p(n) = 364/365 ^ (n * (n-1)/2)

并且对于大于 n = 100 的值，您可以安全地使用下一个 table:

n   p(n)
1   0.0%
5   2.7%
10  11.7%
20  41.1%
23  50.7%
30  70.6%
40  89.1%
50  97.0%
60  99.4%
70  99.9%
100 99.99997%
200 99.9999999999999999999999999998%
300 (100 − (6×10−80))%
350 (100 − (3×10−129))%
365 (100 − (1.45×10−155))%
366 100%
367 100%

Answer 4

你可以利用365！/（365-n）！ = 365 * 364 * ... * (365-(n-1))

所以要计算这一项（假设为 A=365！/（365-n）！），您可以像这样简单地使用上面的数字：

unsinged double A=1; // to make sure there is no overflow
for(int i=0;i<n;i++) A*=365-i;

更进一步：p=A/365^n = (364*363*...*(365-(n-1)))/365^(n-1)= 364/365 * 363/365 * ... (365-(n-1))/365.

所以 p 可以这样计算：

unsigned double p=1;
for(int i=0;i<n;i++) p*= (365-i)/365.0;

线性时间

我认为这应该可行:P

Answer 5

tgamma(n+1) 非常接近 n!。无需循环数百次，这会降低精度，因为每个 *、/ 每次迭代都会失去一点精度。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>

long double fact(int n) {
  return roundl(tgammal(n + 1));
}

double bd_prob(int n) {
  return fact(365)/(powl(365,n)*fact(365-n));
}

int main(void){
  // No problem with 365!
  printf("fact(365) %Le\n", fact(365));
  // No problem with 365 to the 365 power 
  printf("365^365 %Le\n", powl(365, 365));

  printf("prob(22) %f\n", bd_prob(22));
  exit(EXIT_SUCCESS);
}

输出

fact(365) 2.510413e+778
365^365 1.725423e+935  
prob(22) 0.524305

Answer 6

冬青通心粉！多么精彩的表演！

无论如何，计算具有大中间值的此类事物的正确方法是对它们进行 log()

p = exp(log(p))

log(p) = log(365!) - n*log(365) - log((365 - n)!)

对于阶乘，使用 Gamma 函数 G(n+1)=n!，C 库中有一个非常方便的函数可以计算 log(G(x))：lgamma(x)

没有更多的循环，没有长双打，没有 bignum 库，没有溢出...

代码

#include <math.h>
#include <stdio.h>

double b(int n) {
    double l = lgamma(365.0 + 1.0) -
               (double)n * log(365.0) -
               lgamma(365.0 - (double)n + 1.0);

    return exp(l);
}

int main() {
    double p = b(20);
    printf("%e %e\n", p, 1.0 - p);

    return 0;
}

计算大数的生日概率

Calculating Birthday Probability for large numbers

c

probability