I'm drawing $k$ times independently and uniformly random from the the set $\{1,...,n\}$ (aka a multinomial distribution where all $p_i$ are equal).
Is there a formula for (a good lower bound to) the probability that I get every outcome at least $m$ times?
Or, formulated differently: how large do I need to (even better: how small can I) choose the number of draws $k$, s.t. every outcome appears at least $m$ times with probability $\ge$ a target value, for example 99%?
Of course, this is only interesting for $k \ge m \cdot n$.
Let $B_i$ be the number of times that $i$ is chosen, for each $i\in \{1,\dots,n\}$. It is equivalent to find an upper bound for the probability that some number is chosen at most $m-1$ times.
As long as $k>nm$, \begin{align} P(\{B_1\le m-1\}\cup \dots \cup \{B_n\le m-1\}) &\le n\cdot P(B_1\le m-1) \\&\le n\cdot \exp\left(-2\frac{(E[B_1]-(m-1))^2}{k}\right) \\&= n\cdot \exp\left(-2\frac{(k/n-m+1)^2}{k}\right) \end{align}
The first inequality is the union bound, the second is Hoeffding's inequality. For any given values of $n$ and $m$, and a given $\epsilon>0$, your question is answered by the smallest value of $k$ such that the last quantity is at most $\epsilon$. You could technically get a messy formula for the smallest such $k$ in terms of $m,n,\epsilon$ by solving a quadratic equation.