Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Probability
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search