probability of number of balls in a bin

Question

Suppose we throw 180 balls into 10 bins, choosing a random a bin independently from previous throws. What's the probability that some bin has k balls or more?

Answer 1

You can do this using inclusion–exclusion.

Say you have $n=180$ balls and $m=10$ buckets.

If the probability for $j$ particular buckets to contain $k$ or more balls is $p_j$, then by inclusion–exclusion the probability for at least one bucket to contain $k$ or more balls is

$$ \sum_{j=1}^m(-1)^{j+1}\binom mjp_j\;. $$

We have

$$ p_1=m^{-n}\sum_{i=k}^n\binom ni(m-1)^{n-i}\;, $$

$$ p_2=m^{-n}\sum_{i_1=k}^n\sum_{i_2=k}^n\binom n{i_1,i_2}(m-2)^{n-i_1-i_2}\;, $$

$$ p_3=m^{-n}\sum_{i_1=k}^n\sum_{i_2=k}^n\sum_{i_3=k}^n\binom n{i_1,i_2,i_3}(m-3)^{n-i_1-i_2-i_3}\;, $$

and so on. For $k=24$, a case you were interested in, this yields

\begin{eqnarray*} p_1&\approx&8.962965\cdot10^{-2}\;,\\ p_2&\approx&5.137713\cdot10^{-3}\;,\\ p_3&\approx&1.566055\cdot10^{-4}\;,\\ p_4&\approx&1.843512\cdot10^{-6}\;,\\ p_5&\approx&4.496161\cdot10^{-9}\;,\\ p_6&\approx&5.274765\cdot10^{-13}\;,\\ p_7&\approx&1.965299\cdot10^{-20}\;,\\ p_8&=&p_9=p_{10}=0\;,\\ \end{eqnarray*}

and thus the probability for at least one bucket to contain $24$ or more balls is

$$ \sum_{j=1}^m(-1)^{j+1}\binom mjp_j\approx0.683506\;. $$

The exact number of favourable results out of the $10^{180}$ possible results is

683506088319267176075812493611972506717354414439467258046005070314955639642255566511980636893571539150511657874914743568360842020841283776523218664781531830516427726070368000000000.

Interestingly, my first attempt at verifying this with simulations failed and was off by about $0.001$. It turned out that this was due to regularities in Java's built-in pseudorandom number generator; the discrepancy was resolved when I used an XOR shift generator instead.

Here's the Java code for the evaluation of the sums and the simulation.

Answer 2

When you say "uniform distribution," I think you mean instead a Poisson distribution. Here the expected number of balls in each bucket is $180/10 = 18$. Here is the distribution of balls in any given bucket:

The probability that a given (single) bucket has more than $k$ such balls is:

$$\frac{\Gamma (\lfloor k\rfloor +1)-\Gamma (\lfloor k\rfloor +1,18)}{\Gamma (\lfloor k\rfloor +1)}$$

which has a form:

So the chance that a single bucket does not have more than $k$ balls is:

$$q = 1 - \frac{\Gamma (\lfloor k\rfloor +1)-\Gamma (\lfloor k\rfloor +1,18)}{\Gamma (\lfloor k\rfloor +1)}$$,

and the chance that none of the 10 buckets has more than $k$ is $q^{10}$, so the chance that at least one of the buckets has more than $k$ is $1 - q^{10}$.

Note that this is under the assumption that on average 180 balls are thrown, not precisely the stated assumptions. For example, if 180 are thrown, then it is certain that at least one bucket will have 18 or more balls.

Answer 3

However, when it comes to labelled balls, an e.g.f. is waiting somewhere to be written.

Assume that the capacity of a bucket is 23. Then the e.g.f. for one bucket is:

$ 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots + \frac{x^{23}}{23!} $

for ten distinct buckets one will have :

$ (1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots + \frac{x^{23}}{23!})^{10} $

We are now interested in the coefficient of $\frac{x^{180}}{180!}$, which agrees with previous calculus.

316493908895554453369790961313619572009615365012907112082570161990794872355520000505402092717575252190566769024926332221764288309486803949091940966173304490507414724761824000000000

The probability not to spill something is then 0.3164934.