Bins and balls; Large deviations of the empirical occupancy process
Open Access
- 1 May 2002
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 12 (2), 607-636
- https://doi.org/10.1214/aoap/1026915618
Abstract
In the random allocation model, balls are sequentially inserted at random into $n$ exchangeable bins. The occupancy score of a bin denotes the number of balls inserted in this bin. The (random) distribution of occupancy scores defines the object of this paper: the empirical occupancy measure which is a probability measure over the integers. This measure-valued random variable packages many useful statistics. This paper characterizes the large deviations of the flow of empirical occupancy measures when $n$ goes to infinity while the number of inserted balls remains proportional to $n$. The main result is a Sanov-like theorem for the empirical occupancy measure when the set of probability measures over the integers is endowed with metrics that are slightly stronger than the total variation distance. Thanks to a coupling argument, this result applies to the degree distribution of sparse random graphs.
Keywords
This publication has 20 references indexed in Scilit:
- The degree sequence of a random graph. I. The modelsRandom Structures & Algorithms, 1997
- An urn model from learning theoryRandom Structures & Algorithms, 1997
- On large deviations for particle systems associated with spatially homogeneous Boltzmann type equationsProbability Theory and Related Fields, 1995
- Almost all graphs with 1.44n edges are 3‐colorableRandom Structures & Algorithms, 1991
- Normal Approximations to Sums of Scores Based on Occupancy NumbersThe Annals of Probability, 1984
- On the number of vertices of given degree in a random graphJournal of Graph Theory, 1984
- A Berry-Esseen Bound for an Occupancy ProblemThe Annals of Probability, 1982
- Urn Models and Their Application: An Approach to Modern Discrete Probability Theory.Published by JSTOR ,1978
- Integrals which are convex functionalsPacific Journal of Mathematics, 1968
- On general minimax theoremsPacific Journal of Mathematics, 1958