A Markov Chain Example

Date: 07/01/98 at 10:20:50
From: Wolfgang Hoschek
Subject: Given P pots with N balls each, take B balls out of them, how 
many pots do we touch?

Hello. I am stuck on the following question:

Charley has P pots. In each pot there are N balls. He randomly chooses 
a pot that is not empty, takes one ball out of it, and throws it out 
of the window. Charley continues choosing and throwing away balls 
until B balls have been taken out.

How many pots did Charley touch on average?

If you could possibly give me a little help to get started on this, I 
would appreciate it a lot.  

Thank you,
Wolfgang

Date: 07/03/98 at 18:15:49
From: Doctor Pat
Subject: Re: Given P pots with N balls each, take B balls out of them, 
how many pots do we touch?

Wolfgang,

I do not know a solution to your problem, in general, but because it 
is almost the reverse of a problem I have been working on for a while, 
and because no one has answered this in a few days, I will tell you an 
approach to individual problems of a specific subset of your problem.  

If the number of balls in each pot, N, is greater than the number 
to be removed in all, B, then the problem is one of sampling from a 
set of P objects with replacement. For this part of the problem you 
can ignore N and work with P objects and sample B of them "with 
replacement."

I do this for small numbers by the use of Markov matrix methods. If 
you think of the number of pots you have sampled from so far as the 
state of the experiment, then you are always in state 1 after one 
draw. The matrix provides an array of probabilities that you move from 
one state to another. Powers of the matrix then provide the 
probabilities of being in any state after (power + 1) samples.   

Here is a simple one for P = 5 pots and drawing out B = 6 balls 
(remember that there must be N >= 6 balls in each pot).
   
The transition matrix looks like:

   1/5    4/5     0     0     0
    0     2/5    3/5    0     0
    0      0     3/5   2/5    0
    0      0      0    4/5   1/5
    0      0      0     0     1

The fifth power of this gives us the probable state after six draws 
and the first row (which is all we really want) would look like this:

   .00032  .03968    .3456   .4992   .1152

These are the probabilities that we have finished with only touching 
one pot (.00032) or two pots (.03968) or three pots (.3456) etc.  
   
To find the expected average we simply multiply .0032 x 1, .03968 x 2, 
up to .1152 x 5, and then add them up. The expected average for 
drawing six balls from five pots is then 3.68928 pots.
   
I wish I could give you a more general solution. I hope this helps.  
If you find out more, drop me a note, as anything you figure out about 
this problem will help me with mine.  

- Doctor Pat, The Math Forum
Check out our web site! http://mathforum.org/dr.math/