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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.