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

DOI10.1002/rsa.20591zbMath1376.60017arXiv1310.7055OpenAlexW1581959878WikidataQ121640826 ScholiaQ121640826MaRDI QIDQ2811160

Richard Arratia, Joe Kilian, Skip Garibaldi

Publication date: 10 June 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.7055

zbMATH Keywords

collisionsbirthday problemsize biasurn problemchi distribution

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Strong limit theorems (60F15) Combinatorial probability (60C05)

Related Items

A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs ⋮ Normal approximation and fourth moment theorems for monochromatic triangles ⋮ Unnamed Item ⋮ Convergence to scale-invariant Poisson processes and applications in Dickman approximation ⋮ Asymptotics of the overflow in urn models

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Berry-Esseen bound for the uniform multinomial occupancy model
• Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior
• Concentration of measures via size-biased couplings
• Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
• A remainder term estimate for the normal approximation in classical occupancy
• Poisson approximation and the Chen-Stein method. With comments and a rejoinder by the authors
• On the Lambert \(w\) function
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Eigenvalue distributions of large Hermitian matrices; Wigner's semi- circle law and a theorem of Kac, Murdock, and Szegö
• Limiting Distributions in Some Occupancy Problems
• On Birthday, Collectors', Occupancy and Other Classical Urn Problems
• The general birthday problem
• Probability