4
$\begingroup$

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 :)

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting. But a clarification: After the 499th element is added, the possible number of trials to get a number not in the set is much larger than 2. Am I missing something here? $\endgroup$ – PhD Mar 19 '14 at 7:49
  • $\begingroup$ The possible number is not bounded. I was talking about the expected i.e. average number. With about half the numbers taken there's about a 50-50 chance that any number you choose is one not already in your set, so on average it takes two tries. Unless I misunderstood your question. $\endgroup$ – Glen_b Mar 19 '14 at 7:54
  • $\begingroup$ I see what you mean. Another question: How exactly is the expected number of trials until next success is n/(n-k)? I've been trying to derive that from first principles but don't see how we compute that... $\endgroup$ – PhD Mar 19 '14 at 18:14
  • 1
    $\begingroup$ Because at a given number of hits already, you're in a sequence of independent Bernoulli trials, where the probability of succeeding (choosing a value you don't already have) is $(n-k)/n$. The number of trials to the next success is Geometric with $p=(n-k)/n$. The mean of the 'number of trials' version of the geometric is $1/p$. If you want details of how to calculate of means of distributions, I think that should be a new question. $\endgroup$ – Glen_b Mar 19 '14 at 22:55
  • 1
    $\begingroup$ Actually, even if it's not uniform but you only care about the set of samples (not the multiset), then your answer should still work if in sampling you just drop the elements you've already seen and renormalize.... $\endgroup$ – Danica May 7 '17 at 16: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.