On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem
Authors:
Rita Giuliano and Claudio Macci
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 $n$ boxes, and each ball is independently assigned to any fixed box with probability $\frac {1}{n}$. It is well known that, if we consider the random number $T_n$ of balls required to have all the $n$ boxes filled with at least one ball, the sequence $\{T_n/(n\log n)\colon n\geq 2\}$ 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.
References
- 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
- 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
- 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
- Paul Dupuis, Carl Nuzman, and Phil Whiting, Large deviation asymptotics for occupancy problems, Ann. Probab. 32 (2004), no. 3B, 2765–2818. MR 2078557, DOI https://doi.org/10.1214/009117904000000135
- 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, DOI https://doi.org/10.1239/jap/1175267167
- 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, DOI https://doi.org/10.1007/s11009-006-0425-x
- Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. MR 1609153
- 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
- Hosam M. Mahmoud, Pólya urn models, Texts in Statistical Science Series, CRC Press, Boca Raton, FL, [2009] ©2009. MR 2435823
- Michael Mitzenmacher and Eli Upfal, Probability and computing, Cambridge University Press, Cambridge, 2005. Randomized algorithms and probabilistic analysis. MR 2144605
- Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995. MR 1344451
- 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
- Jim X. Zhang and Paul Dupuis, Large-deviation approximations for general occupancy models, Combin. Probab. Comput. 17 (2008), no. 3, 437–470. MR 2410397, DOI https://doi.org/10.1017/S0963548307008681
References
- A. D. Barbour, L. Holst, and S. Janson, Poisson Approximation, The Clarendon Press–Oxford University Press, New York, 1992. MR 1163825 (93g:60043)
- A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Second Edition, Springer-Verlag, New York, 1998. MR 1619036 (99d:60030)
- P. Dupuis and R. S. Ellis, A Weak Convergence Approach to the Theory of Large Deviations, Wiley, New York, 1997. MR 1431744 (99f:60057)
- P. Dupuis, C. Nuzman, and P. Whiting, Large deviation asymptotics for occupancy problems, Ann. Probab. 32 (2004), 2765–2818. MR 2078557 (2005f:60066)
- P. Dupuis, C. Nuzman, and P. Whiting, Large deviations principle for occupancy problems with colored balls, J. Appl. Probab. 44 (2007), 115–141. MR 2312991 (2008e:60056)
- P. Dupuis, J. Zhang, and P. Whiting, Refined large deviation asymptotics for the classical occupancy problem, Methodol. Comput. Appl. Probab. 8 (2006), 467–496. MR 2329283 (2009c:60054)
- R. Durrett, Probability: Theory and Examples, Second Edition, Duxbury Press, Belmont, California, 1996. MR 1609153 (98m:60001)
- N. L. Johnson and S. Kotz, Urn Models and Their Applications, John Wiley & Sons, New York, 1977. MR 0488211 (58:7773)
- H. M. Mahmoud, Polya Urns Models, CRC Press, Boca Raton, 2009. MR 2435823 (2009m:60002)
- M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge University Press, Cambridge, 2005. MR 2144605 (2006d:68002)
- R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995. MR 1344451 (96i:65003)
- A. Shwartz and A. Weiss, Large Deviations for Performance Analysis, Chapman & Hall, London, 1995. MR 1335456 (96i:60029)
- J. X. Zhang and P. Dupuis, Large-deviation approximations for general occupancy models, \text{Combin. Probab. Comput.} 17 (2008), 437–470. MR 2410397 (2009e:60062)
Similar Articles
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
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\in \mathcal {C}_2$
Article copyright:
© Copyright 2014
American Mathematical Society
