GS 2001/Math - Collins
Lab 10
Markov Processes and Transition Matrices

In this lab you will create some transition matrices and use
MATLAB to study how the probability distribution changes over time.

Simple Dice Game

Here's a simple game one person can play:
  Roll a single die getting the numbers 1 thru 5 in order, if you 
  roll a 6 before you get to 5, you have to start over.

Here's how to set up the transition matrix:
  There are 6 states you can be in: have nothing, have 1, 2, 3, 4, 5.
  Let's number these 0, 1, 2, 3, 4, 5.
  Then until you get to 5, you have a 1/6 chance of moving to the
  next state and a 1/6 chance of going back to 0.  Thus the
  transition matrix looks like:
        0    1    2    3    4    5
    0  5/6  1/6  1/6  1/6  1/6   0
    1  1/6  4/6   0    0    0    0
    2   0   1/6  4/6   0    0    0
    3   0    0   1/6  4/6   0    0
    4   0    0    0   1/6  4/6   0
    5   0    0    0    0   1/6   1

  Enter this in MATLAB, call it T  (don't enter the indices 0-5)
  To check it type sum(T) you should get all 1s.

  Let P = [1; 0; 0; 0; 0; 0] this is your starting distribution.
  You can also create it by P = zeros(6,1); P(1) = 1;

  Now if you type T*P you get the distribution after one turn.
  If you type T^2*P you get the distribution after two turns.
  If you type T^3*P you get the distribution after three turns.

Questions: (Either e-mail the answers to me, or hand them in)

     1. What is the probability that you will be back at 0 after 3 turns?
     2. What is the probability that you will be back at 0 after 10 turns?
     3. What is the probability that you have reached 5 after 10 turns?
     4. What is the average score obtained after 10 turns? (Expected Value)
     5. How many turns before the probability that you have reached 5
        exceeds 1/2?

Two Player Dice Battle

This is the game we played in class.
   There are 2 players, A and B.  For each round, each rolls a dice, 
   if A rolls a number greater than or equal to B then A wins.  
   Otherwise B wins.  The first to get 3 wins is the winner.

Building the transition matrix:  
   List all the possible states the game could be in.  
      For example, you start with A having 0 wins and B having 0 wins 
      (write as (0,0)), at some time A could have 2 wins and B have 1 
      win (write as (2,1)).

   Number the states from 1 to N, where N is the number of states.

   Build the matrix T (it will be NxN).  Use the probabilities we
   determined in class and your numbering of the states to fill in
   the values.  Remember that a winning state (either player has 3
   wins) is an absorbing state.

   I'd suggest you put it in a m-file "dice.m" and start it like:
      N = 
      T = zeros(N);    % starts T out as an NxN matrix of zeros
      % 1 = (0,0)      % list what all the states are
      % 2 = ..
      %
      % N = ..
      T( , ) =         % fill in all the non-zero values


      
  You could also enter T as
      T = [0 0 0 ... 0 0  whatever
                             more stuff
                            
                             ];

   Each column (except for winning states) should have 2 entries:
   one if A wins and one if B wins.

   To check your result, type dice and then
   type sum(T) to see if it is all 1s.

Questions: (Either e-mail the answers to me, or hand them in)

    1. What is the probability of being at (2,0) after 2 rounds?
       (0,2)?  How about (3,0) after 3 rounds?   
    2. What is the probability of being down (0,2) and then winning (3,2)?
    3. How many rounds do you have to play before you are guaranteed 
       to have a winner?
    4. What is the probability that A wins?
    5. What is the expected number of rounds before there is a winner?

E-mail: ccollins@math.utk.edu

ccollins@math.utk.edu
Last Modified: July 5, 2001