Asymptotic Distribution for the Birthday Problem with Multiple Coincidences, via an Embedding of the Collision Process

作者：Arratia Richard; Garibaldi Skip^*; Kilian Joe

来源：Random Structures and Algorithms, 2016, 48(3): 480-502.

DOI：10.1002/rsa.20591

• birthday problem
• collisions
• Renyi
• urn problem
• size bias
• chi distribution

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 root 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).
We have two main tools: 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.

• 出版日期2016-5