Examples of Markov chains


Examples of Markov chains

This page contains examples of Markov chains in action.

Contents

Board games played with dice

A game of snakes and ladders or any other game whose moves are determined entirely by dice is a Markov chain, indeed, an absorbing Markov chain. This is in contrast to card games such as 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 blackjack, a player can gain an advantage by remembering which cards have already been shown (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.

A center-biased random walk

Consider a random walk on the number line where, at each step, the position (call it x) may change by +1 (to the right) or -1 (to the left) with probabilities:

P_{move~left} = \tfrac{1}{2} + \tfrac{1}{2} \left( \tfrac{x}{c+|x|} \right)

P_{move~right} = 1 - P_{move~left}

(where c is a constant greater than 0)


For example if the constant, c, equals 1, the probabilities of a move to the left at positions x = -2,-1,0,1,2 are given by \tfrac{1}{6},\tfrac{1}{4},\tfrac{1}{2},\tfrac{3}{4},\tfrac{5}{6} respectively. The random walk has a centering effect that weakens as c increases.

Since the probabilities depend only on the current position (value of x) and not on any prior positions, this biased random walk satisfies the definition of a Markov chain.

A very simple weather model

The probabilities of weather conditions (modeled as either rainy or sunny), 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.

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}
        1 & 0
    \end{bmatrix}
    \begin{bmatrix}
        0.9 & 0.1 \\
        0.5 & 0.5
    \end{bmatrix}^2
    
    = \begin{bmatrix}
        0.86 & 0.14
    \end{bmatrix}

or


    \mathbf{x}^{(2)} =\mathbf{x}^{(1)} P 
    = \begin{bmatrix}
        0.9 & 0.1
    \end{bmatrix}
    \begin{bmatrix}
        0.9 & 0.1 \\
        0.5 & 0.5
    \end{bmatrix}
    
    = \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

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 to a strictly positive vector 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:


    \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}


So − 0.1q1 + 0.5q2 = 0 and since they are a probability vector we know that q1 + q2 = 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.

Citation ranking

Google's page rank algorithm is essentially a Markov chain over the graph of the Web. More information can be found in "The PageRank Citation Ranking: Bringing Order to the Web" by Larry Page, Sergey Brin, R. Motwani, and T. Winograd .

References

See also

  • Mark V. Shaney

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Markov chain — A simple two state Markov chain. A Markov chain, named for Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized …   Wikipedia

  • Markov process — In probability theory and statistics, a Markov process, named after the Russian mathematician Andrey Markov, is a time varying random phenomenon for which a specific property (the Markov property) holds. In a common description, a stochastic… …   Wikipedia

  • Variable-order Markov model — Variable order Markov (VOM) models are an important class of models that extend the well known Markov chain models. In contrast to the Markov chain models, where each random variable in a sequence with a Markov property depends on a fixed number… …   Wikipedia

  • List of mathematical examples — This page will attempt to list examples in mathematics. To qualify for inclusion, an article should be about a mathematical object with a fair amount of concreteness. Usually a definition of an abstract concept, a theorem, or a proof would not be …   Wikipedia

  • Chapman–Kolmogorov equation — In mathematics, specifically in probability theory and in particular the theory of Markovian stochastic processes, the Chapman–Kolmogorov equation is an identity relating the joint probability distributions of different sets of coordinates on a… …   Wikipedia

  • Chapman-Kolmogorov equation — In mathematics, specifically in probability theory, and yet more specifically in the theory of Markovian stochastic processes, the Chapman Kolmogorov equation can be viewed as an identity relating the joint probability distributions of different… …   Wikipedia

  • List of probability topics — This is a list of probability topics, by Wikipedia page. It overlaps with the (alphabetical) list of statistical topics. There are also the list of probabilists and list of statisticians.General aspects*Probability *Randomness, Pseudorandomness,… …   Wikipedia

  • Variable-order Bayesian network — (VOBN) models provide an important extension of both the Bayesian network models and the variable order Markov models. VOBN models are used in machine learning in general and have shown great potential in bioinformatics applications.cite… …   Wikipedia

  • Outline of probability — Probability is the likelihood or chance that something is the case or will happen. Probability theory is used extensively in statistics, mathematics, science and philosophy to draw conclusions about the likelihood of potential events and the… …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.