Bernoulli numbers and the probability of a birthday surprise

Boaz Tsaban

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 paradox arbitrary precision calculators
Contact author(s): tsaban @ math huji ac il
History: 2003-07-17: received
Short URL: https://ia.cr/2003/137
License: 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},
      url = {https://eprint.iacr.org/2003/137}
}