2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).$$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user109027 Nov 17 '13 at 2:59
  • $\begingroup$ @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? $\endgroup$ – mudok Mar 11 '17 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.