Pascal's Modified Triangle

Well, time to post the solution to the coins in a bucket problem. First, just to get an idea of how I got to the solution, consider the answer in the case where the coins go into the bucket randomly, with 50/50 chance, rather than that weird weighted probability that was actually used in the problem. Let P(n,m) represent the probability that you arrive in the situation where there are n coins in the left bucket and m coins in the right bucket. P(1,1) is clearly 1. Next P(2,1) and P(1,2) are both easily found as 1/2. Then P(3,1) and P(1,3) are 1/4, since you must first get to (2,1) or (1,2) and then there is a 1/2 chance that the coin goes in the right place, while P(2,2) is 2/4, as the probabilities must sum to 1.

You basically wind up writing out Pascal's triangle, normalized so that the sum of the elements in any row comes out to 1. P(n,m) will be _n+m-2C_n-1/2^n+m-2. Each element of P(n,m) is the average of the two above it.

Now, in the case of the actual problem, we will still let P(n,m) denote the probability that you arrive in the situation where there are n coins in the left bucket and m coins in the right bucket. As before, P(n,m)=P(m,n), and the sum over all values of n and m such that n+m is held constant should be &Sigma P(n,m)=1.

So, as before P(1,1)=1 and P(2,1)=P(1,2)=1/2. Now, to get to (3,1) you must be at (2,1) and there is a 2/3 chance the coin goes in the right place. So P(3,1)=2/3*P(2,1)=1/3 also P(1,3)=1/3 by symmetry, and by normalization P(2,2)=1/3. Next, for (4,1), you must be first at (3,1) and then there is a 3/4 chance the coin falls into the right place, so P(4,1)=3/4*P(3,1)=1/4 and P(1,4)=1/4 so by normalization and symmetry we must also have P(3,2)=P(2,3)=1/4. So, our triangle has 1, then 1/2,1/2, then 1/3,1/3,1/3 and then 1/4,1/4,1/4,1/4.

Weird, it appears that P(n,m) depends only on n+m and not on the particular values. All distributions of n and m are equally likely across constant n+m. Let us try to prove the guess P(n,m)=1/(n+m-1). We know that this is true for n+m equal to any of {2,3,4}. P(n,m) must obey the relation:

P(n,m)=(n-1)/(n+m-1) P(n-1,m) + (m-1)/(n+m-1) P(n,m-1)

The first term is the chance you got to (n,m) by a coin falling into the left from (n-1,m) and the second is from a coin falling into the right from (n,m-1). Now we can prove our general formula for P(n,m) by induction on n+m. Assume it holds true for n+m=K, then for n+m=K+1

P(n,m)=(n-1)/(n+m-1)*1/(n+m-2) + (m-1)/(n+m-1)*1/(n+m-2)
P(n,m)=1/(m+n-1)

Alright, so for the 1000 coin case, the 999 differet cases (1,999), (2,998), (3,997),.....(998,2), (999,1) are all equally likely. So the bucket with less coins has any of {1,2,3,...499} coins with probability 2/999 and 500 coins with probability 1/999. The solution is then

2/999*&Sigma n +1/999*500
=(2/999)*(499*500/2)+500/999
=500^2/999
=250+250/999

Slightly more than 250. It would be 250.5 if not for the fact that 500 coins in the lesser bucket is slightly less likely.