Probability of all N possible outcomes in M trials I've stumbled across a problem of trying to test some software with randomly generated values. I want to ideally test all possible ($N$) outputs, and want to know the minimum number of test samples to run to have a 99% probability of seeing all outputs. So...
Given $N$ equally likely outcomes, what is the formula or method for computing the probability that all $N$ outcomes occurred in $M$ samples? Assume $M \geq N$.
Or, alternatively, given an $N$ and the desired probability, how do I compute a minimal $M$?
 A: Let $X_1, X_2, \ldots, X_n$ be the frequencies of occurrence of each outcome in the $m$ samples. Then
$$ (X_1, X_2, \ldots, X_n) \sim \text{Multinomial}\left(m;\frac {1} {n}, 
\frac {1} {n}, \ldots, \frac {1} {n} \right)$$
The required probability is
$$ \begin{align} 
&~ \Pr\left\{X_1 \geq 1, X_2 \geq 1, \ldots, X_n \geq 1 \right\} \\
= &~ 1 - \Pr\left\{\bigcup_{i=1}^n X_i = 0\right\} \\
= &~ 1 - \sum_{j=1}^n (-1)^{j-1}\binom {n} {j} \Pr\{X_1 = 0, \ldots, X_j = 0\} \\
= &~ 1 - \sum_{j=1}^n (-1)^{j-1}\binom {n} {j} \left(1 - \frac {j} {n}\right)^m \\ 
\end{align}$$
A: I am going to assume that $n$ is large and use asymptotics to give an approximate, rather than an exact answer. This is related to expected wait time and is known as the coupon collecting problem. Let $T$ be the time needed to collect all $n$ "outputs", i.e. exactly $T$ draws (with replacement) were necessary from $n$ equally possible objects to draw each object at least once. It is easy to see that $Pr(T=m)>0$ iff $m\ge n$, since $m$ draws from a set of size $n$ has at most $\min(m,n)$  distinct values. The miniscule (for large $n$) probability of getting all $n$ outputs after the first $n$ draws is
$$
Pr(T=n)=\frac{n!}{n^n}=c(n)\frac{\sqrt{n}}{e^n},
\quad\text{for some constant}\quad
c(n)\in[\sqrt{2\pi},e]\approx[2.51,2.72]
$$
which follows firstly since in the numerator there are $n!=n(n-1)\cdots2\cdot1$ ("$n$ factorial") ways to rearrange the $n$ objects into a valid draw sequence (also the number ordered samples without replacement of $n$ objects), but there are $n^n$ ordered samples with replacement (or repetition) in the denominator. The last equality above follows from a special form of Stirling's approximation with upper and lower bounds. This gives us an asymptotic estimate of the "best case" probability (as $n$ gets large).
To find the average case, we need the concept of expected value. The expected value $E[X]$ of a random variable $X$ is basically the mean value of $X$. If we repeat this experiment many times, this would be the average time $m$ we had to wait over all the experiments. Its formal definition for a discrete variable taking on a countable set of distinct values $\{x_i\}_{i\in I}$, each with respective probability $P(X=x_i)=p_i$ is:
$$\mu_X=E[X]=\sum_{i\in I}p_ix_i$$
In our case, it turns out that the expected wait time $T$ (number $m$ of trials) to witness each of the $n$ objects is given by
$$\mu_T=E[T]
=n\sum_{k=1}^nE[T_k]
=n\sum_{k=1}^n\frac1k=n\,H_n
\approx n(\gamma+\ln n)+\frac12$$
where $T_k$, with expected value $E[T_k]=n/(n-k+1)$, is the time until $k$ distinct values have been sampled, $H_n=\sum_1^n\frac1k$ is the harmonic series of partial sums of the sequence $\frac1n$ (obtained after factoring $n$ out of the summation) and $\gamma\approx0.5772156649$ is the Euler-Mascheroni constant in its approximation.
To find out how much the time $T=m$ might typically vary from this expected or average value, we can use the variance $Var[T]=\sigma_T^2$, which is also the square of the standard deviation (SD) $\sigma_T$ of $T$. For this problem, we also have
$$\sigma_T^2=Var[T]<\frac{(\pi n)^2}6$$
so that $\sigma_T\approx\frac\pi{\sqrt6}n$.
At this point, we could use a normal approximation (as is done with Binomial variates) for $m/n$ to estimate a value of $m$ which would have $99\%$ certainty of success. By transforming $T$ to $Z=\frac{T-\mu_T}{\sigma_T}$ which approximately has the standard normal distribution (mean $0$ and SD $1$) with cumulative distribution function (CDF) $$\Phi(z)=\frac1{\sqrt{2\pi}}\int_{-\infty}^ze^{-t^2/2}dt$$ and inverse CDF or quantile function $\Phi^{-1}(p)$ (also called the probit function for the standard normal distribution), we can say that
$$ Pr(T\le m) \approx 0.99 \quad\iff $$
$$ Z=\frac{m-\mu_T}{\sigma_T} \approx Z_{0.99}=
\text{probit}(.99)=\Phi^{-1}(.99) \approx 2.33 $$
or
$$ m\approx\mu_T+2.33\,\sigma_T \approx
n\,H_n+2.33\,\frac\pi{\sqrt6}n \approx n(H_n+2.98).$$
This is an asymptotic estimate (approximating limit for large $n$)
for the number $m$ of draws needed to be $99\%$ sure of witnessing
all $n$ outputs. In general (using big-Oh notation), we can say
$m=O(n\log n)$, and in particular, that the ratio
$$\frac{m}{n}\approx H_n+2.98\approx\ln n+3.56+\frac1{2n}
\qquad(\text{for }n\gg1).$$
For a desired certainty $p$, the ratio would be
$$\frac{m}{n}\approx H_n+\frac\pi{\sqrt6}\Phi^{-1}(p)\approx
\ln n+\frac\pi{\sqrt6}\Phi^{-1}(p)+\gamma+\frac1{2n}.$$
