Expected number of ball tosses to have at least 5 balls in 4 out of 5 bins (Skyrim application) I have a bit of an interesting probability question that has an application to Skyrim and the number of quests you need to complete to get an achievement for the Thieves Guild. I can generalize the problem in terms of balls and bins.
Say you have an infinite number of balls available, and there are 5 bins, we can label them bins 1-5 (the bins are distinct). When you toss a ball, it is equally likely to fall into each bin (1/5 chance). What is the expected number of tosses so bins 1-4 have at least 5 balls in them? Each bin can hold an infinite number of balls, and we don't care about the balls falling into bin 5 (meaning it can't necessarily be the first 4 bins to have 5 balls).
I know that if I only cared about 1 bin reaching 5 balls, the expected value would be 5/p where p is the probability (1/5), but I can't continue this logic once one of the bins has 5 balls since the other bins may already have balls in them (the "misses" from trying to fill the first bin) so I have to use some other reasoning.
I wrote some code that I think simulates the rules above and I am getting around 29.7, which is lower than I would expect (the absolute minimum tosses is 20) so I would like to confirm or disprove this result as well as know how to generate a mathematical formula and calculate this without code.
Link to the code:https://github.com/nodnarb22/Skyrim-Thieves-Guild-Radiant-Quest-Simulator/blob/main/thievesguild
Any help or input would be much appreciated!
 A: The expected number of tosses necessary until bins 1-4 all contain at least 5 balls is $37.1378$.  This value is consistent with a Monte Carlo simulation I wrote but not with the OP's simulated value of $29.7$.  I think this is due to an error in the use of the random.randint function in the linked-to Python code.  One should be aware that the function random.randint(1,5) returns only integers in the range $[1,4]$; it will never return $5$.
