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/stats formally was in university, a good 7-10 years ago. My limited memory/understanding of combinatorics+probability 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.

  • 2
    $\begingroup$ By 'randomly placed' do you mean 'with equal probability', among those with space for at least one more ball? $\endgroup$ – Glen_b Aug 14 '14 at 5:10
  • $\begingroup$ Yes, placed with equal probability among all buckets that are not yet filled. $\endgroup$ – Matthew King Aug 14 '14 at 5:34
  • 1
    $\begingroup$ This is a totally rad problem. $\endgroup$ – Brash Equilibrium Aug 14 '14 at 7:08
  • 1
    $\begingroup$ I agree with your simulation estimate (I get a little over 18.5% in a few million simulations). $\endgroup$ – Glen_b Aug 14 '14 at 9:45

Write the problem as a Markov chain with nodes representing the different states of the system: how many balls are in each bucket (considering that you can exchange the first two buckets):

(0, 0, 0, 0), (0, 1, 0, 0), (0, 2, 0, 0), (1, 1, 0, 0), (1, 2, 0, 0), (2, 2, 0, 0), …

I think there are 48 important states.

Calculate the edge probabilities of going from one state to another. Then, calculate the probability of hitting state (2,2,3,1) by iteratively filling the probabilities of arriving at the other 47 states. In computer science, this technique is called dynamic programming.


P(0,0,0,0) = 1
P(0,1,0,0) = 1/4
P(1,1,0,0) = 1/4 P(1,0,0) + 1/4 P(0,1,0) = 1/8


| cite | improve this answer | |

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.