How many times, in expectation, am I fetching a random sample from a predefined discrete probability distribution of elements? As part of a simulation that I'm working on, I have a probability distribution over $n$ elements, from which I have to sample a set $S$  of size $m$. That is, each element  $e \in S$ must be unique [1].
Conceptually I have the following piece of code:
while(S.size < m)
   getNextSampleFromDistribution();

If an element already exists in the set $S$, I just fetch another sample. That is, I keep repeatedly sampling from the distribution, until the set is populated with $m$ elements.
In expectation, how many times is getNextSampleFromDistribution() called? How can I compute that? 
Someone suggested that the arrival of the next valid sample, can be modeled as a Poisson process with the wait times between them being exponential and thus this can be categorized as an exponential distribution where $E[calls \space to \space getNext...] = 1/\lambda$. If true, then what is $\lambda$ in this case? If not, then how best to come up with a strong theoretical expectation value explaining this?
For a simulation that I ran for generating a set of 500 elements from a probability distribution over 1000 number, the while loop ran close to $20,000$ times in some instances!
[1] - this is redundant if I say 'set' but still making it clear if someone overlooks that :)
 A: This question is related to the coupon-collector problem, but it's one where you only require $m$ of the $n$ elements.
The number of calls to the next success is not Poisson but geometric, and the $p$ for that geometric changes with each success (since the chance of hitting already obtained values increases). Here 'success' is 'obtain an element we don't already have'.
The expected number of trials until the next success, given $k$ successes so far, is $\frac{n}{n-k}$
So when $k$ = 0, it's 1 - you get a success immediately.
Then when $k$=1, you expect $\frac{n}{n-1}$ tries until the next success, and so on.
So the expected number of trials until the $m$th success is 
$n[\frac{1}{n}+\frac{1}{n-1} + \frac{1}{n-2}+ \ldots + \frac{1}{n-m}]$
$= n(H_n-H_{n-m-1})$  ($H_n$ is the $n^{\text{th}}$ harmonic number).
Since $ \lim_{n \to \infty} \left(H_n - \ln n\right) = \gamma\,$, a reasonable approximation for large $n$ and $m$ not too small might be $n(\log(n)-\log(n-m-1))$, which would suggest you expect just over 695 trials on average ... but the distribution is somewhat skew, so sometimes it might take a while longer than that.
(I am not sure how you get it to take 20000, though, if m=500 and n=1000, the expected number of trials to get the last one is only about 2, and each of the earlier ones is shorter on average.)
