
Columns Balls and Probability
Posted:
Jul 20, 2008 8:50 PM


I'm going out on a limb here, to see if anyone can help me or point me into the correct direction:
The problem is simple, but very hard to answer as we make some of the numbers bigger. Lets start of with a simple example:
In this problem, I have Columns, that are hollow, like pipes, and they have space in them for 2 balls. I can represent them with a 2 x 2 matrix when empty,
[ 0 , 0 ] [ 0 , 0 ]
and full
[ 1 , 1 ] [ 1 , 1 ]
The problem comes, is determining the probability of "filling" up a column or tube when a ball is placed randomly, The only information that we keep after each ball is placed in, is how many we have previously placed.
This 2 x 2 example is incredibly easy. Here it is as follows, Let f(N) = the probability that a ball will fill a column, where N is the number of balls previously in the array.
f(0) = 0% [ 0 , 0 ] [ 0 , 0 ] <= if a ball goes it, it cant fill up a column
f(1) = 50% [ 0 , 0 ] [ X , X ] <= the ball has a 50/50 chance of landing on another ball f(2) = 100%
[ 0 , 0 ] [ 1 , 1 ] <= no matter where the ball goes, it will always fill up a column
Lets expand this out, to a 2x3 [ 0 , 0 , 0 ] [ 0 , 0 , 0 ]
This is straight forward as well. f(0) = 0% f(1) = ~33% f(2) = ~67% f(3) = 100%
Thus for a 2 deep column the equation looks something like this f(N) = N/X where X is the number of columns.
I get stuck, where the column dept increases beyond 2, to 3, or 4
Thus for a 3x4 [ 0 , 0 , 0 , 0 ] [ 0 , 0 , 0 , 0 ] [ 0 , 0 , 0 , 0 ]
I get lost here... Can anyone help me or point me in the right direction?
PS I did some calcs by hand, and for a 3x4 to get you started looks something like this <c = total possible combinations> f(0) = 0% <1> f(1) = 0% <4> f(2) = 10% <10> f(3) = 18.75% <16> f(4) = ~31.5789474% <19> f(5) = 43.75% <16> f(6) = 60% <10> f(7) = 75% <4> f(8) = 100% <1>
This was just done with lots and lots of counting, and a little bit of deduction.

