Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process1. Issue 3 (6th July 2015)

• Record Type: Journal Article
• Authors: Arratia, Richard; Garibaldi, Skip; Kilian, Joe
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 480
• Page End: 502
• Publication Date: 2015-07-06
• Subjects: birthday problem -- collisions -- Renyi -- urn problem -- size bias -- chi distribution; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20591
• Languages: English
• ISSNs: 1042-9832

Abstract

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 n π / 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 ∞ 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 Rényi. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 480–502, 2016