HOW MANY IID SAMPLES DOES IT TAKE TO SEE ALL THE BALLS IN A BOX?
成果类型：
Article
署名作者：
Sellke, Thomas M.
署名单位：
Purdue University System; Purdue University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004841
发表日期：
1995
页码：
294-309
关键词：
摘要：
Suppose a box contains m balls, numbered from 1 to m. A random number of balls are drawn from the box, their numbers are noted and the balls are then returned to the box. This is done repeatedly, with the sample sizes being iid. Let X be the number of samples needed to see all the balls. This paper uses Markov-chain coupling to derive a simple but typically very accurate approximation for EX in terms of the sample size distribution. The approximation formula generalizes the formula found by Polya for the special case of fixed sample sizes.