Normal Approximation for Isolated Balls in an Urn Allocation Model
Abstract
Consider throwing $n$ balls at random into $m$ urns, each ball landing in urn $i$ with probability $p(i)$. Let $S$ be the resulting number of singletons, i.e., urns containing just one ball. We give an error bound for the Kolmogorov distance from the distribution of $S$ to the normal, and estimates on its variance. These show that if $n$, $m$ and $(p(i))$ vary in such a way that $n p(i)$ remains bounded uniformly in $n$ and $i$, then $S$ satisfies a CLT if and only if ($n$ squared) times the sum of the squares of the entries $p(i)$ tends to infinity, and demonstrate an optimal rate of convergence in the CLT in this case. In the uniform case with all $p(i)$ equal and with $m$ and $n$ growing proportionately, we provide bounds with better asymptotic constants. The proof of the error bounds is based on Stein's method via size-biased couplings.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 2155-2181
Publication Date: October 6, 2009
DOI: 10.1214/EJP.v14-699
References
- A. D. Barbour and A. V. Gnedin. Small counts in the infinite occupancy scheme. Electron. J. Probab. 14 (2009), 365-384. Math. Review MR2480545
- A. D. Barbour, L. Holst and S. Janson. Poisson Approximation. (1992) Oxford University Press, New York. Math. Review 93g:60043
- S. Chatterjee. A new method of normal approximation. Ann. Probab. 36 (2008), 1584-1610. Math. Review 2009j:60043
- G. Englund. A remainder term estimate for the normal approximation in classical occupancy. Ann. Probab. 9 (1981), 684-692. Math. Review 82j:60015
- W. Feller. An Introduction to Probability Theory and its Applications. Vol. I. 3rd ed. (1968) John Wiley and Sons, New York. Math. Review MR0228020
- A. Gnedin, B. Hansen and J. Pitman. Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. Probab. Surv. 4 (2007), 146-171. Math. Review 2008g:60056
- L. Goldstein and M. D. Penrose (2008). Normal approximation for coverage models over binomial point processes. To appear in Ann. Appl. Probab. Math. Review number not available.
- H.-K. Hwang and S. Janson. Local limit theorems for finite and infinite urn models. Ann. Probab. 36 (2008), 992-1022. Math. Review 2009f:60032
- N. L. Johnson and S. Kotz. Urn Models and their Application: An approach to Modern Discrete Probability Theory. (1977) John Wiley and Sons, New York. Math. Review MR0488211
- V. F. Kolchin, B.A. Sevast'yanov and V. P. Chistyakov Random Allocations. (1978) Winston, Washington D.C. Math. Review MR0471015
- Mikhailov, V. G. The central limit theorem for a scheme of independent allocation of particles by cells. (Russian) Number theory, mathematical analysis and their applications. Trudy Mat. Inst. Steklov. 157 (1981), 138-152. Math. Review 83f:60022
- Quine, M. P. and Robinson, J. A Berry-Esseen bound for an occupancy problem. Ann. Probab. 10 (1982), 663-671. Math. Review 83i:60027
- Quine, M. P. and Robinson, J. Normal approximations to sums of scores based on occupancy numbers. Ann. Probab. 12 (1984), 794-804. Math. Review 85h:60035
- Steele, J. M. An Efron-Stein inequality for non-symmetric statistics. Ann. Statist. 14 (1986), 753-758. Math. Review 87m:60050
- Vatutin, V. A. and Mikhailov, V. G. Limit theorems for the number of empty cells in an equiprobable scheme for the distribution of particles by groups. Theory Probab. Appl. 27 (1982), 734-743. Math. Review 84c:60020

This work is licensed under a Creative Commons Attribution 3.0 License.