3
$\begingroup$

We have a set of numbers, of size $m$. We are going to pick $a$ numbers with uniform probability from that set, with replacement. Let X be the random variable denoting the probability of having X of those picks distinct (exactly X distinct values are picked).

Motivation: I need to calculate this probability in order to calculate a more advanced distribution regarding Bloom filters, in particular the distribution of the number of bits set to 1 in a Bloom filter.

Letting that aside, I am having trouble formulating the the PMF for X. I've tried to look out for multi-variate binomial distribution but I couldn't relate it to what I want to do.

The question is whether there is such a probability distribution in the literature, and if now, how can I approach this problem ?

Thanks.

Update:

I have managed to make a formulation: the probability we pick $x$ distinct values is $$ \frac{1}{m} \frac{1}{m-1} \cdots \frac{1}{m-x+1} $$

And the probability of picking the rest of our $a-x$ picks in that set of $x$ values is $$ \left(\frac{x}{m}\right)^{a-x} $$

Finally, the number of such configurations is $\binom{m}{x}$. Multiplying all that together and simplifying gives us a PMF

$$ P(X=x;a,m) = \frac{ \left( \frac{m}{x} \right) ^{x-a}}{x!} $$

Does that seem to make any sense ?

  • 0
    Alaggan: The cardinality of the set stays $m$ right (since we are sampling with replacement)? So the probability that you pick $x$ distinct values is $(\frac{1}{m})^{x}$.2011-01-12
  • 0
    @Trevor: Yes the cardinality stays $m$, but in order to guarantee that the later picks are distinct, we "temporarily" pick with replacement.2011-01-12
  • 0
    @Trevor: I am not sure if what I said in the comment makes sense or not actually...2011-01-12
  • 0
    Alaggan: The number of combinations possible when $k$ balls are selected from a box with $n$ distinguishable balls (with replacement) is $\frac{(n+k-1)!}{(n-1)!k!}$.2011-01-12

4 Answers 4