Banach Matchbox Problem

Date: 10/31/98 at 00:30:44
From: Patel Akshay
Subject: Probability

Mr. Stephan kept two matchboxes, one in each pocket. Each box 
contained exactly n matches. Whenever he wanted a match he reached at 
random into one of his pockets. When he found that the box he picked 
was empty, what is the probability that the other one has exactly k 
matches (k = 0, 1, 2,......n)?

My approach to this example:

There are two cases possible:

 (1) both are empty
 (2) one is empty and other is full 

For second case the probability of getting k matches out of n is k/n, 
but as we have two pockets there are two different possibilities.  
Either the left is empty or the right is empty. So to cover both cases 
I just multiplied the answer by 2 and got 2(k/n).

But I think my answer is wrong, so I want your help for this example. 

Thank You.

Date: 10/31/98 at 10:43:14
From: Doctor Anthony
Subject: Re: Probability

This is a classic problem, sometimes called the Banach Matchbox 
problem. Note that the least number of 'trials' is n+1 and the maximum 
number is 2n+1.

Suppose p = the probability that he uses the lefthand pocket and 
q = the probability that he uses the righthand pocket. Then:

   Prob(k=n) = C(n+1,n+1)p^(n+1) q^0 + C(n+1,n+1)p^0 q^(n+1) 
             = p^(n+1) + q^(n+1) 
             = 2(1/2)^(n+1)       if p = q = 1/2
             = (1/2)^n

If he has used 1 match from the other box, then during the first n+1 
occasions he must have chosen n matches from one box and 1 match from 
the second box. Then on the n+2 nd occasion he returns to the empty 
box.

The probability of this is:

   Prob(k=n-1) = C(n+1,n)p^n q p + C(n+1,n)p q^n q  
               = 2 C(n+1,n)(1/2)^(n+2)  if p = q = 1/2
               = C(n+1,n)(1/2)^(n+1)
               = (n+1)(1/2)^(n+1)

If he has used 2 mmatches from the other box, then during the first n+2 
occasions he must have chosen n matches from one box and 2 matches from 
the second box. Then on the n+3 rd occasion he returns to the empty 
box.

The probability of this is:

   Prob(k=n-2) = C(n+2,n)p^n q^2 p + C(n+2,n)p^2 q^n q  
               = 2 C(n+2,n)(1/2)^(n+3)   if p = q = 1/2
               = C(n+2,n)(1/2)^(n+2)
            

The pattern is now clear:

   P(k=n-r) = C(n+r,n)(1/2)^(n+r)  
  
So if we want the answer in terms of k we replace r by n-k in this 
expression:

   P(k matches in other box) = C(n+n-k,n)(1/2)^(n+n-k)
                             = C(2n-k,n)(1/2)^(2n-k)      

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/