1
$\begingroup$

I'll start with a specific example of what I am trying to solve:

I have eight balls to be randomly placed into four buckets. Buckets #1-3 have the capacity of 2, 2, 3 respectively, while bucket #4 has an infinite capacity. A bucket can't be filled over its capacity. A ball will not be thrown to a bucket that is already full. I would like to calculate the probability that my eight balls will completely fill buckets #1-3.

The last time I studied maths formally was in university, a good 7-10 years ago. My limited memory/understanding of combinatorics is failing me. I'm a software guy, so I wrote a basic simulator for the problem, which seems to tell me that my eight balls will fill buckets #1-3 ~18% of the time. I'd like to understand how to approach the problem mathematically.

$\endgroup$
4
$\begingroup$

The capacities of each cell make this a tricky problem. The probability of reaching a given configuration depends on the sequence of cells selected. For example, throwing balls into cells 1,1,2, in that order, has probability $(1/4)^2(1/3)$ while 1,2,1 has probability $(1/4)^3.$ So determining equally likely outcomes is difficult. Instead we can solve using a Markov chain. Let the states of the chain be the vector of number of balls in the 4 cells after any number of balls have been thrown. We start in state $(0,0,0,0)$ and throw 8 balls, one by one, taking into account the capacities. After the first ball, we are in state $(1,0,0,0), (0,1,0,0), (0,0,1,0)$ or $(0,0,0,1)$. And they each have probability $1/4$ of occurring. Similarly, we must fill in a one-step transition matrix $P$ that gives the probability of moving from any state $(i,j,k,m)$ to any other after one more ball is thrown. With 8 balls thrown the capacities are: $2,2,3,8$ and so the number of states we need to consider is $3x3x4x9=324.$

We then compute the elements of the matrix $P$ of size 324x324 (mostly $0$). This was easy in Excel. Then we compute the power $P^8.$ The non-zero probabilities in row $(0,0,0,0)$ of $P^8$ tell us the probability of being at each given state after $8$ balls are thrown.

The results show that state $(2,2,3,1)$ has probability $0.1855$ and it is the most likely to occur. There are 36 states that can occur after 8 balls are thrown.

$\endgroup$
0
$\begingroup$

If the order does matter:

$$\text{Coefficient of $x^8$ in } \\8! \underbrace{(1+x+x^2/2!)^2}_{\text{bucket 1 & 2}} \underbrace{(1+x+x^2/2!+x^3/3!)}_{\text{bucket 3}} \underbrace{(1+x+x^2/2!+\cdots\infty)}_{\text{bucket 4}}$$ $$\small\text{Coefficient of $x^8$ in } \\\small8! \underbrace{\left(\frac{x^7}{24}+\frac{7\times x^6}{24}+\frac{13\times x^5}{12}+\frac{31\times x^4}{12}+\frac{25 x^3}{6}+\frac{9\times x^2}{2}+3 x+1\right)}_{\text{bucket 1,2 & 3}} \underbrace{(1+x+x^2/2!+\cdots\infty)}_{\text{bucket 4}}$$ $$=8!\left(\frac{1}{24}.\frac{1}{1!}+\frac{7}{24}.\frac{1}{2!}+\frac{13}{12}.\frac{1}{3!}+\frac{31}{12}.\frac{1}{4!}+\frac{25}{6}.\frac{1}{5!}+\frac{9}{2}.\frac{1}{6!}+\frac{3}{1}.\frac{1}{7!}+\frac{1}{1}.\frac{1}{8!}\right)$$ $$=20857$$ For $(2,2,3,1)$ there is:$$8!\left(\frac1{2!}\right)^2\left(\frac1{3!}\right)\left(\frac1{1!}\right)=1680$$ So probability is $1680/20857\approx8.05\%$


Note: I have considered order inside bucket irrelevant, for e.g. if you put $1$st ball in bucket $1$ then $2$nd ball in bucket $1$, this is same as $2$nd in bucket $1$ then $1$st in bucket $1$. Also if you wish to include that order too multiply the below result in $8!$, so that both numerator and denominator's $8!$ factor cancels and you'll get the same probability of $1/36$


If the order doesn't matter:

$$\text{Coefficient of $x^8$ in } \underbrace{(1+x+x^2)^2}_{\text{bucket 1 & 2}} \underbrace{(1+x+x^2+x^3)}_{\text{bucket 3}} \underbrace{(1+x+x^2+\cdots\infty)}_{\text{bucket 4}}$$ $$\text{Coefficient of $x^8$ in } \underbrace{(x^7+3 x^6+6 x^5+8 x^4+8 x^3+6 x^2+3 x+1)}_{\text{bucket 1,2 & 3}} \underbrace{(1+x+x^2+\cdots\infty)}_{\text{bucket 4}}$$ $$=1+3+6+8+8+6+3+1=36$$ Numerically these correspond to: $$\begin{array}{|c|c|}\hline \text{No. of balls in bucket }(1+2+3)&\text{ways}&\text{#ways}\\\hline 0&(0,0,0)&1\\ 1&(0,0,1)\times3&3\\ 2&(0,1,1)\times3+(0,0,2)\times3&6\\ 3&(0,1,2)\times6+(0,0,3)+(1,1,1)&8\\ 4&(0,1,3)\times2+(0,2,2)\times3+(1,1,2)\times3&8\\ 5&(0,2,3)\times2+(1,2,2)\times3+(1,1,3)&6\\ 6&(1,2,3)\times2+(2,2,2)&3\\ 7&(2,2,3)&1\\\hline &**Sum**&36\\\hline \end{array}$$ Corresponding to each there exist only one way in bucket $4$. So probability is $1/36\approx2.77\%$

$\endgroup$
  • 1
    $\begingroup$ Thanks for the answer, Aditya. This was my first thought, too, but I think that @Happytreat is correct in that order counts. Algorithmic simulation indicates that buckets 1-3 will be filled with a probability of greater than 1/36. $\endgroup$ – Matthew King Aug 14 '14 at 6:54
  • $\begingroup$ @MatthewKing edited the answer $\endgroup$ – RE60K Aug 14 '14 at 7:38

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.