How many iid samples does it take to see all the balls in a box? (English) Zbl 0823.60054

Sellke, Thomas M.

Ann. Appl. Probab. 5, No. 1, 294-309 (1995).

Summary: 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 i.i.d. 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 Pólya for the special case of fixed sample sizes.

MSC:

60J10

Markov chains (discrete-time Markov processes on discrete state spaces)

Keywords:

coupon collector’s problem; Markov chains; Markov-chain coupling