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 Free Access
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