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 $S$ to the normal, and estimates on its variance. These show that if $n$, $m$ and $(p_i,1\le i\le m)$ vary in such a way that ${\sup }_i{p}_i=O(n^{-1})$, then $S$ satisfies a CLT if and only if $n^2{\sum }_i{p}_i^2$ tends to infinity, and demonstrate an optimal rate of convergence in the CLT in this case. In the uniform case $(p_i\equiv m^{-1})with$m$and$n$ growing proportionately, we provide bounds with better asymptotic constants. The proof of the error bounds are based on Stein's method via size-biased couplings.

32 Pages

References in corpus (2)

• A new method of normal approximation
• Small counts in the infinite occupancy scheme