Bernoulli numbers and the probability of a birthday surprise
arXiv:math/0304028 · doi:10.1016/S0166-218X(02)00396-7
Abstract
A birthday surprise is the event that, given k uniformly random samples from a sample space of size n, at least two of them are identical. We show that Bernoulli numbers can be used to derive arbitrarily exact bounds on the probability of a birthday surprise. This result can be used in arbitrary precision calculators, and it can be applied to better understand some questions in communication security and pseudorandom number generation.
Small updates