Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process

Abstract

We study the random variable B(c,n), which counts the number of balls that must be thrown into n equally-sized bins in order to obtain c collisions. The asymptotic expected value of B(1,n) is the well-known $\sqrt{n\pi /2}$ appearing in the solution to the birthday problem; the limit distribution and asymptotic moments of B(1,n) are also well known. We calculate the distribution and moments of B(c,n) asymptotically as n goes to infinity and c = O(n). Our main tools are an embedding of the collision process, realizing the process as a deterministic function of the standard Poisson process, and a central limit result by Renyi.

References in corpus (3)

• Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
• A Berry-Esseen bound for the uniform multinomial occupancy model
• Bounded size bias coupling: a Gamma function bound, and universal Dickman-function behavior

Cited by in corpus (3)

• A fourth moment phenomenon for asymptotic normality of monochromatic subgraphs
• Bounded size bias coupling: a Gamma function bound, and universal Dickman-function behavior
• Counting birthday collisions using partitions