Topzle Topzle

Birthday problem

Updated: Wikipedia source

Birthday problem

In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share the same birthday. The birthday paradox is the counterintuitive fact that only 23 people are needed for that probability to exceed 50%. The birthday paradox is a veridical paradox: it seems wrong at first glance but is, in fact, true. While it may seem surprising that only 23 individuals are required to reach a 50% probability of a shared birthday, this result is made more intuitive by considering that the birthday comparisons will be made between every possible pair of individuals. With 23 individuals, there are ⁠23 × 22/2⁠ = 253 pairs to consider. Real-world applications for the birthday problem include a cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function, as well as calculating the approximate risk of a hash collision existing within the hashes of a given size of population. The problem is generally attributed to Harold Davenport in about 1927, though he did not publish it at the time. Davenport did not claim to be its discoverer "because he could not believe that it had not been stated earlier". The first publication of a version of the birthday problem was by Richard von Mises in 1939.

Tables

1
1
n
1
p(n)
00.0%
5
5
n
5
p(n)
02.7%
10
10
n
10
p(n)
11.7%
20
20
n
20
p(n)
41.1%
23
23
n
23
p(n)
50.7%
30
30
n
30
p(n)
70.6%
40
40
n
40
p(n)
89.1%
50
50
n
50
p(n)
97.0%
60
60
n
60
p(n)
99.4%
70
70
n
70
p(n)
99.9%
75
75
n
75
p(n)
99.97%
100
100
n
100
p(n)
99.99997%
200
200
n
200
p(n)
(100 − 2×10−28)%
300
300
n
300
p(n)
(100 − 6×10−80)%
350
350
n
350
p(n)
(100 − 3×10−129)%
365
365
n
365
p(n)
(100 − 1.45×10−155)%
≥ 366
≥ 366
n
≥ 366
p(n)
100%
n
p(n)
1
00.0%
5
02.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%
75
99.97%
100
99.99997%
200
(100 − 2×10−28)%
300
(100 − 6×10−80)%
350
(100 − 3×10−129)%
365
(100 − 1.45×10−155)%
≥ 366
100%
p = 10−18
p = 10−18
length of hex string
p = 10−18
no. ofbits(b)
p = 10−15
hash spacesize(2b)
p = 10−12
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 10−9
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 10−6
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 0.001
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 0.01
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 0.25
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 0.50
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 0.75
8
8
length of hex string
8
no. ofbits(b)
32
hash spacesize(2b)
4.3×109
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
2.9
Number of hashed elements such that probability of at least one hash collision ≥ p
93
Number of hashed elements such that probability of at least one hash collision ≥ p
2.9×103
Number of hashed elements such that probability of at least one hash collision ≥ p
9.3×103
Number of hashed elements such that probability of at least one hash collision ≥ p
5.0×104
Number of hashed elements such that probability of at least one hash collision ≥ p
7.7×104
Number of hashed elements such that probability of at least one hash collision ≥ p
1.1×105
(10)
(10)
length of hex string
(10)
no. ofbits(b)
(40)
hash spacesize(2b)
(1.1×1012)
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
47
Number of hashed elements such that probability of at least one hash collision ≥ p
1.5×103
Number of hashed elements such that probability of at least one hash collision ≥ p
4.7×104
Number of hashed elements such that probability of at least one hash collision ≥ p
1.5×105
Number of hashed elements such that probability of at least one hash collision ≥ p
8.0×105
Number of hashed elements such that probability of at least one hash collision ≥ p
1.2×106
Number of hashed elements such that probability of at least one hash collision ≥ p
1.7×106
(12)
(12)
length of hex string
(12)
no. ofbits(b)
(48)
hash spacesize(2b)
(2.8×1014)
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
2
Number of hashed elements such that probability of at least one hash collision ≥ p
24
Number of hashed elements such that probability of at least one hash collision ≥ p
7.5×102
Number of hashed elements such that probability of at least one hash collision ≥ p
2.4×104
Number of hashed elements such that probability of at least one hash collision ≥ p
7.5×105
Number of hashed elements such that probability of at least one hash collision ≥ p
2.4×106
Number of hashed elements such that probability of at least one hash collision ≥ p
1.3×107
Number of hashed elements such that probability of at least one hash collision ≥ p
2.0×107
Number of hashed elements such that probability of at least one hash collision ≥ p
2.8×107
16
16
length of hex string
16
no. ofbits(b)
64
hash spacesize(2b)
1.8×1019
Number of hashed elements such that probability of at least one hash collision ≥ p
6.1
Number of hashed elements such that probability of at least one hash collision ≥ p
1.9×102
Number of hashed elements such that probability of at least one hash collision ≥ p
6.1×103
Number of hashed elements such that probability of at least one hash collision ≥ p
1.9×105
Number of hashed elements such that probability of at least one hash collision ≥ p
6.1×106
Number of hashed elements such that probability of at least one hash collision ≥ p
1.9×108
Number of hashed elements such that probability of at least one hash collision ≥ p
6.1×108
Number of hashed elements such that probability of at least one hash collision ≥ p
3.3×109
Number of hashed elements such that probability of at least one hash collision ≥ p
5.1×109
Number of hashed elements such that probability of at least one hash collision ≥ p
7.2×109
(24)
(24)
length of hex string
(24)
no. ofbits(b)
(96)
hash spacesize(2b)
(7.9×1028)
Number of hashed elements such that probability of at least one hash collision ≥ p
4.0×105
Number of hashed elements such that probability of at least one hash collision ≥ p
1.3×107
Number of hashed elements such that probability of at least one hash collision ≥ p
4.0×108
Number of hashed elements such that probability of at least one hash collision ≥ p
1.3×1010
Number of hashed elements such that probability of at least one hash collision ≥ p
4.0×1011
Number of hashed elements such that probability of at least one hash collision ≥ p
1.3×1013
Number of hashed elements such that probability of at least one hash collision ≥ p
4.0×1013
Number of hashed elements such that probability of at least one hash collision ≥ p
2.1×1014
Number of hashed elements such that probability of at least one hash collision ≥ p
3.3×1014
Number of hashed elements such that probability of at least one hash collision ≥ p
4.7×1014
32
32
length of hex string
32
no. ofbits(b)
128
hash spacesize(2b)
3.4×1038
Number of hashed elements such that probability of at least one hash collision ≥ p
2.6×1010
Number of hashed elements such that probability of at least one hash collision ≥ p
8.2×1011
Number of hashed elements such that probability of at least one hash collision ≥ p
2.6×1013
Number of hashed elements such that probability of at least one hash collision ≥ p
8.2×1014
Number of hashed elements such that probability of at least one hash collision ≥ p
2.6×1016
Number of hashed elements such that probability of at least one hash collision ≥ p
8.3×1017
Number of hashed elements such that probability of at least one hash collision ≥ p
2.6×1018
Number of hashed elements such that probability of at least one hash collision ≥ p
1.4×1019
Number of hashed elements such that probability of at least one hash collision ≥ p
2.2×1019
Number of hashed elements such that probability of at least one hash collision ≥ p
3.1×1019
(48)
(48)
length of hex string
(48)
no. ofbits(b)
(192)
hash spacesize(2b)
(6.3×1057)
Number of hashed elements such that probability of at least one hash collision ≥ p
1.1×1020
Number of hashed elements such that probability of at least one hash collision ≥ p
3.5×1021
Number of hashed elements such that probability of at least one hash collision ≥ p
1.1×1023
Number of hashed elements such that probability of at least one hash collision ≥ p
3.5×1024
Number of hashed elements such that probability of at least one hash collision ≥ p
1.1×1026
Number of hashed elements such that probability of at least one hash collision ≥ p
3.5×1027
Number of hashed elements such that probability of at least one hash collision ≥ p
1.1×1028
Number of hashed elements such that probability of at least one hash collision ≥ p
6.0×1028
Number of hashed elements such that probability of at least one hash collision ≥ p
9.3×1028
Number of hashed elements such that probability of at least one hash collision ≥ p
1.3×1029
64
64
length of hex string
64
no. ofbits(b)
256
hash spacesize(2b)
1.2×1077
Number of hashed elements such that probability of at least one hash collision ≥ p
4.8×1029
Number of hashed elements such that probability of at least one hash collision ≥ p
1.5×1031
Number of hashed elements such that probability of at least one hash collision ≥ p
4.8×1032
Number of hashed elements such that probability of at least one hash collision ≥ p
1.5×1034
Number of hashed elements such that probability of at least one hash collision ≥ p
4.8×1035
Number of hashed elements such that probability of at least one hash collision ≥ p
1.5×1037
Number of hashed elements such that probability of at least one hash collision ≥ p
4.8×1037
Number of hashed elements such that probability of at least one hash collision ≥ p
2.6×1038
Number of hashed elements such that probability of at least one hash collision ≥ p
4.0×1038
Number of hashed elements such that probability of at least one hash collision ≥ p
5.7×1038
(96)
(96)
length of hex string
(96)
no. ofbits(b)
(384)
hash spacesize(2b)
(3.9×10115)
Number of hashed elements such that probability of at least one hash collision ≥ p
8.9×1048
Number of hashed elements such that probability of at least one hash collision ≥ p
2.8×1050
Number of hashed elements such that probability of at least one hash collision ≥ p
8.9×1051
Number of hashed elements such that probability of at least one hash collision ≥ p
2.8×1053
Number of hashed elements such that probability of at least one hash collision ≥ p
8.9×1054
Number of hashed elements such that probability of at least one hash collision ≥ p
2.8×1056
Number of hashed elements such that probability of at least one hash collision ≥ p
8.9×1056
Number of hashed elements such that probability of at least one hash collision ≥ p
4.8×1057
Number of hashed elements such that probability of at least one hash collision ≥ p
7.4×1057
Number of hashed elements such that probability of at least one hash collision ≥ p
1.0×1058
128
128
length of hex string
128
no. ofbits(b)
512
hash spacesize(2b)
1.3×10154
Number of hashed elements such that probability of at least one hash collision ≥ p
1.6×1068
Number of hashed elements such that probability of at least one hash collision ≥ p
5.2×1069
Number of hashed elements such that probability of at least one hash collision ≥ p
1.6×1071
Number of hashed elements such that probability of at least one hash collision ≥ p
5.2×1072
Number of hashed elements such that probability of at least one hash collision ≥ p
1.6×1074
Number of hashed elements such that probability of at least one hash collision ≥ p
5.2×1075
Number of hashed elements such that probability of at least one hash collision ≥ p
1.6×1076
Number of hashed elements such that probability of at least one hash collision ≥ p
8.8×1076
Number of hashed elements such that probability of at least one hash collision ≥ p
1.4×1077
Number of hashed elements such that probability of at least one hash collision ≥ p
1.9×1077
length of hex string
no. ofbits(b)
hash spacesize(2b)
Number of hashed elements such that probability of at least one hash collision ≥ p
p = 10−18
p = 10−15
p = 10−12
p = 10−9
p = 10−6
p = 0.001
p = 0.01
p = 0.25
p = 0.50
p = 0.75
8
32
4.3×109
2
2
2
2.9
93
2.9×103
9.3×103
5.0×104
7.7×104
1.1×105
(10)
(40)
(1.1×1012)
2
2
2
47
1.5×103
4.7×104
1.5×105
8.0×105
1.2×106
1.7×106
(12)
(48)
(2.8×1014)
2
2
24
7.5×102
2.4×104
7.5×105
2.4×106
1.3×107
2.0×107
2.8×107
16
64
1.8×1019
6.1
1.9×102
6.1×103
1.9×105
6.1×106
1.9×108
6.1×108
3.3×109
5.1×109
7.2×109
(24)
(96)
(7.9×1028)
4.0×105
1.3×107
4.0×108
1.3×1010
4.0×1011
1.3×1013
4.0×1013
2.1×1014
3.3×1014
4.7×1014
32
128
3.4×1038
2.6×1010
8.2×1011
2.6×1013
8.2×1014
2.6×1016
8.3×1017
2.6×1018
1.4×1019
2.2×1019
3.1×1019
(48)
(192)
(6.3×1057)
1.1×1020
3.5×1021
1.1×1023
3.5×1024
1.1×1026
3.5×1027
1.1×1028
6.0×1028
9.3×1028
1.3×1029
64
256
1.2×1077
4.8×1029
1.5×1031
4.8×1032
1.5×1034
4.8×1035
1.5×1037
4.8×1037
2.6×1038
4.0×1038
5.7×1038
(96)
(384)
(3.9×10115)
8.9×1048
2.8×1050
8.9×1051
2.8×1053
8.9×1054
2.8×1056
8.9×1056
4.8×1057
7.4×1057
1.0×1058
128
512
1.3×10154
1.6×1068
5.2×1069
1.6×1071
5.2×1072
1.6×1074
5.2×1075
1.6×1076
8.8×1076
1.4×1077
1.9×1077
n(d)
n(d)
d
n(d)
1–2
2
3–5
3
6–9
4
10–16
5
17–23
6
24–32
7
33–42
8
43–54
9
55–68
10
69–82
11
83–99
12
d
1–2
3–5
6–9
10–16
17–23
24–32
33–42
43–54
55–68
69–82
83–99
n(d)
2
3
4
5
6
7
8
9
10
11
12
0
0
k
0
nfor d = 365
23
1
1
k
1
nfor d = 365
14
2
2
k
2
nfor d = 365
11
3
3
k
3
nfor d = 365
9
4
4
k
4
nfor d = 365
8
5
5
k
5
nfor d = 365
8
6
6
k
6
nfor d = 365
7
7
7
k
7
nfor d = 365
7
k
nfor d = 365
0
23
1
14
2
11
3
9
4
8
5
8
6
7
7
7
0.01
0.01
p
0.01
n
0.14178√365 = 2.70864
n↓
2
p(n↓)
0.00274
n↑
3
p(n↑)
0.00820
0.05
0.05
p
0.05
n
0.32029√365 = 6.11916
n↓
6
p(n↓)
0.04046
n↑
7
p(n↑)
0.05624
0.1
0.1
p
0.1
n
0.45904√365 = 8.77002
n↓
8
p(n↓)
0.07434
n↑
9
p(n↑)
0.09462
0.2
0.2
p
0.2
n
0.66805√365 = 12.76302
n↓
12
p(n↓)
0.16702
n↑
13
p(n↑)
0.19441
0.3
0.3
p
0.3
n
0.84460√365 = 16.13607
n↓
16
p(n↓)
0.28360
n↑
17
p(n↑)
0.31501
0.5
0.5
p
0.5
n
1.17741√365 = 22.49439
n↓
22
p(n↓)
0.47570
n↑
23
p(n↑)
0.50730
0.7
0.7
p
0.7
n
1.55176√365 = 29.64625
n↓
29
p(n↓)
0.68097
n↑
30
p(n↑)
0.70632
0.8
0.8
p
0.8
n
1.79412√365 = 34.27666
n↓
34
p(n↓)
0.79532
n↑
35
p(n↑)
0.81438
0.9
0.9
p
0.9
n
2.14597√365 = 40.99862
n↓
40
p(n↓)
0.89123
n↑
41
p(n↑)
0.90315
0.95
0.95
p
0.95
n
2.44775√365 = 46.76414
n↓
46
p(n↓)
0.94825
n↑
47
p(n↑)
0.95477
0.99
0.99
p
0.99
n
3.03485√365 = 57.98081
n↓
57
p(n↓)
0.99012
n↑
58
p(n↑)
0.99166
p
n
n↓
p(n↓)
n↑
p(n↑)
0.01
0.14178√365 = 2.70864
2
0.00274
3
0.00820
0.05
0.32029√365 = 6.11916
6
0.04046
7
0.05624
0.1
0.45904√365 = 8.77002
8
0.07434
9
0.09462
0.2
0.66805√365 = 12.76302
12
0.16702
13
0.19441
0.3
0.84460√365 = 16.13607
16
0.28360
17
0.31501
0.5
1.17741√365 = 22.49439
22
0.47570
23
0.50730
0.7
1.55176√365 = 29.64625
29
0.68097
30
0.70632
0.8
1.79412√365 = 34.27666
34
0.79532
35
0.81438
0.9
2.14597√365 = 40.99862
40
0.89123
41
0.90315
0.95
2.44775√365 = 46.76414
46
0.94825
47
0.95477
0.99
3.03485√365 = 57.98081
57
0.99012
58
0.99166

