×

Local limit theorems for finite and infinite urn models. (English) Zbl 1138.60027

Summary: Local limit theorems are derived for the number of occupied urns in general finite and infinite urn models under the minimum condition that the variance tends to infinity. Our results represent an optimal improvement over previous ones for normal approximation.

MSC:

60F05 Central limit and other weak theorems
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aldous, D. (1989). Probability Approximations via the Poisson Clumping Heuristic . Springer, New York. · Zbl 0679.60013
[2] Bahadur, R. R. (1960). On the number of distinct values in a large sample from an infinite discrete distribution. Proc. Nat. Inst. Sci. India Part A 26 supplement II 67-75. · Zbl 0151.23803
[3] Barbour, A., Holst, L. and Janson, S. (1992). Poisson Approximation . Oxford Univ. Press. · Zbl 0746.60002
[4] Berndt, B. C. (1985). Ramanujan ’ s Notebooks. Part I. Springer, New York. · Zbl 0555.10001
[5] Bogachev, L. V., Gnedin, A. V. and Yakubovich, Yu. V. (2006). On the variance of the number of occupied boxes. Available at · Zbl 1181.60014
[6] Chistyakov, V. P. (1967). Discrete limit distributions in the problem of balls falling in cells with arbitrary probabilities. Mat. Zametki 1 9-16 (in Russian); translated as Math. Notes 1 6-11. · Zbl 0184.21404
[7] Darling, D. A. (1967). Some limit theorems associated with multinomial trials. Proc. Fifth Berkeley Sympos. Math. Statist. Probab. ( Berkeley , CA , 1965/66 ) II . Contributions to Probability Theory , Part 1 345-350. Univ. California Press, Berkeley, CA. · Zbl 0201.50801
[8] Dutko, M. (1989). Central limit theorems for infinite urn models. Ann. Probab. 17 1255-1263. · Zbl 0685.60023
[9] Englund, G. (1981). A remainder term estimate for the normal approximation in classical occupancy. Ann. Probab. 9 684-692. · Zbl 0464.60025
[10] Flajolet, P., Gardy, D. and Thimonier, L. (1992). Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39 207-229. · Zbl 0762.60006
[11] Gnedin, A., Hansen, B. and Pitman, J. (2007). Notes on the occupancy problem with infinitely many boxes: General asymptotics and power laws. Probab. Surveys 4 146-171. · Zbl 1189.60050
[12] Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for compositions derived from transformed subordinators. Ann. Probab. 34 468-492. · Zbl 1142.60327
[13] Hitczenko, P. and Louchard, G. (2001). Distinctness of compositions of an integer: A probabilistic analysis. Random Structures Algorithms 19 407-437. · Zbl 1014.05008
[14] Hodges, J. L. Jr. and Le Cam, L. (1960). The Poisson approximation to the Poisson binomial distribution. Ann. Math. Statist. 31 737-740. · Zbl 0100.14301
[15] Holst, L. (1971). Limit theorems for some occupancy and sequential occupancy problems. Ann. Math. Statist. 42 1671-1680. · Zbl 0231.60022
[16] Hwang, H.-K. and Yeh, Y.-N. (1997). Measures of distinctness for random partitions and compositions of an integer. Adv. in Appl. Math. 19 378-414. · Zbl 0943.05009
[17] Jacquet, P. and Szpankowski, W. (1998). Analytical depoissonization and its applications. Theoret. Comput. Sci. 201 1-62. · Zbl 0902.68087
[18] Janson, S. (2006). Rounding of continuous random variables and oscillatory asymptotics. Ann. Probab. 34 1807-1826. · Zbl 1113.60017
[19] Johnson, N. L. and Kotz S. (1977). Urn Models and Their Application. An Approach to Modern Discrete Probability Theory . Wiley, New York. · Zbl 0352.60001
[20] Karlin, S. (1967). Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17 373-401. · Zbl 0154.43701
[21] Kesten, H. (1968). Review of Darling. Some limit theorems associated with multinomial trials. Math. Reviews 35 #7378.
[22] Kolchin, V. F. (1967). Uniform local limit theorems in the classical ball problem for a case with varying lattices. Theory Probab. Appl. 12 57-67. · Zbl 0164.48401
[23] Kolchin, V. F., Sevast’yanov, B. A. and Chistyakov, V. P. (1976). Random Allocations . Nauka, Moscow. (In Russian.) English translation published by V. H. Winston & Sons, Washington, DC (1978). · Zbl 0464.60002
[24] Kotz, S. and Balakrishnan, N. (1997). Advances in urn models during the past two decades. In Advances in Combinatorial Methods and Applications to Probability and Statistics 203-257. Birkhäuser, Boston, MA. · Zbl 0888.60014
[25] Le Cam, L. (1960). An approximation theorem for the Poisson binomial distribution. Pacific J. Math. 10 1181-1197. · Zbl 0118.33601
[26] Prodinger, H. (2004). Periodic oscillations in the analysis of algorithms. J. Iranian Stat. Soc. 3 251-270. · Zbl 1491.68279
[27] Quine, M. P. and Robinson, J. (1982). A Berry-Esseen bound for an occupancy problem. Ann. Probab. 10 663-671. · Zbl 0493.60034
[28] Rais, B., Jacquet, P. and Szpankowski, W. (1993). Limiting distribution for the depth in PATRICIA tries. SIAM J. Discrete Math. 6 197-213. · Zbl 0798.68067
[29] Rényi, A. (1962). Three new proofs and a generalization of a theorem of Irving Weiss. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 203-214; also in Selected Papers of Alfréd Rényi III 1962-1970 (1976) (P. Turán, ed.) 195-213. Akadémiai Kiadó, Budapest.
[30] Sevast’yanov, B. A. and Chistyakov, V. P. (1964). Asymptotic normality in the classical ball problem. Theory Probab. Appl. 9 198-211; see also Letter to the Editors, ibid. , 513-514. · Zbl 0142.14704
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.