Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / birthday paradox, arbitrary precision calculators

Publication Info: Discrete Applied Mathematics 127(3) (2003), 657--663

Date: received 16 Jul 2003

Contact author: tsaban at math huji ac il

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20030717:170552 (All versions of this report)

Discussion forum: Show discussion | Start new discussion