References

  1. In his autobiography, Halmos criticized the form in which the birthday paradox is often presented, in terms of numerical
  2. David Singmaster, Sources in Recreational Mathematics: An Annotated Bibliography, Eighth Preliminary Edition, 2004, sect
    https://www.puzzlemuseum.com/singma/singma6/SOURCES/singma-sources-edn8-2004-03-19.htm#_Toc69534221
  3. H.S.M. Coxeter, "Mathematical Recreations and Essays, 11th edition", 1940, p 45, as reported in I. J. Good, Probability
    https://archive.org/details/probabilityweigh0000good/page/38/mode/2up?q=same%20birthday
  4. Selected Papers of Richard von Mises
  5. see Birthday#Distribution through the year
  6. (Bloom 1973)
  7. The Cauchy‑Schwarz Master Class
    https://archive.org/details/cauchyschwarzmas00stee_431
  8. Significance
    https://doi.org/10.1111%2Fj.1740-9713.2007.00246.x
  9. SIAM Review
    http://http.cs.berkeley.edu/~daw/papers/genbday-crypto02.ps
  10. Jim Gray, Catharine van Ingen. Empirical Measurements of Disk Failure Rates and Error Rates
    https://arxiv.org/abs/cs/0701166
  11. mw- .mw- D. Brink, A (probably) exact solution to the Birthday Problem, Ramanujan Journal, 2012, [1].
    https://link.springer.com/article/10.1007/s11139-011-9343-9
  12. Brink 2012, Theorem 2
  13. Brink 2012, Theorem 3
  14. Brink 2012, Table 3, Conjecture 1
  15. The On-line Encyclopedia of Integer Sequences
    https://oeis.org/A014088
  16. DasGupta, Anirban. "The matching, birthday and the strong birthday problem: a contemporary review." Journal of Statistic
  17. Mario Cortina Borja, The Strong Birthday Problem, Significance, Volume 10, Issue 6, December 2013, Pages 18–20, https://
    https://doi.org/10.1111/j.1740-9713.2013.00705.x
  18. Lecture Notes in Computer Science, vol 4296
    https://doi.org/10.1007%2F11927587_5
  19. Z. E. Schnabel (1938) The Estimation of the Total Fish Population of a Lake, American Mathematical Monthly 45, 348–352.
  20. M. Pollanen (2024) A Double Birthday Paradox in the Study of Coincidences, Mathematics 23(24), 3882. https://doi.org/10.
    https://doi.org/10.3390/math12243882
  21. M. C. Wendl (2003) Collision Probability Between Sets of Random Variables, Statistics and Probability Letters 64(3), 249
    https://dx.doi.org/10.1016/S0167-7152(03)00168-8
  22. M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
  23. Matt Might's blog
    http://matt.might.net/articles/counting-hash-collisions/
  24. Random Structures & Algorithms
  25. The Art of Computer Programming
  26. Journal of Computational and Applied Mathematics
    https://doi.org/10.1016%2F0377-0427%2893%29E0258-N
  27. Introduction to Algorithms
  28. bbc.com
    https://www.bbc.co.uk/news/magazine-27835311
  29. Perceptual and Motor Skills
    https://doi.org/10.2466%2Fpms.106.1.91-103
  30. Random Structures and Algorithms
    https://doi.org/10.1002%2Frsa.10004
Image
Source: —
Tip: Wheel or +/− to zoom, drag to pan, Esc to close.