A note on the exponentiation approximation of the birthday paradox

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.