Examples of Markov chains

From Wikipedia, the free encyclopedia

This page contains examples of Markov chains in action.

1 Board games played with dice
2 A very simple weather model
- 2.1 Predicting the weather
- 2.2 Steady state of the weather
3 Citation ranking
4 Applications in Marketing
5 References
6 External links

[edit] Board games played with dice

A game of Monopoly, snakes and ladders or any other game whose moves are determined entirely by dice is a Markov chain. This is in contrast to card games such as poker or blackjack, where the cards represent a 'memory' of the past moves. To see the difference, consider the probability for a certain event in the game. In the above mentioned dice games, the only thing that matters is the current state of the board. The next state of the board depends on the current state, and the next roll of the dice. It doesn't depend on how things got to their current state. In a game such as poker or blackjack, a player can gain an advantage by remembering which hands have already been played (and hence which cards are no longer in the deck), so the next state (or hand) of the game is not independent of the past states.

[edit] A very simple weather model

The probabilities of weather conditions, given the weather on the preceding day, can be represented by a transition matrix:

$P = \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix}$

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 i, it will be followed by a day of type j.

Notice that the rows of P sum to 1: this is because P is a stochastic matrix.

[edit] 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%:

$\mathbf{x}^{(0)} = \begin{bmatrix} 1 & 0 \end{bmatrix}$

The weather on day 1 can be predicted by:

$\mathbf{x}^{(1)} = \mathbf{x}^{(0)} P = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix} = \begin{bmatrix} 0.9 & 0.1 \end{bmatrix}$

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:

$\mathbf{x}^{(2)} =\mathbf{x}^{(1)} P = \mathbf{x}^{(0)} P^2 = \begin{bmatrix} 0.9 & 0.1 \end{bmatrix} \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix}^2 = \begin{bmatrix} 0.86 & 0.14 \end{bmatrix}$

General rules for day n are:

$\mathbf{x}^{(n)} = \mathbf{x}^{(n-1)} P$

$\mathbf{x}^{(n)} = \mathbf{x}^{(0)} P^n$

[edit] 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:

$\mathbf{q} = \lim_{n \to \infty} \mathbf{x}^{(n)}$

but only converges if P is a regular transition matrix (that is, there is at least one Pⁿ 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:

$\begin{matrix} P & = & \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix} \\ \mathbf{q} P & = & \mathbf{q} & \mbox{(} \mathbf{q} \mbox{ is unchanged by } P \mbox{.)} \\ & = & \mathbf{q}I \\ \mathbf{q} (P - I) & = & \mathbf{0} \\ & = & \mathbf{q} \left( \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix} - \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \right) \\ & = & \mathbf{q} \begin{bmatrix} -0.1 & 0.1 \\ 0.5 & -0.5 \end{bmatrix} \end{matrix}$

$\begin{bmatrix} q_1 & q_2 \end{bmatrix} \begin{bmatrix} -0.1 & 0.1 \\ 0.5 & -0.5 \end{bmatrix} = \begin{bmatrix} 0 & 0 \end{bmatrix}$

- 0.1 q 1 + 0.5 q 2 = 0

and since they are a probability vector we know that

q 1 + q 2 = 1.

Solving this pair of simultaneous equations gives the steady state distribution:

$\begin{bmatrix} q_1 & q_2 \end{bmatrix} = \begin{bmatrix} 0.833 & 0.167 \end{bmatrix}$

In conclusion, in the long term, 83% of days are sunny.

[edit] Citation ranking

For the most prolific example of the use of Markov chains, see Google. A description behind the page rank algorithm, which is basically a Markov chain over the graph of the Internet, can be found in the seminal paper, "The Page Rank Citation Ranking: Bringing Order to the Web" by Larry Page, Sergey Brin, R. Motwani, and T. Winograd.