Determining the probability of unique values chosen from a larger set? I'm trying to solve what I think is a more generalized version of the "birthday paradox".  I run into problems like this all the time and I can never quite figure out how to tackle them.
Suppose I have a set of $M$ possibilities all with an equal probability of being chosen: $\operatorname{P}(M_n) = 1/M$.  Now suppose I pick from the set of possibilities $N$ times.  I'd like to know the probability of there being $C$ unique values chosen.  I'd also like to know the probability of the tails.
This strikes me as related to the Birthday paradox.
To make the problem more concrete, I'm currently trying to figure out how unexpected an event is.  I have $156$ salts chosen where each salt is a $12\mathrm{-bit}$ number.  Only $147$ salts were unique.  That is, $9$ of them are duplicates.  So $M = 2^{12} = 4096$ and $N = 156$.  I'd like to calculate the probability that there were exactly $147$ unique salts chosen.  I'd also like to be able to compute the probably of at least $147$ and at most $147$.
Is there a probability distribution for this?  Maybe something like the Poisson distribution?
 A: Define the Bernoulli random variable $X_i$ to be one if the number $i$ is chosen and zero otherwise. Then the number of distinct numbers chosen is $X:= X_1+\cdots+X_N$. Each $X_i$ is zero with probability $\left(1-\frac 1 M\right)^N$. Hence, $E[X_i]= 1-\left(1-\frac 1 M\right)^N$, and by the linearity of expectation,
$$E[X] = N\cdot\left(1-\left(1-\frac 1 M\right)^N\right)$$
which yields
$$ N\cdot\left(1-\exp(-N/M)\right)\le E[X]\le N\cdot\left(1-4^{-N/M}\right)$$
Although $X_i$'s are not independent, we can still get tail estimates by applying Chernoff bounds on $X$ since they seem to be "negatively dependent" (roughly, knowing that a subset of $X_i$'s are high does not increase the chance of other disjoint subsets being high).
In fact, the problem you are considering is the number of non-empty bins in a balls into bins experience with $N$ balls and $M$ bins. This model is well explored - as far as I know, there are at least tail bounds on the number of empty bins.
A: To end up with $C$ unique values, you'd have to select one of $\binom{M}{C}$ possibilities, and spread the remaining $N-C$ options among the $C$ selected.
That leads to $\binom{M}{C}\binom{C}{N-C}$ ways out of $N^M$.
I am not sure that this answers your question.
