If I roll $D$ copies of an $S$-sided dice, which is the probability that I will get at least $M$ matches?
For example, consider $D=3$, $S=4$, $M=2$: rolling three $4$-sided dice, looking for two or more of a kind.
There are $4^3=64$ possible rolls. The probability is $\dfrac{40}{64}$ ($36$ ways of getting exactly a pair plus four ways of getting three of a kind, out of $4^3$ possible rolls).
What is the probability in the general case? Assuming there isn't a closed-form solution, is there a good upper bound? My application involves values in the range of $D=10^{12}$, $S=10^9$, $M=10^1$.
Edit: this was an answer given for a version with the question with a typo on it. It's an approximation assuming that $D$ and $S$ are both large, and $D$ is much smaller than $S$.
If we let $X_k$ count the number of dice that come up $k$, then $X_k$ counts lots and lots of independent events that are each very very unlikely: a textbook case for the Poisson approximation. We have $\mathbb E[X_k] = \frac{D}{S}$, so $X_k$ is approximately a Poisson random variable with rate $\frac{D}{S}$: we have $$\Pr[X_k = n] \approx e^{-D/S} \frac{(D/S)^n}{n!}.$$
Moreover, if $D$ is much smaller than $S$, then most values are not going to show up at all, and are even less likely to show up $M$ times. If a value does show up at least $M$ times, it has very good odds of showing up exactly $M$ times: we have $\Pr[X_k = M+1] = \Pr[X_k = M] \cdot \frac{D}{S(M+1)}$, which is on the order of $10^{-4}$ for your application. So we can approximate the probability that $X_k \ge M$ by the probability that $X_k = M$ pretty darn well. Let $$p^* = \Pr[X_k = M] \approx e^{-D/S} \frac{(D/S)^M}{M!}$$ so that we can refer to this value later.
Then we know have very very many events ($S$ of them) that are each very very unlikely ($p^*$ is very small): the event that $X_1 \ge M$, that $X_2 \ge M$, that $X_3 \ge M$, and so on, all the way to $X_S \ge M$. So the Poisson approximation is once again an excellent estimate. If $Y$ is the number of values $k$ such that $X_k \ge M$, then $\mathbb E[Y] \approx p^* S$, so $Y$ is Poisson with rate $p^* S$, and we have $$\Pr[Y=0] \approx e^{-p^*S} \approx \exp\left(-Se^{-D/S} \frac{(D/S)^M}{M!}\right).$$
This, then, is our estimate for the probability that there are no values occurring $M$ times.