##### Exercise10

This exercise will analyze the board game Chutes and Ladders, or at least a simplified version of it.

The board for this game consists of 100 squares arranged in a $$10\times10$$ grid and numbered 1 to 100. There are pairs of squares joined by a ladder and pairs joined by a chute. All players begin in square 1 and take turns rolling a die. On their turn, a player will move ahead the number of squares indicated on the die. If they arrive at a square at the bottom of a ladder, they move to the square at the top of the ladder. If they arrive at a square at the top of a chute, the move down to the square at the bottom of the chute. The winner is the first player to reach square 100.

1. We begin by playing a simpler version of this game with only eight squares laid out in a row as shown in Figure 13 and containing neither chutes nor ladders. Rather than a six-sided die, we will flip a coin and move ahead one or two squares depending on the result whether we have heads or tails. If we are on square 7, we move ahead to square 8 regardless of the coin flip, and if we are on square 8, we will stay there forever.

Construct the $$8\times8$$ matrix $$A$$ that records the probability that a player moves from one square to another on one move. For instance, if a player is on square 2, there is a 50% chance they are on square 3 and a 50% chance they are on square 4 at the end of the next move.

Since we begin the game on square 1, the initial vector $$\xvec_0 = \evec_1\text{.}$$ Generate a few terms of the Markov chain $$\xvec_{k+1} = A\xvec_k\text{.}$$

What is the probability that we arrive at square 8 by the fourth move? By the sixth move? By the seventh move?

2. We will now modify the game by adding one chute and one ladder as shown in Figure 14.

Even though there are eight squares, we only need to consider six of them. For instance, if we arrive at the first white square, we move up to square 4. Similarly, if we arrive at the second white square, we move down to square 1.

Once again, construct the $$6\times6$$ stochastic matrix that records the probability that we move from one square to another on a given turn and generate some terms in the Markov chain that begins with $$\xvec_0=\evec_1\text{.}$$

1. What is the smallest number of moves we can make and arrive at square 6? What is the probability that we arrive at square 6 using this number of moves?

2. What is the probability that we arrive at square 6 after five moves?

3. What is the probability that we are still on square 1 after five moves? After seven moves? After nine moves?

4. After how many moves do we have a 90% chance of having arrived at square 6?

5. Find the steady-state vector and discuss what this vector implies about the game.

One can analyze the full version of Chutes and Ladders having 100 squares in the same way. Without any chutes or ladders, one finds that the average number of moves required to reach square 100 is 29.0. Once we add the chutes and ladders back in, the average number of moves required to reach square 100 is 27.1. This shows that the average number of moves does not change significantly when we add the chutes and ladders. There is, however, much more variation in the possibilities because it is possible to reach square 100 much more quickly and much more slowly.

in-context