How many times should I draw with replacement? Given an urn with $M$ unique balls, how many times do I need to draw with replacement before the probability that I have seen each ball at least once is greater than $\epsilon$?
 A: Any sequence of $n$ drawings results in a word $w$ of length $n$ over the alphabet $[M]$. There are $M^n$ such words.
How many of these words $w$ are admissible, meaning that $w$ contains each letter $\ell\in [M]$ at least once? Any admissible word can be fabricated in the following way: Choose a partition of $[n]$ (the set of positions for the $n$ letters to be written) into $M$ nonempty blocks and assign  to each block one of the letters $1$, $2$, $\ldots$, $M$. There are
$$\left\{\matrix{n\cr M\cr}\right\}\tag{1}$$
ways to choose this partition, where $(1)$ denotes a so-called Stirling number of the second kind, and there are $M!$ ways to assign a letter $\ell$ to each of the $M$ blocks. It follows that there are $M!\left\{\matrix{n\cr M\cr}\right\}$ admissible words. Therefore the probability $p_n$ that a random word of length $n$ is admissible is given by
$$p_n=\left\{\matrix{n\cr M\cr}\right\}{M!\over M^n}\ .$$
In order to determine the minimal $n$ for which $p_n>\epsilon$ one would need estimates for the Stirling numbers $\left\{\matrix{n\cr M\cr}\right\}$.
A: You can see this as a combinatorial problem.
There are $M^k$ possible run of $k$ draw each with the same probability (the draw are independent).
For a run we have seen each balls at least once if we can choose $M$ indexes such that for those indexes the balls are different. There are ${k\choose M}$ such set of indexes possible, and for each one $M!$ possibility to arrange the balls in those indexes.
Hence the number of run of length k that have seen all the balls at least once is  $${k\choose M}M!$$
it follows that the probability to have such a run is ($0$ for $k<M$ and for $k\geq M$):
$$P(X=k)=\frac{{k\choose M}M!}{M^k}=\frac{\frac{k!}{M!(k-M)!}M!}{M^k}=\frac{k!}{M^k(k-M)!}$$
So if you want $P(X=k)\geq \epsilon$ you have to sole $$\frac{k!}{M^k(k-M)!}\geq\epsilon$$ 
It should be doable :)
I hope it helped.
A: Order the $M$ balls form $1$ to $M$ and suppose you have drawn $n$ balls with replacement. Among the $n$ balls, the number of ball$1$ is $x_1$, the number of ball$2$ is $x_2,\ \cdots$,  the number of ball$M$ is $x_M$, then
$$
x_1+x_2+\cdots +x_M=n
$$
you want to see each ball at least once, that is the restiction:
$$ x_i\ge 1,\ for\  1\le n\le M
$$
we have ${n-M \choose M-1}$ different choices, so I claim:
$$
P(the\ desired\ event)={n-M \choose M-1}\cdot \frac{1}{M^n}
$$
