Activities

Markov chains - pots, dice, ...

Pots

There are five pots each containing a large number of balls. A pot is chosen at random, a ball is removed and thrown away. This process is completed six times. Find the probability of only choosing one pot, two pots, three pots, four pots or five pots.

This problem is dealt with by Dr Math. An extract follows:
 

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

Dice problem

Now consider the problem of repeatedly throwing a six-face die.  Complete the following table showing the probability of throwing only one value, two values, three values, four values, five values or six values.

 
 
 

number
of
different
values
thrown
number of throws
 
1
2
3
4
5
6
7
8
9
1
1
                
2
0
                
3
0
                
4
0
                
5
0
                
6
0
                

Solutions

Cereal box problem

Suppose there was one of six prizes inside your favorite box of cereal.  Perhaps it's a pen, a plastic
movie character, or a picture card.  How many boxes of cereal would you expect to have to buy, to get all
six prizes? Is this the same as the dice problem?

Simulation and notes from MSTE

Cliff-Hanger

Homer Simpson stands on the edge of a cliff. One step would send poor Homer over the edge. He takes random steps, either toward or away from the cliff. At any step, the probability of taking a step away is 2/3 and the probability of a step toward the cliff 1/3.

Assume Homer is safe when he reaches 3 steps from the edge. What is the probability of him escaping?

Consider the number of steps from the edge (-1, 0, 1, 2, 3) as the five states of a Markov process. Use the transition matrix to answer the problem.

Investigate the effect of changing the 2/3 and 1/3 probabilities.

Simulation from MSTE