This is a simplified version of an applied probability modeling problem. I believe I solved it, but I'm wondering if there is a more elegant approach than mine:

There are 10 boxes and 200 balls. At each trial exactly four boxes are selected at random and exactly one ball is placed into each. Thus there are 50 trials in the game. The boxes have equal capacity. What must that capacity be so that in 90% of the 50-trial games no box overflows?

Answer: Obviously more than 20; using binomial, 28 seems to suffice.

  • $\begingroup$ In this set up can a box be selected more than once in a trial? or is it 4 separate boxes each trial? $\endgroup$ – user345 Aug 23 '17 at 2:16
  • $\begingroup$ No repetition: Exactly 4 boxes and exactly one ball per box on a trial. $\endgroup$ – BruceET Aug 23 '17 at 2:23

The filling process of any one box can be modeled as a random walk starting at $n = 0$, where at each step $n$ either increases by 1 with probability $p = 0.4$ (since the probability of any one box being chosen in a given trial is 4 out of 10) or $n$ stays the same with probability $1 - p = 0.6$. The probability of ending up with $n$ balls in any given box at the end of 50 trials is then $$ P(n) = { 50 \choose n } p^n (1 - p)^{50 - n}, $$ and the probability of having more than $n$ balls in a box is $$ P_o(n) = \sum_{m = n+1}^{50} { 50 \choose m } p^m (1 - p)^{50 - m}. $$

Now, we want to find the value of $n$ for which there is at least a 90% chance that none of the 10 boxes overflows. Since the probability of a box of capacity $n$ overflowing is $P_o(n)$, the probability of none of the ten boxes overflowing is* $$ (\text{prob. of no overflows}) = (1 - P_o(n))^{10} \geq \frac{9}{10} \qquad P_o(n) \leq 1 - \sqrt[10]{\frac{9}{10}} = 0.0104807... $$

From here, one can plug various choices of $n$ into Wolfram Alpha and find that $P_o(27) \approx 0.016$ and $P_o(28) \approx 0.007$. So the answer does appear to be 28.

Alternately, one can approximate the binomial distribution by a normal distribution. Each trial adds a mean of of $\bar{\mu} = 0.4$ balls to each bin, with a variance of $\bar{\sigma}^2 = 0.24$. This means that after $N = 50$ trials, the distribution of the number of balls $n$ in a given bin will be $$ P(n) \, dn = \frac{1}{\sqrt{2 \pi N \bar{\sigma}^2}} \exp \left[ - \frac{(n - N \bar{\mu})^2}{ 2 N \bar{\sigma}^2} \right] dn $$ This is a normal distribution with a mean of $N \bar{\mu} = 20$, a variance of $N \bar{\sigma}^2 = 12$, and a standard deviation of $\sigma = \sqrt{12}$. By the above logic, we want to know the argument of the error function $\text{erf}(x)$ such that $$ \frac{1}{2} + \frac{1}{2}\text{erf}(x) = \sqrt[10]{\frac{9}{10}} \approx 0.989519... $$ which can be found to be $x = 1.6325...$ (thanks again to Wolfram Alpha.) Thus, according to this approximation, there is a 90% chance of no overflows if the size of the boxes is greater than $20 + 1.6325 \sigma = 26.55...$. I think that the continuity correction bumps this up to 27.05, which implies that you really need a box size of 28, but it's been a while since I've used this; in any event, this is only an approximation, and it obviously comes pretty close to the exact result from the binomial distribution.

(The advantage of this sort of calculation is that it only requires one lookup of values in a table of values for the error function, rather than a series of calculations of a sum involving binomial coefficients; so it might be better for a quick-and-dirty answer, and would certainly be easier if I didn't have a computer handy.)

*The one caveat here is that I'm not 100% sure that the probability of one box overflowing is independent of the probability of any of the other boxes overflowing. It seems plausible to me, but I haven't come up with a rigorous argument.

  • 2
    $\begingroup$ I think it is clear that the probabilities of each box overflowing are not independent because if one box overflows there are fewer balls available to the other boxes. On the other hand, it seems like it will be pretty close because there are lots of other boxes to take or not take the excess balls. Absent a calculation that accounts for this (which I think is hard) we are quite close. +1 $\endgroup$ – Ross Millikan Aug 23 '17 at 4:20
  • $\begingroup$ @RossMillikan: Assuming independence: In R, 1-pbinom(28,50,.4)^10 returns 0.07361547, but 1-pbinom(27,50,.4)^10 returns 0.1492586. // Simulation of the exact model (using $50 \times 10$ arrays) should show dependence is quite weak. $\endgroup$ – BruceET Aug 25 '17 at 20:06

Extended and corrected comment. For the Problem as stated above independence is more important than I intended. (To simplify the posted problem, I reduced the number of boxes and the number of trials from the original applied problem, with unanticipated results.)

Assuming that boxes are independent does indeed give 28 as the 99th percentile for the maximum number $W$ of balls in the fullest box. However, a simulation of the actual situation described, shows that the 99th percentile of $W$ is 31, and that the correlation of the numbers of balls in two different boxes is about $r = -0.11.$

In the simulation below using R statistical software, the game is "played" 10,000 times. For each play of the game, the matrix MAT has $50$ rows (trials) and $10$ columns (boxes). Each element of the matrix is 1 or 0 according as the box received a ball on the relevant trial, or not. All rows add to 4.

set.seed(1776)  # change seed for different simulation
games = 10000;  w = r =  numeric(games)
for (k in 1:games) 
 trials=50;  boxes=10  
 MAT=matrix(rep(0, trials*boxes), nrow=trials)
 for (i in 1:trials) {
   MAT[i,] = sample(c(1,1,1,1,0,0,0,0,0,0), boxes) } 
 w[k] = max(colSums(MAT))
 r[k] = cor(MAT[,1],MAT[,2]) 
quantile(w, .99)
## 99% 
##  31 
## -0.1139328

Repeated simulations gave exactly 31 for the 99th percentile of $W,$ and very nearly an average correlation of -0.11 between the contents of the first and second columns. The figure below shows the simulated distribution of $W.$

enter image description here

Thanks to @MichaelSiefert and @RossMillikan for helpful discussions of this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.