Stone's Note
0%

Birthday problem

发表于 更新于

Birthday problem

Birthday problem 很经典，即在一群人中，求有两个人同一天生日的概率有多大。一种错觉是，假设一年365天（什么闰年等特殊情况都不考虑），那么最少要366个人，才一定能满足有两个人同一天生日，这么看来，要满足两个人同一天生日也需要一个很大的总体人数。

既然是错觉，那一定不对。

计算相同生日的概率P(A)很麻烦，两个人一天，三个人一天。。。。那这么求起来就没头了。这个问题我们如果求P(A)的补集P(A’)，那么 P(A) = 1 - P(A’)。P(A’)即集合中没有任何两个人有相同生日的概率，每个人的生日都是唯一的。

  • 第一个人可以随便在365天内任选一天，概率是 365/365，即一定不会重复
  • 第二个人在抛出第一人的那天的364天内任选一天，概率是364/365
  • 。。。

以此类推，若集合有N个人，那么P(A’)的概率是:
birthday-problem

下面用代码测试一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <math.h>

#define NUM 100

int main(int argc, char** argv)
{
    int i = 0, j = 100;
    double t = 1;
    
    for (i = 1;i <= NUM; ++i, t = 1)
    {   
        t = 1.0 / pow(365, i); 
        for (j = 0; j < i; ++j)
            t *= 365 - j;

        printf("%d %f\n\n", i, 1.0 - t); 
    }   

    return 0;
}
// gcc birthday_problem.c -Wall -g -lm

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
1 0.000000
2 0.002740
3 0.008204
4 0.016356
5 0.027136
6 0.040462
7 0.056236
8 0.074335
9 0.094624
10 0.116948
11 0.141141
12 0.167025
13 0.194410
14 0.223103
15 0.252901
16 0.283604
17 0.315008
18 0.346911
19 0.379119
20 0.411438
21 0.443688
22 0.475695
23 0.507297
24 0.538344
25 0.568700
26 0.598241
27 0.626859
28 0.654461
29 0.680969
30 0.706316
31 0.730455
32 0.753348
33 0.774972
34 0.795317
35 0.814383
36 0.832182
37 0.848734
38 0.864068
39 0.878220
40 0.891232
41 0.903152
42 0.914030
43 0.923923
44 0.932885
45 0.940976
46 0.948253
47 0.954774
48 0.960598
49 0.965780
50 0.970374
51 0.974432
52 0.978005
53 0.981138
54 0.983877
55 0.986262
56 0.988332
57 0.990122
58 0.991665
59 0.992989
60 0.994123
61 0.995089
62 0.995910
63 0.996604
64 0.997190
65 0.997683
66 0.998096
67 0.998440
68 0.998726
69 0.998964
70 0.999160
71 0.999321
72 0.999453
73 0.999561
74 0.999649
75 0.999720
76 0.999777
77 0.999824
78 0.999861
79 0.999891
80 0.999914
81 0.999933
82 0.999948
83 0.999960
84 0.999969
85 0.999976
86 0.999982
87 0.999986
88 0.999989
89 0.999992
90 0.999994
91 0.999995
92 0.999997
93 0.999997
94 0.999998
95 0.999999
96 0.999999
97 0.999999
98 0.999999
99 1.000000
100 1.000000

可以看出，当集合人数超过23人时，就有超过50%的概率有两个人同一天生日，这个数比我们“直觉”的数小了很多。

Reference & Thanks