On the Number of i.i.d. Samples Required to Observe All of the Balls in an Urn

Brad C. Johnson () and Thomas M. Sellke ()
Additional contact information
Brad C. Johnson: University of Manitoba
Thomas M. Sellke: Purdue University

Methodology and Computing in Applied Probability, 2010, vol. 12, issue 1, 139-154

Abstract: Abstract Suppose an urn contains m distinct balls, numbered 1,...,m, and let τ denote the number of i.i.d. samples required to observe all of the balls in the urn. We generalize the partial fraction expansion type arguments used by Pólya (Z Angew Math Mech 10:96–97, 1930) for approximating $\mathbb{E}(\tau)$ in the case of fixed sample sizes to obtain an approximation of $\mathbb{E}(\tau)$ when the sample sizes are i.i.d. random variables. The approximation agrees with that of Sellke (Ann Appl Probab 5(1):294–309, 1995), who made use of Wald’s equation and a Markov chain coupling argument. We also derive a new approximation of $\mathbb{V}(\tau)$ , provide an (improved) bound on the error in these approximations, derive a recurrence for $\mathbb{E}(\tau)$ , give a new large deviation type result for tail probabilities, and look at some special cases.

Keywords: Coupon collector’s problem; Generalized coupon collector’s problem; Markov chains; Primary 60J010; Secondary 60E05 (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-008-9095-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:12:y:2010:i:1:d:10.1007_s11009-008-9095-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-008-9095-1

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().