On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem. (English. Ukrainian original) Zbl 1329.60052
Theory Probab. Math. Stat. 87, 31-40 (2013); translation from Teor. Jmovirn. Mat. Stat. 87, 28-37 (2012).
Summary: 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): 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.
MSC:
| 60F10 | Large deviations |
| 60F05 | Central limit and other weak theorems |
| 60C05 | Combinatorial probability |
| 60G55 | Point processes (e.g., Poisson, Cox, Hawkes processes) |
Keywords:
occupancy problem; large deviations principle; coupon collector problem; triangular array; Poisson approximationReferences:
| [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. · Zbl 0746.60002 |
| [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. · Zbl 0896.60013 |
| [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. · Zbl 0904.60001 |
| [4] | Paul Dupuis, Carl Nuzman, and Phil Whiting, Large deviation asymptotics for occupancy problems, Ann. Probab. 32 (2004), no. 3B, 2765 – 2818. · Zbl 1057.60023 · doi: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. · Zbl 1142.60017 · doi: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. · Zbl 1106.60035 · doi:10.1007/s11009-006-0425-x |
| [7] | Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. · Zbl 0709.60002 |
| [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. · Zbl 0352.60001 |
| [9] | Hosam M. Mahmoud, Pólya urn models, Texts in Statistical Science Series, CRC Press, Boca Raton, FL, 2009. · Zbl 1149.60005 |
| [10] | Michael Mitzenmacher and Eli Upfal, Probability and computing, Cambridge University Press, Cambridge, 2005. Randomized algorithms and probabilistic analysis. · Zbl 1092.60001 |
| [11] | Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995. · Zbl 0849.68039 |
| [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. · Zbl 0871.60021 |
| [13] | Jim X. Zhang and Paul Dupuis, Large-deviation approximations for general occupancy models, Combin. Probab. Comput. 17 (2008), no. 3, 437 – 470. · Zbl 1218.60023 · doi:10.1017/S0963548307008681 |
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.
