A note on the exponentiation approximation of the birthday paradox

Abstract

This note sheds new light on the exponentiation approximation of the probability that all K individuals have distinct birthdays across N calendar days. The exponentiation approximation imposes a pairwise independence assumption, which does not hold in general. We sidestep this assumption by deriving the conditional probability for each pair of individuals to have distinct birthdays given that previous pairs do. An interesting implication is that the conditional probability decreases in a step-function form—not in a strictly monotonical form—as more pairs are restricted to have distinct birthdays. The source of the step-function structure is identified and illustrated. We also establish the equivalence between the pairwise approach and another common approach based on permutations of all individuals.

KEYWORDS:

• Birthday problem
• collision
• pairwise approach
• permutation approach
• probability

MSC 2010 Classification Codes:

• 97K50
• 60-01
• 65C50

Acknowledgements

We thank John W. Dennis, Shigeyuki Hamori, Marcela Parada-Contzen, Yuki Sugimoto, Yuto Tada, Zheng Zhang, and seminar participants at Kobe University for helpful comments and discussions.

Disclosure statement

The authors declare that there are no competing interests.