# Essays/Birthday Problem

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.