A Berry-Esseen bound for the uniform multinomial occupancy model

Jay Bartroff (University of Southern California)
Larry Goldstein (University of Southern California)


The inductive size bias coupling technique and Stein's method yield a Berry-Esseen theorem for the number of urns having occupancy $d \geq 2$ when $n$ balls are uniformly distributed over $m$ urns. In particular, there exists a constant $C$ depending only on $d$ such that$$\sup_{z \in \mathbb{R}}\left|P\left( W_{n,m} \le z \right) -P(Z \le z)\right| \le C \frac{\sigma_{n,m}}{1+(\frac{n}{m})^3} \quad\mbox{for all $n \ge d$ and $m \ge 2$,}$$where $W_{n,m}$ and $\sigma_{n,m}^2$ are the standardized count and variance, respectively, of the number of urns with $d$ balls, and $Z$ is a standard normal random variable. Asymptotically, the bound is optimal up to constants if $n$ and $m$ tend to infinity together in a way such that $n/m$ stays bounded.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-29

Publication Date: February 17, 2013

DOI: 10.1214/EJP.v18-1983


  • Baldi, P.; Rinott, Y.; Stein, C. A normal approximation for the number of local maxima of a random function on a graph. Probability, statistics, and mathematics, 59--81, Academic Press, Boston, MA, 1989. MR1031278
  • Barbour, A. D.; Gnedin, A. V. Small counts in the infinite occupancy scheme. Electron. J. Probab. 14 (2009), no. 13, 365--384. MR2480545
  • Barbour, A. D.; Holst, Lars; Janson, Svante. Poisson approximation. Oxford Studies in Probability, 2. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992. x+277 pp. ISBN: 0-19-852235-5 MR1163825
  • Barbour, A. D.; Karoński, Michał; Ruciński, Andrzej. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B 47 (1989), no. 2, 125--145. MR1047781
  • Bollobás, Béla. Random graphs. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. xvi+447 pp. ISBN: 0-12-111755-3; 0-12-111756-1 MR0809996
  • Bolthausen, E. An estimate of the remainder in a combinatorial central limit theorem. Z. Wahrsch. Verw. Gebiete 66 (1984), no. 3, 379--386. MR0751577
  • Chao, Anne; Yip, Paul; Lin, Huey-Shyan. Estimating the number of species via a martingale estimating function. Statist. Sinica 6 (1996), no. 2, 403--418. MR1399311
  • Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2010). Normal approximation by Stein's method. Springer Verlag.
  • Chen, Louis H. Y.; Shao, Qi-Man. Normal approximation under local dependence. Ann. Probab. 32 (2004), no. 3A, 1985--2028. MR2073183
  • Chen, L.H. Y. and Röllin, A. (2010). Stein couplings for Normal Approximation. Preprint http://arxiv.org/abs/1003.6039
  • Efron, B.; Stein, C. The jackknife estimate of variance. Ann. Statist. 9 (1981), no. 3, 586--596. MR0615434
  • Efron, B. and Thisted, R. (1976). Estimating the Number of Unseen Species: How Many Words Did Shakespeare Know? phBiometrika 63: 435--448.
  • Englund, Gunnar. A remainder term estimate for the normal approximation in classical occupancy. Ann. Probab. 9 (1981), no. 4, 684--692. MR0624696
  • Erdős, P.; Rényi, A. On random graphs. I. Publ. Math. Debrecen 6 1959 290--297. MR0120167
  • Gnedin, Alexander; Hansen, Ben; Pitman, Jim. Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. Probab. Surv. 4 (2007), 146--171. MR2318403
  • Goldstein, Larry. Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing. J. Appl. Probab. 42 (2005), no. 3, 661--683. MR2157512
  • Goldstein, L. (2012). A Berry-Esseen bound with applications to vertex degree counts in the Erdös-Rényi random graph Ann. Appl. Probab. to appear
  • Goldstein, Larry; Penrose, Mathew D. Normal approximation for coverage models over binomial point processes. Ann. Appl. Probab. 20 (2010), no. 2, 696--721. MR2650046
  • Goldstein, Larry; Reinert, Gesine. Zero biasing in one and higher dimensions, and applications. Stein's method and applications, 1--18, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., 5, Singapore Univ. Press, Singapore, 2005. MR2201883
  • Goldstein, Larry; Rinott, Yosef. Multivariate normal approximations by Stein's method and size bias couplings. J. Appl. Probab. 33 (1996), no. 1, 1--17. MR1371949
  • Goldstein, Larry; Zhang, Haimeng. A Berry-Esseen bound for the lightbulb process. Adv. in Appl. Probab. 43 (2011), no. 3, 875--898. MR2858224
  • Hoeffding, Wassily. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 1963 13--30. MR0144363
  • Hwang, Hsien-Kuei; Janson, Svante. Local limit theorems for finite and infinite urn models. Ann. Probab. 36 (2008), no. 3, 992--1022. MR2408581
  • Janson, Svante; Nowicki, Krzysztof. The asymptotic distributions of generalized $U$-statistics with applications to random graphs. Probab. Theory Related Fields 90 (1991), no. 3, 341--375. MR1133371
  • Johnson, Norman L.; Kotz, Samuel. Urn models and their application. An approach to modern discrete probability theory. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, 1977. xiii+402 pp. MR0488211
  • Karlin, Samuel. Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17 1967 373--401. MR0216548
  • Karoński, Michał; Ruciński, Andrzej. Poisson convergence and semi-induced properties of random graphs. Math. Proc. Cambridge Philos. Soc. 101 (1987), no. 2, 291--300. MR0870602
  • Kolchin, Valentin F.; Sevastʹyanov, Boris A.; Chistyakov, Vladimir P. Random allocations. Translated from the Russian. Translation edited by A. V. Balakrishnan. Scripta Series in Mathematics. V. H. Winston & Sons, Washington, D.C.; distributed by Halsted Press [John Wiley & Sons], New York-Toronto, Ont.-London, 1978. xi+262 pp. ISBN: 0-470-99394-4 MR0471016
  • Kordecki, Wojciech. Normal approximation and isolated vertices in random graphs. Random graphs '87 (Poznań, 1987), 131--139, Wiley, Chichester, 1990. MR1094128
  • Palka, Zbigniew. On the number of vertices of given degree in a random graph. J. Graph Theory 8 (1984), no. 1, 167--170. MR0732030
  • Penrose, Mathew D. Normal approximation for isolated balls in an urn allocation model. Electron. J. Probab. 14 (2009), no. 74, 2156--2181. MR2550296
  • Quine, M. P.; Robinson, J. Normal approximations to sums of scores based on occupancy numbers. Ann. Probab. 12 (1984), no. 3, 794--804. MR0744234
  • Riordan, J. (1937) Moment Recurrence Relations for Binomial, Poisson and Hypergeometric Frequency Distributions Ann. Math. Statist. 8(2):103--111.
  • Robbins, Herbert E. Estimating the total probability of the unobserved outcomes of an experiment. Ann. Math. Statist. 39 1968 256--257. MR0221695
  • Starr, Norman. Linear estimation of the probability of discovering a new species. Ann. Statist. 7 (1979), no. 3, 644--652. MR0527498
  • Stein, Charles. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory, pp. 583--602. Univ. California Press, Berkeley, Calif., 1972. MR0402873
  • Stein, Charles. Approximate computation of expectations. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986. iv+164 pp. ISBN: 0-940600-08-0 MR0882007
  • Thisted, Ronald; Efron, Bradley. Did Shakespeare write a newly-discovered poem? Biometrika 74 (1987), no. 3, 445--455. MR0909350

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