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-2}C

_{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.

## No comments:

Post a Comment