From TheBestLinks.com
This page contains examples of Markov chains in action.
A game of snakes and ladders or any other game whose moves are determined entirely by dice is a Markov chain.
A very simple weather model
The probabilities of weather conditions, given the weather on the preceding day,
can be represented by a transition matrix:
- <math>
P = \begin{bmatrix}
0.9 & 0.5 \\
0.1 & 0.5
\end{bmatrix}
<math>
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.
(P)i j is the probability that, if a given day is of type j, it will be
followed by a day of type i.
Notice that the columns of P sum to 1: this is because P is a stochastic matrix.
Predicting the weather
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%:
- <math>
\mathbf{x}^{(0)} = \begin{bmatrix}
1 \\
0
\end{bmatrix}
<math>
The weather on day 1 can be predicted by:
- <math>
\mathbf{x}^{(1)} = P \mathbf{x}^{(0)} = \begin{bmatrix}
0.9 & 0.5 \\
0.1 & 0.5
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix}
= \begin{bmatrix}
0.9 \\
0.1
\end{bmatrix}
<math>
Thus, there is an 90% chance that day 1 will also be sunny.
The weather on day 2 can be predicted in the same way:
- <math>
\mathbf{x}^{(2)} = P \mathbf{x}^{(1)} = P^2 \mathbf{x}^{(0)}
= \begin{bmatrix}
0.9 & 0.5 \\
0.1 & 0.5
\end{bmatrix}^2
\begin{bmatrix}
1 \\
0
\end{bmatrix}
= \begin{bmatrix}
0.86 \\
0.14
\end{bmatrix}
<math>
General rules for day n are:
- <math>
\mathbf{x}^{(n)} = P \mathbf{x}^{(n-1)}
<math>
- <math>
\mathbf{x}^{(n)} = P^n \mathbf{x}^{(0)}
<math>
Steady state of the weather
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:
- <math>
\mathbf{q} = \lim_{n \to \infty} \mathbf{x}^{(n)}
<math>
but only converges if P is a regular transition matrix (that is, there
is at least one Pn with all non-zero entries).
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:
- <math>
\begin{matrix}
P & = & \begin{bmatrix}
0.9 & 0.5 \\
0.1 & 0.5
\end{bmatrix}
\\
P \mathbf{q} & = & \mathbf{q}
& \mbox{(} \mathbf{q} \mbox{ is unchanged by } P \mbox{.)}
\\
& = & I \mathbf{q}
\\
(I - P) \mathbf{q} & = & \mathbf{0} \\
& = & \left( \begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}
- \begin{bmatrix}
0.9 & 0.5 \\
0.1 & 0.5
\end{bmatrix} \right) \mathbf{q}
\\
& = & \begin{bmatrix}
0.1 & -0.5 \\
-0.1 & 0.5
\end{bmatrix} \mathbf{q}
\end{matrix}
<math>
- <math>
\begin{bmatrix}
0.1 & -0.5 \\
-0.1 & 0.5
\end{bmatrix}
\begin{bmatrix}
q_1 \\
q_2
\end{bmatrix} = \begin{bmatrix}
0 \\
0
\end{bmatrix}
<math>
- <math>
\begin{bmatrix}
0.1 & -0.5 \\
-0.1 & 0.5
\end{bmatrix}
\approx \begin{bmatrix}
1 & -5 \\
0 & 0
\end{bmatrix}
<math>
- <math>
q_1 - 5 q_2 = 0
<math>
Set s = q2, so 5 s = q1. We want
s + 5 s = 1: therefore s = 0.167. Our steady state vector is:
- <math>
\begin{bmatrix}
q_1 \\
q_2
\end{bmatrix}
= \begin{bmatrix}
5 s \\
s
\end{bmatrix}
= \begin{bmatrix}
0.833 \\
0.167
\end{bmatrix}
<math>
In conclusion, in the long term, 83% of days are sunny.
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
