Calculating probability of getting $m$ unique numbers when choosing $n$ times from $0\ldots k$

Question

I'm trying to write a test to verify a reasonable distribution for a function that generates 4-digit pin numbers from 8 digit phone numbers. I'm not aware of any direct method of calculating this, so my approach is to (1) generate $n$ pin numbers, (2) for each $i \in \{1,\ldots,n\}$ calculate the probability that there would be $i$ unique pin numbers among the generated, and (3) test that the actual number of unique pins in the $n$ generated fall within $\pm2$ stdev of the average of the probabilities calculated in step (2).

I'm stuck on step 2.

I know that the probability of choosing only 1 distinct number from $0..k$ in $n$ tries is

$$\left(1 \over k \right)^{n-1}$$

and that the probability of choosing $n$ distinct numbers from $0..k$ in $n$ tries is

$$\prod_{i=0}^n{1-\left(i \over k \right)}$$

How do I calculate the probability when the chosen numbers aren't all the same or all distinct?

Answer 1

You are looking at a generalization of the well-known birthday problem. Here's a reference which gives a formula for your case (although the variables are named differently than yours). I've transcribed the relevant result using your naming.

The probability of getting $m$ unique values from $[0, k)$ when choosing $n$ times is given by:

$$P(V = m) = \binom{k}{m}\displaystyle\sum_{i=0}^m (-1)^i \binom{m}{i} \left(\frac{m-i}{k}\right)^n $$

where $V$ is a random variable giving the number of unique outcomes and $\binom{\cdot}{\cdot}$ is the binomial coefficient.

Answer 2

If I understand your question correctly, what you really want is the expected value and the standard deviation of $V,$ the number of distinct values found in $n$ independent random variables each drawn with uniform distribution from a set of $k$ values. (You need the expected value to compare the actual number of unique values to, and you need the standard deviation so that you can determine if the actual number of unique values is within $\pm2\sigma$ of the expected value.)

You apparently intend to get these results by explicitly computing the distribution of $V$ (your "step (2)") and then applying the formulas for expected value and standard deviation of a discrete distribution. But step (2) is more work than you need to do.

The reference already provided by George V. Williams gives formulas for the expected value and variance of $V$ that do not require explicit knowledge of the probability with which any particular number of unique values occurs. The expected value is $$ E(V) = k\left(1−\left(1−\frac1k\right)^n\right)$$ (as adapted from the expectation computed in the reference, assuming $k$ possible values from which to choose where the reference assumes $m$). The variance (similarly adapted from the notation of the reference) is $$\mathrm{var}(V) = k(k−1)\left(1−\frac2k\right)^n + k\left(1−\frac1k\right)^n − k^2\left(1−\frac1k\right)^{2n}$$