# What is the expected time to cover $m \leq N$ elements in a set by sampling uniformly and with replacement?

The expectation for covering a set of $N$ elements by sampling uniformly and with replacement is $N * H(N)$, where $H(N)$ is the $N$th harmonic number. Is there a similar expression using harmonic numbers for the expectation for the number of sampling events necessary to see any $m \leq N$ unique elements in the set?

To be clear, imagine a set of unique integers: {1, 2, 3, 4, 5}. I sample randomly and uniformly from this set, sequentially pulling, say, the elements: $5$, $5$, $3$, $5$, $2$, and so on. Here, the chance of pulling the element $4$ is trivially $\frac{1}{5}$ each trial. If we set $m = 3$, here, we'd be asking for the number of sampling with replacement events necessary to see a random subset of three out of the five unique integers in the set (of which there are $5$ choose $3 = 10$ possibilities).

What is the expectation for the general case of the problem? Can this be expressed in a nice way using harmonic numbers?

I'm still not sure what you mean by "see any $m\le N$ unique elements".
I. Maybe you mean that you're going to wait till you've seen a specific set of $m$ elements. E.g., you're drawing from the set $\{1,2,\dots,N\}$, and you're going to keep drawing till you've seen the $m$ elements $1,2,\dots,m$. In this case, the expected waiting time is$$E[W]=NH_m=N\left(\frac11+\frac12+\dots+\frac1m\right).$$
II. Maybe you mean that you're going to wait till you've seen any $m$ distinct elements. In this case the expected waiting time is $$E[W]=N\left(H_N-H_{N-m}\right)=N\left(\frac1N+\frac1{N-1}+\cdots+\frac1{N-m+1}\right).$$
• I meant the case where we consider any distinct elements, so thanks for your help! In my other question, I noticed (from simulation) that the number of elements I draw that are not a specific set of $m$ elements (prior to covering the $m$ elements) seems to scale as $(N - m)*H(m)$. Does this make sense to you? – user109027 Nov 17 '13 at 2:59
• @bof Hi I dont understand why for the case of any m distinct elements the waiting time is $N(H_N-H_{N-m})$. Can you please explain? – mudok Mar 11 '17 at 1:57