A game of snakes and ladders or any other game whose moves are determined entirely by dice is a Markov chain.
Table of contents |
|
The probabilities of weather conditions, given the weather on the preceding day,
can be represented by a transition matrix:
(P)i j is the probability that, if a given day is of type i, it will be
followed by a day of type j.
Notice that the columns of P sum to 1: this is because P is a stochastic matrix.
The weather on day 0 is known to be sunny. This is represented by a vector in which the "sunny" entry is 100%, and the "rainy" entry is 0%:
The weather on day 2 can be predicted in the same way:
In this example, predictions for the weather on more distant days are increasingly
inaccurate and tend towards a steady state vector. This vector represents
the probabilities of sunny and rainy weather on all days, and is independent
of the initial weather.
The steady state vector is defined as:
Since the q is independent from initial conditions, it must be unchanged when transformed by P. This makes it an eigenvector (with eigenvalue 1), and means it can be derived from P. For the weather example:
A very simple weather model
The matrix P represents the weather model in which a sunny day is 90%
likely to be followed by another sunny day, and a rainy day is 50% likely to
be followed by another rainy day. The columns can be labelled "sunny" and
"rainy" respectively, and the rows can be labelled in the same order. Predicting the weather
The weather on day 1 can be predicted by:
Thus, there is an 90% chance that day 1 will also be sunny.
General rules for day n are:Steady state of the weather
but only converges if P is a regular transition matrix (that is, there
is at least one Pn with all non-zero entries).
Set s = q2, so 5 s = q1. We want
s + 5 s = 1: therefore s = 0.167. Our steady state vector is:
In conclusion, in the long term, 83% of days are sunny.