Paper 2003/137

Bernoulli numbers and the probability of a birthday surprise

Boaz Tsaban

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.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Discrete Applied Mathematics 127(3) (2003), 657--663
Keywords
birthday paradoxarbitrary precision calculators
Contact author(s)
tsaban @ math huji ac il
History
2003-07-17: received
Short URL
https://ia.cr/2003/137
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/137,
      author = {Boaz Tsaban},
      title = {Bernoulli numbers and the probability of a birthday surprise},
      howpublished = {Cryptology ePrint Archive, Paper 2003/137},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/137}},
      url = {https://eprint.iacr.org/2003/137}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.