5
$\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$
1

1 Answer 1

6
$\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$
9
  • $\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, 2014 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, 2014 at 7:54
  • 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, 2014 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, 2017 at 16:57
  • 1
    $\begingroup$ @Danica It seems like one of my comments in this thread is now misnaming you (it referred to what I assume is an older username on your account). I have just now (as I type) removed that comment since the discussion still makes perfect sense without it and it didn't say anything essential. $\endgroup$
    – Glen_b
    Apr 22, 2022 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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