Our Group Members

Ben Rahn
Janel Krenz
Lori Naiberg
Chad Seichter
Kyle Colden
Ivan Lau
Mr. Markov Plays Chutes and
Ladders
I. Introduction
II. The Concept of a Markov Chain
III. The Chutes and Ladders Transition Matrix
IV. Simulation Techniques
V. Repeated Play
VI. Conclusion

Introduction
How the Game is Played
Chutes and Ladders is a board game where players
spin a pointer to determine how they will advance
The board consists of 100 numbered squares
The objective is to land on square 100
The spin of the pointer determines how many
squares the player will advance at his turn with
equal probability of advancing from 1 to 6 squares
However, the board is filled with chutes, which
move a player backward if landed on
There are also ladders, which advance a
player
Chutes have pictures of bad behavior which
leads to disasters
Ladders have pictures of good behavior
leading to rewards
Most of the chutes and ladders produce
relatively small changes in position, but
several produce large gains or losses


The Concept of a
Markov Chain
Topics Covered
Transition matrix
Probability vectors
Absorbing vs. non-absorbing Markov
chains
Steady-state matrices


Markov Chains
A Markov Chain is a weighted digraph
representing a discrete-time system that can be in
any number of discrete states
The transition matrix for a Markov chain is the
transpose of a matrix of probabilities of moving
from one state to another
Pij = probability of moving from state i to j
Transition Matrix
Below, is the layout of the transition matrix for
Chutes and Ladders (101x101)

p0,0 p0,1 p0,100
p1,0 p1,1 p1,100
. . .
. . .
p100,0 p100, 1 . p100,100



Three properties which identify a state
model as being a Markov model:
1) The probability of moving from state i to j is
independent of what happened before moving to
state j and how one got to state i (Markov
assumption)
2) Sum of probabilities for each state must be one
3) X(t) = probability distribution vector of the
probability of the system being in each of the
states at time n
Probability Vector
The probability vector is a column vector in
which the entries are nonnegative and add
up to one
The entries can represent the probabilities
of finding a system in each of the states
Two types of Markov Chains
1) Absorbing Markov Chains
Can not get out of certain states
Once a system enters an absorbing
state, the system remains in that state
from then on
2) Non-absorbing Markov Chains
Can always get out of every state

Absorbing Markov Chains
(Chutes and Ladders)
Two conditions must be met for a Markov Chain
to be absorbing:
Must have at least one state which cannot be
left once it has been entered
It must be possible, through a series of one
or more moves, to reach at least one absorbing
state from every non-absorbing state (given
enough time, every subject will eventually be
trapped in an absorbing state)

Common Question
A common question arising in Markov-
chain models is, what is the long-term
probability that the system will be in each
state?
The vector containing these long-term
probabilities is called the steady-state vector
of the Markov chain
Steady-state matrix
The steady-state probabilities are average probabilities
that the system will be in a certain state after a large
number of transition periods
The convergence of the steady-state matrix is
independent of the initial distribution
Long-term probabilities of being on certain squares
m P
n
n


lim
The Chutes and
Ladders Transition
Matrix
Analytical Computation
Programming Language: Java
Objectives:
Compute the transition matrix
Compute the probability vectors
Techniques of Transition Matrix
How we did the analytic computations
2D array of integers of size 101 by 101
Each array entry represents a move from one square to
another
i.e. Pij represents the players move from position i to position j
A square with a ladder beginning in that square is considered a
pseudo-state and has a 0 probability of landing on it
A square with a chute beginning in that square is considered a
pseudo-state and also has a 0 probability of landing on it
Results of Transition Matrix
The matrix is way too large to show on this
slide
Some example probabilities computed:
If a player is on square 97, the probability of
staying on that square is 3/6 and the probability
of moving to square 78 is 1/6
Techniques of Probability
Vectors
How we did the analytic computations
1D array of integers of size 101
Probability vectors Vn represent the probability
of being on a certain square on move n
Vo = {1,0,0} and means that the probability
of being on square 0 is 1 or 100%
Vo * P = V1;
V1 * P = V2, etc.

Results of Transition Matrix
After 1000 moves, the probability vector
reached a limit of {0,0,1}
This means that after 1000 moves, the game
is expected to be won!!!
Simulation
Techniques
Simulation
Programming Language: C++
Objectives:
Find frequencies for being at each position
Find mean number of moves to win
Find standard deviation
Simulate a large number of games
Technique One
How we simulated the game
Array of 101 integers representing the board
Each array entry represented a state
Psuedo-states held the value at the end of the ladder
or the chute
i.e. Index 1 represented square 1 and held 38. If
index became 1 it would move to square 38.
Normal states held the index of that state. Index
would be compared to value and be the same so
index would stay at its value.
Technique One
When index became 100 game would be over.
If index was greater than 100 it would reset to
its previous. This repeats until index 100 is hit.
Mean and standard deviation were calculated
throughout the game.
Printed most moves to win and least moves.
Printed number of times each square was
landed on for 250,000 games and frequency of
each.
Technique One Results
We ran 250,000 games
Mean is approximately 39.65 moves to
reach square 100.
The standard deviation is approximately
24.00

Technique Two
Run the game as a non-absorbing.
i.e. If the index is 100 or above subtract 100 to
run the game as a non-ending board.
Calculate the frequency of landing on each
square.
This was done to compare to the non-
absorbing analytical model.

Repeated Play
Analytic Computation
Programming Language: Java
Objectives:
Compute the non-absorbing matrix
Compute the corresponding probability vectors

Techniques of Repeated Play
How we did the analytic computations:
Similar to transition matrix, except square 100
cannot be landed on
Instead, the player repeats back to the
beginning of the board (Similar to Monopoly)
The game cannot be won using this method
Comparison will be done to simulation results
Probabilities of landing on
certain squares After 1000 games
Theoretical Experimental
% 775 . 1
0
P
% 76 . 1
0
P
% 581 . 0
5
P
% 552 . 0
5
P
% 89 . 2
26
P
% 94 . 2
26
P
% 09 . 2
42
P % 13 . 2
42
P
% 573 . 0
65
P % 599 . 0
65
P
% 452 . 0
99
P % 441 . 0
99
P
Conclusion
The Theoretical Result and The
Experimental Result matched

The Markov Chain works in Chutes
and Ladders

A new look on Chutes and
Ladders
Chutes and Ladders is a game for 3-6
years old.

We can make it more interesting by
changing some rules
Drinking Chutes and Ladders

If you are interested in playing
Drinking Chutes and Ladders, come
to THE MARKET AT 10:00p.m.
tonight
See you there!!
Special Thanks to Dr. Deckelman for
all his help and pizzas
Sources
Mooney and Swift. A Course In
Mathematical Modeling. MAA
Publications, 1999.