In this module we develop another way of looking at games and models like the game we studied in the last module. This approach, called Markov Chains, is a very nice example of the use of vectors and matrices. It is, however, possible to use this approach without using vectors or matrices. Markov chains are named after Andrei Adreyevich Markov. A brief biographical sketch of Markov is available at the MacTutor History of Mathematics Archive.

Recall the game we described in the last module.

• A player throws two dice.
  • If the result is 7 she wins and the game is over.
  • If the result is 2 she loses and the game is over.
  • If the result is neither 7 nor 2 then the game continues below. The result of this first throw is called the player's point

• The player throws the dice again.
  • If the result is the same as the first throw -- that is, if the player "makes her point" then she wins and the game is over.
  • If the result is 7 then the player loses and the game is over.
  • If the result is neither the player's point nor 7 then the game continues. This step is repeated over and over again until the player either makes her original point and wins or rolls a 7 and loses.

You can try the game by clicking here to open a new window with a Java applet. Arrange the windows as usual -- overlapping, so that it is easy to move back-and-forth between the two windows by clicking on the exposed portion of the inactive window to make it active. Because the new window can be very thin, if you have a large monitor you may be able to arrange the two windows so that they both fit on your screen without overlapping.

When the applet begins there are twelve lines indicating twelve possible situations. Notice there is a red dot next to the words "about to start." This indicates that the game has not yet begun.

At the bottom of the applet are two blank dice. Click on these dice to simulate the first throw of the dice. You will see the result of the first throw of the dice. Notice the red dot moves from its former position to the new state of play. Click on the dice to simulate the next throw of the dice. Notice that once again the red dot moves to the new current state of play. Of course, after the first roll of the dice, each roll may result in a win or a loss or the player may remain in the same state. If the player remains in the same state the red dot doesn't actually move; it just stays put. Continue "rolling the dice" until the player either wins or loses.

You can begin a new game at any time by clicking on the words "about to start."

If we look in on the game then there are twelve different situations or states that we might see.

1. The game is about to begin. The player has not yet thrown the dice for the first time.

2. The player has won -- she threw a 7 on the first throw or made her point on a subsequent throw.

3. The player has lost -- she threw a 2 on the first throw or a 7 on a subsequent throw.

4. The player threw a 3 on the first throw and is ready to make a subsequent throw. Her "point" is 3.

5. The player threw a 4 on the first throw and is ready to make a subsequent throw. Her "point" is 4.

6. The player threw a 5 on the first throw and is ready to make a subsequent throw. Her "point" is 5.

7. The player threw a 6 on the first throw and is ready to make a subsequent throw. Her "point" is 6.

8. The player threw a 8 on the first throw and is ready to make a subsequent throw. Her "point" is 8.

9. The player threw a 9 on the first throw and is ready to make a subsequent throw. Her "point" is 9.

10. The player threw a 10 on the first throw and is ready to make a subsequent throw. Her "point" is 10.

11. The player threw a 11 on the first throw and is ready to make a subsequent throw. Her "point" is 11.

12. The player threw a 12 on the first throw and is ready to make a subsequent throw. Her "point" is 12.

As the game is played, the player moves from one state to another. She always starts in state 1. What happens after that depends on the throws of the dice. For example, if her first throw was a 4, she would move to state 5. Then if the next throw was a 9 should would remain in state 5. Then if the next throw was a 7 she would move to state 3.

We are interested in the probability that she finds herself in each state at each time of the game. We keep track of these probabilities with a sequence of vectors

Each of these vectors has twelve entries, one entry for each of the twelve states. Each entry in the vector p_n is a number between zero and one that gives the probability that the player is in the corresponding state after n tosses of the dice. The sum of the entries is always one because the player must be in one of the 12 states. These vectors are called probability vectors.

The vector p₀ gives the probability of each state after zero throws of the dice -- that is, before the game begins. Thus, the player must be in state 1 and

This vector is called the initial probability vector.

Next we want to determine the probability vector p₁ that gives us the probabilities of each state after the first throw of the dice.

The first entry is easy -- it gives us the probability that after one throw of the dice the player is in state 1. But state 1 is the state before the game begins, so after one throw of the dice this entry is zero.

