Essays/Birthday Problem
< Essays
Jump to navigation
Jump to search
What is the probability that n people chosen at random will have some pair of them having the same birthday? We make the following simplifying assumptions:
- There are 365 days in a year.
- A person is equally likely to be born on any day of the year.
For n>:365 , the probability is 1. For n<365 , the probability is 1 minus the probability of the n persons all having distinct birthdays. Thus:
] n=: i.365 NB. number of people 0 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 ... 365 ^ n NB. number of all arrangements of birthdays 1 365 133225 4.86271e7 1.77489e10 6.47835e12 2.3646e15 8.63078e17 3.15023e20 1.14984e23 4.1969e25 ... (!n) * n!365 NB. number of ways of having n distinct birthdays 1 365 132860 4.82282e7 1.74586e10 6.30256e12 2.26892e15 8.14542e17 2.91606e20 1.04103e23 ... (365^n) %~ (!n) * n!365 NB. probability of having n distinct birthdays 1 1 0.99726 0.991796 0.983644 0.972864 0.959538 0.943764 0.925665 0.905376 0.883052 0.858859 ... ] p=: -. (365^n) %~ (!n)*n!365 NB. probability of some pair having the same birthday 0 0 0.00273973 0.00820417 0.0163559 0.0271356 0.0404625 0.0562357 0.0743353 0.0946238 0.116948 .... 0.5 (< i. 1:) p NB. smallest n for which the probability is at least 0.5 23
The expression for p is problematic computationally for large n (see _30{.p ), because the numerator and the denominator in the division are both extremely large. The problem can be ameliorated with some algebraic simplifications:
(365^n) %~ (!n) * n!365 (365^n) %~ (!n) * (*/@:(365-i.)"0 n) % !n (365^n) %~ */@:(365-i.)"0 n ([: */ 365 %~ 365-i.)"0 n
That is, the probabilities are:
] q=: -. ([: */ 365 %~ 365-i.)"0 n
0 0 0.00273973 0.00820417 0.0163559 0.0271356 0.0404625 0.0562357 0.0743353 0.0946238 0.116948 ...
_8 {. q
1 1 1 1 1 1 1 1
_8 {. ([: */ 365 %~ 365-i.)"0 n
1.13677e_141 2.49155e_143 4.77831e_145 7.85476e_147 1.07599e_148 1.17917e_150 9.69182e_153 5.31059e_155
load 'plot'
plot n;q
The following are selected values from a table of n , q (some pair having the same birthday), and 1-q (no pair having the same birthday; n distinct birthdays).
t=: 0 0j10 0j10 ": n ,. q ,. (1-q)
$t
365 29
(30{.t) ,"1 ' ' ,"1 (100+i.30){t
0 0.0000000000 1.0000000000 100 0.9999996928 0.0000003072
1 0.0000000000 1.0000000000 101 0.9999997769 0.0000002231
2 0.0027397260 0.9972602740 102 0.9999998387 0.0000001613
3 0.0082041659 0.9917958341 103 0.9999998837 0.0000001163
4 0.0163559125 0.9836440875 104 0.9999999166 0.0000000834
5 0.0271355737 0.9728644263 105 0.9999999403 0.0000000597
6 0.0404624836 0.9595375164 106 0.9999999575 0.0000000425
7 0.0562357031 0.9437642969 107 0.9999999698 0.0000000302
8 0.0743352924 0.9256647076 108 0.9999999787 0.0000000213
9 0.0946238339 0.9053761661 109 0.9999999850 0.0000000150
10 0.1169481777 0.8830518223 110 0.9999999895 0.0000000105
11 0.1411413783 0.8588586217 111 0.9999999926 0.0000000074
12 0.1670247888 0.8329752112 112 0.9999999949 0.0000000051
13 0.1944102752 0.8055897248 113 0.9999999965 0.0000000035
14 0.2231025120 0.7768974880 114 0.9999999976 0.0000000024
15 0.2529013198 0.7470986802 115 0.9999999983 0.0000000017
16 0.2836040053 0.7163959947 116 0.9999999988 0.0000000012
17 0.3150076653 0.6849923347 117 0.9999999992 0.0000000008
18 0.3469114179 0.6530885821 118 0.9999999995 0.0000000005
19 0.3791185260 0.6208814740 119 0.9999999996 0.0000000004
20 0.4114383836 0.5885616164 120 0.9999999998 0.0000000002
21 0.4436883352 0.5563116648 121 0.9999999998 0.0000000002
22 0.4756953077 0.5243046923 122 0.9999999999 0.0000000001
23 0.5072972343 0.4927027657 123 0.9999999999 0.0000000001
24 0.5383442579 0.4616557421 124 1.0000000000 0.0000000000
25 0.5686997040 0.4313002960 125 1.0000000000 0.0000000000
26 0.5982408201 0.4017591799 126 1.0000000000 0.0000000000
27 0.6268592823 0.3731407177 127 1.0000000000 0.0000000000
28 0.6544614723 0.3455385277 128 1.0000000000 0.0000000000
29 0.6809685375 0.3190314625 129 1.0000000000 0.0000000000
See also
Contributed by Roger Hui.