×

Bins and balls: Large deviations of the empirical occupancy process. (English) Zbl 1013.60017

Summary: 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.

MSC:

60F10 Large deviations
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] BARBOUR, A., HOLST, L. and JANSON, S. (1992). Poisson Approximation. Clarendon Press, London. · Zbl 0765.60015 · doi:10.1214/aop/1176989531
[2] BARTLETT, M. S. (1938). The characteristic function of a conditional statistic. J. London Math. Soc. 13 62-67. · Zbl 0018.22503 · doi:10.1112/jlms/s1-13.1.62
[3] BOLLOBÀS, B. (1985). Random Graphs. Academic Press, New York. · Zbl 0567.05042
[4] BOLLOBÀS, B. and FRIEZE, A. M. (1985). On matching and Hamiltonian cy cles in random graphs. In Random Graphs 83. Annals of Discrete Mathematics 28 23-46.
[5] BOUCHERON, S. and GARDY, D. (1997). An urn model from learning theory. Random Structures Algorithms 10 43-67. · Zbl 0872.60005
[6] CHVATAL, V. (1991). Almost all graphs with 1.44 edges are 3 colourable. Random Structures Algorithms 2 11-28. · Zbl 0715.05026 · doi:10.1002/rsa.3240020103
[7] DEMBO, A., VERSHIK, A. and ZEITOUNI, O. (2000). Large deviations for integer partitions. Markov Process. Related Fields 6 147-179. · Zbl 0972.60006
[8] DEMBO, A. and ZEITOUNI, O. (1999). Large Deviation Techniques and Applications. Springer, New York.
[9] ETHIER, S. and KURTZ, T. G. (1986). Markov Processes, Characterization and Convergence. Wiley, New York. · Zbl 0592.60049
[10] FELLER, W. (1968). Probability Theory. Wiley, New York. · Zbl 0155.23101
[11] GILES, J. R. (1992). Convex analysis with application in the differentiation of convex functions. In Research Notes in Math. 58. Pitman, London.
[12] JOHNSON, N. L. and KOTZ, S. (1977). Urn Models and Their Application. An Approach to Modern Discrete Probability Theory. Wiley, New York. · Zbl 0352.60001
[13] KOLCIN, V. F., SEVAST’JANOV, B. A. and CISTJAKOV, V. P. (1978). Random Allocations. Wiley, New York.
[14] LÉONARD, C. (1995). Large deviations for particle sy stems associated with spatially homogeneous Boltzmann ty pe equations. Probab. Theory Related Fields 101 1-44. · Zbl 0839.60031 · doi:10.1007/BF01192194
[15] LÉONARD, C. (2000). Minimizers of energy functionals under not very integrable constraints.
[16] LÉONARD, C. and NAJIM, J. (2000). An extension of Sanov’s theorem. Application to the Gibbs conditioning principle.
[17] MCKAY, B. D. and WORMALD, N. C. (1998). The degree sequence of a random graph. Random Structures Algorithms 11 97-117. · Zbl 0884.05081 · doi:10.1002/(SICI)1098-2418(199709)11:2<97::AID-RSA1>3.0.CO;2-O
[18] MORRIS, C. (1975). Central Limit Theorems for multinomial sums. Ann. Statist. 3 165-168. · Zbl 0305.62013 · doi:10.1214/aos/1176343006
[19] PALKA, Z. (1984). On the number of vertices of given degree in a random graph. J. Graph Theory 8 267-270. · Zbl 0532.05052 · doi:10.1002/jgt.3190080119
[20] PITTEL, B., SPENCER, J. and WORMALD, N. (1996). Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 111-151. · Zbl 0860.05065 · doi:10.1006/jctb.1996.0036
[21] QUINE, M. P. (1979). A functional Central Limit Theorem for generalized occupancy numbers. Stochastic Process. Appl. 9 109-115. · Zbl 0414.60039 · doi:10.1016/0304-4149(79)90044-9
[22] QUINE, M. P. and ROBINSON, J. (1982). A Berry-Essen bound for an occupancy problem. Ann. Probab. 10 663-671. · Zbl 0493.60034 · doi:10.1214/aop/1176993775
[23] QUINE, M. P. and ROBINSON, J. (1984). Normal approximations to sums of scores based on occupancy numbers. Ann. Probab. 12 794-804. · Zbl 0584.60031 · doi:10.1214/aop/1176993228
[24] RAO, R. and REN, R. (1991). Theory of Orlicz Spaces. Marcel Dekker, New York. · Zbl 0724.46032
[25] ROCKAFELLAR, R. T. (1968). Integrals which are convex functionals. Pacific J. Math. 24 525- 538. · Zbl 0159.43804 · doi:10.2140/pjm.1968.24.525
[26] SION, M. (1958). On general Minimax theorems. Pacific J. Math. 8 171-176. · Zbl 0081.11502 · doi:10.2140/pjm.1958.8.171
[27] VARADHAN, S. R. S. (1984). Large Deviations and Applications. SIAM, Philadelphia. · Zbl 0549.60023
[28] VITTER, J. S. and FLAJOLET, P. (1990). Average-case analysis of algorithms and data structures. In Handbook of Theoretical Computer Science A (J. Van Leeuwen, ed.) 431- 524. Elsevier, Amsterdam. · Zbl 0900.68251
[29] AND ECOLE POLy TECHNIQUE, CMAP 91128 PALAISEAU FRANCE E-MAIL: christian.leonard@u-paris10.fr
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.