Click here to open a new window with a Java applet that can help you determine the remaining entries in this vector. Arrange these two windows so that they overlap and you can move easily between the two windows by clicking on the exposed portion of the inactive window to make it active. The Java applet shows the 36 possible results when two dice are thrown. If you click on any one of the results then all the results with the same total turn pink. Notice, for example, there is only one result -- one on both dice -- that totals 2 but there six possible combinations that total 7.

Now the second entry in the vector p₁ indicates the probability that after the first throw of the dice the player is in state 2 and has won. This happens when the first throw of the dice is a seven. Click on any combination of dice whose sum is seven in the applet. Notice that there are a total of six combinations whose sum is seven. Thus the probability of being in state 2 after one throw of the dice is 6/36.

Fill in the remaining entries in the vector p₁.

answer

In order to determine the probability that the player eventually wins the game, we begin by determining the probability of moving from each state to each state on each throw of the dice. We record these probabilities in a table like the table below, which is only partially filled out. We read this table as follows.

• To find the probability of moving from state j to state i begin by locating column j.

• Then locate row i.

• The entry in column j and row i is the probability of moving from state j to state i

For example, the probability of moving from state 1 to state 3 is, according to the table below, 1 / 36.

                                              From State

                1      2      3      4      5      6      7      8      9     10     11     12

To

State  1 |      0

State  2 |   6/36

State  3 |   1/36

State  4 |   2/36

State  5 |   3/36

State  6 |   4/36

State  7 |   5/36

State  8 |   5/36

State  9 |   4/36

State 10 |   3/36

State 11 |   2/36

State 12 |   1/36

• Fill in the remaining entries in this table.

  answer

• Notice that the entries in each column add up to one. Explain why.

A table like this is often called a matrix. We use the notation a_{i, j} for the entry in the i-th row and the j-th column -- that is, for the probability of moving from state j to state i. We use the notation A to represent the entire matrix.

We will use this table, or matrix, to determine the vector p_{n + 1} from the vector p_n. First, we need some notation for the entries of the vectors p_n and p_{n + 1}. Let

The entry s_j is the probability of being in state j after n throws of the dice. The entry t_i is the probability of being in state i after one more throw of the dice. Thus,

   ti = ai,1 s1 + ai,2 s2 + ai,3 s3 +  ai,4 s4 +  
        ai,5 s5 + ai,6 s6 + ai,7 s7 +  ai,8 s8 +  
        ai,9 s9 + ai,10 s10 + ai,11 s11 +  ai,12 s12 

Notice the sum on the right hand side above has 12 terms. Each term represents the throws in which a player enters state i from one of the 12 states. Consider, for example, the first term

This term is the product of two factors. The first factor, a_{i, 1} is the probability that if you are in state 1 you will move to state i. The second factor, s₁, is the probability that you are in state 1. The product represents those throws of the dice in which you start at state 1 and move to state i.

The formula

   ti = ai,1 s1 + ai,2 s2 + ai,3 s3 +  ai,4 s4 +  
        ai,5 s5 + ai,6 s6 + ai,7 s7 +  ai,8 s8 +  
        ai,9 s9 + ai,10 s10 + ai,11 s11 +  ai,12 s12 

is exactly the formula used to compute the matrix product

Your CAS window describes how to work with this situation either with or without linear algebra. This is a good example of the power of linear algebra (vectors and matrices) but it is possible to study this game without linear algebra.

Use your CAS window to answer the following questions.

• What is the probability that a player wins the game we have been discussing? Compare your answer with the answer you obtained in the last module using simulation.

• Suppose the game was played with two four-sided dice. With four-sided dice the most likely result is 5, so 5 is used wherever 7 was used in the original game. How likely is the player to win with two four-sided dice? Compare your answer with the answer you obtained in the last module using simulation.

• Suppose the game was played with two twelve-sided dice. With twelve-sided dice the most likely result is 13, so 13 is used wherever 7 was used in the original game. How likely is the player to win with two twelve-sided dice? Compare your answer with the answer you obtained in the last module using simulation.

• Use the method we developed in this module to find the probability that a timid roulette player wins. Compare your answer with the answer you obtained earlier using simulation.