What's the probability of getting any one face at least $m$ times, when throwing a $k$-sided die $n$ times?

Question

Say we have a $k$-sided die, and we want to throw it $n$ times.

What's the expression for the probability of getting any one face up at least $m$ times, where $m \in \{0, ... , n\}$?

Edit: The question previously asked about the probability of getting a specific face at least $m$ times. I realized that's not what I wanted, my apologies. I'm instead looking for the probability of getting any one face at least $m$ times. So whether we get '1' at least $m$ times, or '2' at least $m$ times, or '$k$' at least $m$ times, they will all be favorable outcomes.

Answer 1

The probability of the complementary event, that no face appears $m$ times or more, is $$ \frac{n!}{k^n}[x^n]\left(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\dots+\frac{x^{m-1}}{(m-1)!}\right)^k\tag{$*$} $$ Here, $[x^n]f(x)$ means the coefficient of $x^n$ in the polynomial $f(x)$ (more generally, $f$ can be a power series). To see this, note that if you brute force expand out $\left(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\dots+\frac{x^{m-1}}{(m-1)!}\right)^k$ and collect all powers of $x^n$, the result is $$ \frac1{k^n}\sum_{a_1+a_2+\dots+a_k=n,\\0\le a_i\le m-1}\frac{n!}{a_1!a_2!\cdots a_k!} $$ The summation ranges over all tuples $(a_1,\dots,a_k)$ of nonnegative integers between $0$ and $m-1$ whose sum is $n$. For each $i\in \{1,\dots,k\}$, the variable $a_i$ indicates choosing the summand $x^{a_i}/a_i!$ in the $i^{th}$ copy of $(1+x^1/1!+\dots+x^{m-1}/(m-1)!)$. But this summation is obviously a brute-force way to count the number the number of sequences of length $n$, whose entries are die faces, such that each face appears at most $m-1$ times.

This also follows from the the theory of exponential generating functions, which is explained in chapter 3 of generatingfunctionology, available for free online.

Finally, the answer to your question is one minus the expression $(*)$.

Answer 2

This is equivalent to placing $n$ balls inside $k$ urns, we want $1-P_{n,k,m}$ where $P_{n,k,m}$ is the probability that all urns have less than $m$ balls.

An exact solution is rather convoluted (see Mike Earnest's answer).

An approximate solution, for large $n,k,m$, can be obtained via Poissonization: the number of balls inside each urn can be approximated by a Poisson with $\lambda = n/k$, and, in this approximation

$$P_{n,k,m} \approx \left( e^{-\lambda} \sum_{j=0}^{m-1} \frac{\lambda ^j}{j!} \right)^k= e^{-n} \left( \sum_{j=0}^{m-1} \frac{(n/k) ^j}{j!} \right)^k$$

See also:

Probability of 3 people in a room of 30 having the same birthday

What is the probability that throwing $m$ balls at random in $n$ urns at least one urn contains $c$ elements?

https://stats.stackexchange.com/questions/475169/maximum-number-of-balls-thrown-into-k-urns-with-equal-probability