How many samples does it take to see all the balls in an urn? (Q1282508): Difference between revisions

Consider an urn containing \(N\) balls, numbered from 1 to \(N\). A random number \(K\) of balls are drawn without replacement, their numbers are noted and the balls are then returned to the urn. This is done repeatedly, with the sample sizes being independent identically distributed as \(K\). Let \(v(N,K)\) denote the number of samples needed to see all the balls. It is shown that \[ Ev(N,K)\approx {N\over a_1} \sum^N_{n=1} {1\over n}+ {a_1- a_2\over 2a^2_1} \sum^N_{n= 2}{1\over n}, \] where \(a_j= EK^j\), \(j= 1,2\). The asymptotic distribution of \(v(N,K)\) as \(N\to\infty\) is also derived. For related work see \textit{T. M. Sellke} [Ann. Appl. Probab. 5, No. 1, 294-309 (1995; Zbl 0823.60054)].