On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem

Authors:
Rita Giuliano and Claudio Macci

Original publication:
Teoriya Imovirnostei ta Matematichna Statistika, tom **87** (2012).

Journal:
Theor. Probability and Math. Statist. **87** (2013), 31-40

MSC (2010):
Primary 60F10, 60C05

DOI:
https://doi.org/10.1090/S0094-9000-2014-00902-3

Published electronically:
March 21, 2014

MathSciNet review:
3241444

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In the classical occupancy problem one puts balls in boxes, and each ball is independently assigned to any fixed box with probability . It is well known that, if we consider the random number of balls required to have all the boxes filled with at least one ball, the sequence converges to 1 in probability. Here we present the large deviation principle associated to this convergence. We also discuss the use of the Gärtner Ellis Theorem for the proof of some parts of this large deviation principle.

**1.**A. D. Barbour, Lars Holst, and Svante Janson,*Poisson approximation*, Oxford Studies in Probability, vol. 2, The Clarendon Press, Oxford University Press, New York, 1992. Oxford Science Publications. MR**1163825****2.**Amir Dembo and Ofer Zeitouni,*Large deviations techniques and applications*, 2nd ed., Applications of Mathematics (New York), vol. 38, Springer-Verlag, New York, 1998. MR**1619036****3.**Paul Dupuis and Richard S. Ellis,*A weak convergence approach to the theory of large deviations*, Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1997. A Wiley-Interscience Publication. MR**1431744****4.**Paul Dupuis, Carl Nuzman, and Phil Whiting,*Large deviation asymptotics for occupancy problems*, Ann. Probab.**32**(2004), no. 3B, 2765–2818. MR**2078557**, https://doi.org/10.1214/009117904000000135**5.**Paul Dupuis, Carl Nuzman, and Phil Whiting,*Large deviations principle for occupancy problems with colored balls*, J. Appl. Probab.**44**(2007), no. 1, 115–141. MR**2312991**, https://doi.org/10.1239/jap/1175267167**6.**Paul Dupuis, Jim Zhang, and Philip Whiting,*Refined large deviation asymptotics for the classical occupancy problem*, Methodol. Comput. Appl. Probab.**8**(2006), no. 4, 467–496. MR**2329283**, https://doi.org/10.1007/s11009-006-0425-x**7.**Richard Durrett,*Probability: theory and examples*, 2nd ed., Duxbury Press, Belmont, CA, 1996. MR**1609153****8.**Norman L. Johnson and Samuel Kotz,*Urn models and their application*, John Wiley & Sons, New York-London-Sydney, 1977. An approach to modern discrete probability theory; Wiley Series in Probability and Mathematical Statistics. MR**0488211****9.**Hosam M. Mahmoud,*Pólya urn models*, Texts in Statistical Science Series, CRC Press, Boca Raton, FL, 2009. MR**2435823****10.**Michael Mitzenmacher and Eli Upfal,*Probability and computing*, Cambridge University Press, Cambridge, 2005. Randomized algorithms and probabilistic analysis. MR**2144605****11.**Rajeev Motwani and Prabhakar Raghavan,*Randomized algorithms*, Cambridge University Press, Cambridge, 1995. MR**1344451****12.**Adam Shwartz and Alan Weiss,*Large deviations for performance analysis*, Stochastic Modeling Series, Chapman & Hall, London, 1995. Queues, communications, and computing; With an appendix by Robert J. Vanderbei. MR**1335456****13.**Jim X. Zhang and Paul Dupuis,*Large-deviation approximations for general occupancy models*, Combin. Probab. Comput.**17**(2008), no. 3, 437–470. MR**2410397**, https://doi.org/10.1017/S0963548307008681

Retrieve articles in *Theory of Probability and Mathematical Statistics*
with MSC (2010):
60F10,
60C05

Retrieve articles in all journals with MSC (2010): 60F10, 60C05

Additional Information

**Rita Giuliano**

Affiliation:
Dipartimento di Matematica “L. Tonelli”, Università di Pisa, Largo Bruno Pontecorvo 5, I-56127 Pisa, Italy

Email:
giuliano@dm.unipi.it

**Claudio Macci**

Affiliation:
Dipartimento di Matematica, Università di Roma Tor Vergata, Via della Ricerca Scientifica, I-00133 Rome, Italy

Email:
macci@mat.uniroma2.it

DOI:
https://doi.org/10.1090/S0094-9000-2014-00902-3

Keywords:
Large deviation principle,
coupon collector's problem,
triangular array,
Poisson approximation

Received by editor(s):
December 13, 2011

Published electronically:
March 21, 2014

Additional Notes:
The financial support of the Research Grant PRIN 2008 Probability and Finance is gratefully acknowledged

The authors thank Francesco Pasquale for useful comments on the proof of \eqref{eq:UB} for $F∈\mathcal{C}_{2}$

Article copyright:
© Copyright 2014
American Mathematical Society