# Does this probability distribution have a name?

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 ?

-
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}$. –  PEV Jan 12 '11 at 17:10
@Trevor: Yes the cardinality stays $m$, but in order to guarantee that the later picks are distinct, we "temporarily" pick with replacement. –  M. Alaggan Jan 12 '11 at 17:15
@Trevor: I am not sure if what I said in the comment makes sense or not actually... –  M. Alaggan Jan 12 '11 at 17:15
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!}$. –  PEV Jan 12 '11 at 17:19

Look up multiset coefficients in Wikipedia's Multiset. Your calculation would actually give $\frac{m!}{x!}\left(\frac{x}{m}\right)^{(a-x)}\binom {m}{x}$ the way you are arguing but the approach is not correct and this will not sum to 1. You are not counting the correct number of ways to get x different items.

-
The Multiset coefficient is new to me, but from what I understood I see that it allows for repetition, rather than restricting the counting to distinct values. Or am I confused ? –  M. Alaggan Jan 12 '11 at 17:17
Yes, but if you pick a elements and ask the X be distinct, you have a multiset. You allow that certain members are repeated. This section shows how to count the number of ways to have exactly X distinct when picking a. –  Ross Millikan Jan 12 '11 at 17:21

The number of multisets from a set of size $m$ with cardinality $a$ is $\binom{m+a-1}{a}$.

-
True, but how many of those has a distinct cardinality of $x$ (i.e. number of distinct items is exactly $x$) ? –  M. Alaggan Jan 12 '11 at 17:49
@M.Alaggan: You first choose the $a$ elements from the $m$ element set(with replacement). Then from your chosen set of $a$ elements, you calculate the probability of $x$ of the $a$ elements of being distinct. –  PEV Jan 12 '11 at 17:52
Great! That is an approach worth trying, thanks :) –  M. Alaggan Jan 12 '11 at 17:56
The probability of picking (with replacement) $a$ distinct items from a set of size $m$ is
$$\frac{m}{m} \frac{m-1}{m} ... \frac{m-a+1}{m} = \frac{(m)_a}{m^a}$$
A more wordy version is: There are $a$ terms in the above. Each term represents one pick. Your first pick you can pick any of $m$ items from the set, so the probability you pick $1$ distinct item, from $m$ distinct items is $\frac{m}{m}$. Second term comes from the fact that on your second pick, you have $m-1$ options that don't duplicate the first pick. These are independent events, so you can multiply the probabilities together. Rinse and repeat for a total of $a$ times, and you have the result.