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.
Publié le : 2002-05-14
Classification:
Random graphs,
large deviations,
occupancy,
Orlicz spaces,
Sanov theorem,
Poisson approximation,
60F10,
05A17,
05C40,
05C80,
05A99
@article{1026915618,
author = {Boucheron, St\'ephane and Gamboa, Fabrice and L\'eonard, Christian},
title = {Bins and balls; Large deviations of the empirical occupancy process},
journal = {Ann. Appl. Probab.},
volume = {12},
number = {1},
year = {2002},
pages = { 607-636},
language = {en},
url = {http://dml.mathdoc.fr/item/1026915618}
}
Boucheron, Stéphane; Gamboa, Fabrice; Léonard, Christian. Bins and balls; Large deviations of the empirical occupancy process. Ann. Appl. Probab., Tome 12 (2002) no. 1, pp. 607-636. http://gdmltest.u-ga.fr/item/1026915618/