The following solution uses exponential generating functions.  The reader not familiar with generating functions may find many resources in the answers to the question How can I learn about generating functions?
Define $T$ to be the number of the first toss in which bins 1-4 all contain at least $5$ balls each (and bin $5$ contains any number of balls whatever), and let $p_n = P(T \le n)$.  The EGF of $p_n$ is
$$f(x) = \left( e^{x/5} - 1 - \left( \frac{x}{5} \right) - \frac{1}{2!} \left( \frac{x}{5} \right)^2 - \frac{1}{3!} \left( \frac{x}{5} \right)^3 - \frac{1}{4!} \left( \frac{x}{5} \right)^4 \right)^4 \; e^{x/5} \tag{*}$$
We are interested in $q_n = P(T > n)$.  Since $q_n = 1 - p_n$, the EGF of $q_n$ is $e^x - f(x)$.  By a well-known theorem, $E(T) = \sum_{n=0}^{\infty} q_n$.  Making use of the identity
$$n! = \int_0^{\infty} e^{-x} x^n \; dx$$
in combination with the definition of the EGF
$$e^x - f(x) = \sum_{n=0}^\infty \frac{q_n}{n!} x^n$$
we have
$$\sum_{n=0}^{\infty} q_n= \int_0^{\infty} e^{-x} (e^x - f(x)) \; dx$$
So $$E(T) = \int_0^{\infty} e^{-x} (e^x - f(x)) \; dx$$
where $f(x)$ is given by $(*)$.
Evaluating the integral (I used Mathematica) yields $E(T) = 37.1378$.
A: Let's start with considering that
$$
\begin{array}{l}
 \left( {x_1  + x_2  + x_3  + x_4  + x_5 } \right)^n  =  \cdots
  + x_{k_{\,1} } x_{k_{\,2} }  \cdots x_{k_{\,n} }
  +  \cdots \quad \left| {\;k_j  \in \left\{ {1,2, \cdots ,5} \right\}} \right.\quad  =  \\ 
  =  \cdots  + x_{\,j_{\,1} } ^{r_{\,1} } x_{\,j_{\,2} } ^{r_{\,2} }  \cdots x_{\,j_{\,n} } ^{r_{\,n} }
  +  \cdots \quad \left| \begin{array}{l}
 \;j_i  \in \left\{ {1, \ldots ,5} \right\} \\ 
 \;\sum\limits_i {r_i }  = n \\  \end{array} \right.\quad  =  \\ 
  = \sum\limits_{\left\{ {\begin{array}{*{20}c}
   {0\, \le \,k_{\,j} \,\left( { \le \,n} \right)}  \\
   {k_{\,1}  + k_{\,2}  + \, \cdots  + k_{\,5} \, = \,n}  \\
\end{array}} \right.\;} {\left( \begin{array}{c}
 n \\  k_{\,1} ,\,k_{\,2} ,\, \cdots ,\,k_{\,5}  \\ 
 \end{array} \right)x_{\,1} ^{k_{\,1} } x_{\,2} ^{k_{\,2} }  \cdots x_{\,5} ^{k_{\,5} } }  \\ 
 \end{array}
$$
is enumerating all possible sequences of $n$ tosses ending with $k_j$ balls in box $j$, and
$$
\begin{array}{l}
 \left( {1 + 1 + 1 + 1 + 1} \right)^n  = 5^n  =  \\ 
  = \sum\limits_{\left\{ {\begin{array}{*{20}c}
   {0\, \le \,k_{\,j} \,\left( { \le \,n} \right)}  \\
   {k_{\,1}  + k_{\,2}  + \, \cdots  + k_{\,5} \, = \,n}  \\
\end{array}} \right.\;} {\left( \begin{array}{c}
 n \\  k_{\,1} ,\,k_{\,2} ,\, \cdots ,\,k_{\,5}  \\  \end{array} \right)}  \\ 
 \end{array}
$$
Now let's consider the configuration of boxes having respectively $\ge 5, \ge 5,\ge 5,\ge 5,  \le 4 $ balls:
last box has a different content, it is distinguishable and we have $5$
ways to choose it out of the five.
So the number of sequences that have such a configuration after $n$ tosses is
$$
\begin{array}{l}
 N(n) = 5\sum\limits_{\left\{ {\begin{array}{*{20}c}
   {5\, \le \,k_{\,1,2,3,4} \,\left( { \le \,n} \right)}  \\
   {\,0 \le k_{\,5}  \le 4}  \\
   {k_{\,1}  + k_{\,2}  + \, \cdots  + k_{\,5} \, = \,n}  \\
\end{array}} \right.\;} {\left( \begin{array}{c}
 n \\  k_{\,1} ,\,k_{\,2} ,\, \cdots ,\,k_{\,5}  \\ 
 \end{array} \right)}  =  \\ 
  = 5\sum\limits_{\left\{ {\begin{array}{*{20}c}
   {0\, \le \,j_{\,1,2,3,4} \,\left( { \le \,n - 5} \right)}  \\
   {\,0 \le k\left( { \le 4} \right)}  \\
   {j_{\,1}  + j_{\,2}  + \,j_{\,3}  + j_{\,4} \, = \,n - 24 + k}  \\
\end{array}} \right.\;} {\left( \begin{array}{c}
 n \\  5 + j_{\,1} ,\,5 + j_{\,2} ,\,5 + j_{\,3} ,5 + j_{\,4} ,\,4 - k \\ 
 \end{array} \right)}  =  \\   = \quad  \ldots  \\ 
 \end{array}
$$
there are many ways to rewrite the multinomial in terms of binomials etc. and I will omit them.
Clearly
$$
\begin{array}{l}
 N(n) = 0\quad \left| {0 \le n \le 19} \right. \\ 
 N(20) = 5\frac{{20!}}{{\left( {5!} \right)^4 0!}} \\ 
 \quad  \vdots  \\ 
 \end{array}
$$
But to answer to your question, the above is not much of interest.
We need in fact to find the number of sequences that becomes "successful" at the n-th toss.
The $n-1$ -sequences which can become successful just at the following step $n$ are only
of these two types
$$
\begin{array}{l}
 \left\{ { \ge 5,\; \ge 5,\; \ge 5,\; = 4,\; = 4} \right\}, \\ 
 \left\{ { \ge 5,\; \ge 5,\; \ge 5,\; = 4,\; < 4} \right\} \\ 
 \end{array}
$$
and since they can be permuted, we have respectively
$$
\left( \begin{array}{c} 5 \\  2 \\  \end{array} \right),\;
 2\left( \begin{array}{c} 5 \\  2 \\ \end{array} \right)
$$
ways to arrange them, and thereafter

*

*two ways to place the $n$th ball for the first,

*one way the second.

Therefore
$$
\begin{array}{l}
 N_{first} (n) = 2\left( \begin{array}{c}
 5 \\  2 \\  \end{array} \right)\left( {\sum\limits_{\left\{ {\begin{array}{*{20}c}
   {5\, \le \,k_{\,1,2,3} \,\left( { \le \,n - 9} \right)}  \\
   {k_{\,1}  + k_{\,2}  + \, \cdots  + k_{\,5} \, = \,n}  \\
\end{array}} \right.\;} {\left( \begin{array}{c}
 n - 1 \\  k_{\,1} ,\,k_{\,2} ,k_{\,3} ,4,\,4 \\ 
 \end{array} \right)}  + \sum\limits_{\left\{ {\begin{array}{*{20}c}
   {5\, \le \,k_{\,1,2,3} \,\left( { \le \,n - 5 - j} \right)}  \\
   {0 \le j \le 3}  \\
   {k_{\,1}  + k_{\,2}  + k_{\,3} \, + j\, = \,n - 5}  \\
\end{array}} \right.\;} {\left( \begin{array}{c}
 n - 1 \\  k_{\,1} ,\,k_{\,2} ,k_{\,3} ,4,\,j \\ 
 \end{array} \right)} } \right) =  \\ 
  = \quad  \cdots  \\ 
 \end{array}
$$
and for the probability
$$
P_{first} (n) = \frac{{N_{first} (n)}}{{5^n }}
$$
and then the expected $n$ follows obviously.
