Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-11T10:09:57.896Z Has data issue: false hasContentIssue false
  • English
  • Français

Approaching the coupon collector’s problem with group drawings via Stein’s method

Part of: Limit theorems Combinatorial probability

Published online by Cambridge University Press:  25 April 2023

Carina Betken  and
Christoph Thäle
Carina Betken*
Affiliation:
Ruhr University Bochum
Christoph Thäle*
Affiliation:
Ruhr University Bochum
*
*Postal address: Faculty of Mathematics, Ruhr University Bochum, 44780 Bochum, Germany.
*Postal address: Faculty of Mathematics, Ruhr University Bochum, 44780 Bochum, Germany.
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the coupon collector’s problem with group drawings. Assume there are n different coupons. At each time precisely s of the n coupons are drawn, where all choices are supposed to have equal probability. The focus lies on the fluctuations, as $n\to\infty$, of the number $Z_{n,s}(k_n)$ of coupons that have not been drawn in the first $k_n$ drawings. Using a size-biased coupling construction together with Stein’s method for normal approximation, a quantitative central limit theorem for $Z_{n,s}(k_n)$ is shown for the case that $k_n=({n/s})(\alpha\log(n)+x)$, where $0<\alpha<1$ and $x\in\mathbb{R}$. The same coupling construction is used to retrieve a quantitative Poisson limit theorem in the boundary case $\alpha=1$, again using Stein’s method.

Keywords

Central limit theoremcoupon collector’s problemPoisson limit theoremsize-biased couplingStein’s method

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60F05: Central limit and other weak theorems
Type
Original Article
Information
Journal of Applied Probability , Volume 60 , Issue 4 , December 2023 , pp. 1352 - 1366
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arratia, R. Goldstein, L. and Kochman, F. (2019). Size bias for one and all. Prob. Surv. 16, 1–61.CrossRefGoogle Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford University Press.CrossRefGoogle Scholar
Baum, L. E. and Billingsley, P. (1965). Asymptotic distributions for the coupon collector’s problem. Ann. Math. Statist. 36, 1835–1839.Google Scholar
De Moivre, A. (1718). The Doctrine of Chances. W. Pearson, London.Google Scholar
Englund, G. (1981). A remainder term estimate for the normal approximation in classical occupancy. Ann. Prob. 9, 684–692.Google Scholar
Euler, L. (1785). Solutio quarundam quaestionum difficiliorum in calculo probabilium. Opuscula Analytica, Vol. 2, 331–346.Google Scholar
Goldstein, L. and Rinott, Y. (1996). Multivariate normal approximations by Stein’s method and size bias couplings. J. Appl. Prob. 33, 1–17.Google Scholar
Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application: An Approach to Modern Discrete Probability Theory. Wiley, Chichester.Google Scholar
Kolchin, V. F., Sevastianov, B. A. and Chistiakov, V. P. (1978). Random Allocations. Halsted Press, Washington.Google Scholar
Laplace, P. S. (1812). Théorie Analytique des Probabilités. Courcier, Paris.Google Scholar
Mahmoud, H. (2010). Gaussian phases in generalized coupon collection. Adv. Appl. Prob. 42, 994–1012.CrossRefGoogle Scholar
Mikhailov, V. G. (1977). A Poisson limit theorem in the scheme of group disposal of particels. Theory Prob. Appl. 22, 152–156.Google Scholar
Mikhailov, V. G. (1980). Asymptotic normality of the number of empty cells for group allocation of particles. Theory Prob. Appl. 25, 82–90.CrossRefGoogle Scholar
Neal, P. (2008). The generalised coupon collector problem. J. Appl. Prob. 45, 621–629.CrossRefGoogle Scholar
Ross, N. (2011). Fundamentals of Stein’s method. Prob. Surv. 8, 210–293.CrossRefGoogle Scholar
Schilling, J. and Henze, N. (2021). Two Poisson limit theorems for the coupon collector’s problem with group drawings. J. Appl. Prob. 58, 966–977.CrossRefGoogle Scholar
Smythe, R. T. (2011). Generalized coupon collection: The superlinear case. J. Appl. Prob. 48, 189–199.CrossRefGoogle Scholar
Stadje, W. (1990). The collector’s problem with group drawings. Adv. Appl. Prob. 22, 866–882.CrossRefGoogle Scholar
Vatutin, V. A. and Mikhailov, V. G. (1983). Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles. Theory Prob. Appl. 27, 734–743.Google Scholar