Markov chain

A Markov chain (named in honor of Andrei Andreevich Markov) is a stochastic process with what is called the Markov property, of which there is a "discrete-time" version and a "continuous-time" version. In the discrete-time case, the process consists of a sequence X₁,X₂,X₃,.... of random variables taking values in a "state space", the value of X_n being "the state of the system at time n". The (discrete-time) Markov property says that the conditional distribution of the "future"

$X_{n+1},X_{n+2},X_{n+3},\dots$

given the "past", X₁,...,X_n, depends on the past only through X_n. In other words, knowledge of the most recent past state of the system renders knowledge of less recent history irrelevant. Each particular Markov chain may be identified with its matrix of "transition probabilities", often called simply its transition matrix. The entries in the transition matrix are given by

$p_{ij}=P(X_{n+1}=j\mid X_{n}=i)$

= the probability that the system will be in state j "tomorrow" given that it is in state i "today". The ij entry in the kth power of the matrix of transition probabilities is the conditional probability that k "days" in the future the system will be in state j, given that it is in state i "today". A matrix is a stochastic matrix if and only if it is the matrix of transition probabilities of some Markov chain.

There may exist one or more vectors π such that

$P\pi =\pi \,$

where P is the transition matrix. Such a vector is called a stationary distribution, steady-state distribution, or steady-state vector. A stationary distribution is an eigenvector of the transition matrix associated with the eigenvalue 1.

Whether or not there is a stationary distribution, and whether or not it is unique if it does exist, are determined by certain properties of the transition matrix. Irreducible means that every state is accessible from every other state. Aperiodic means that for every state, the transition from that state to itself is possible. Positive recurrent means that the expected return time is finite for every state. Sometimes the terms indecomposable, acyclic, and persistent are used as synonyms for "irreducible", "aperiodic", and "recurrent", respectively. A transition matrix which is positive (that is, every element of the matrix is positive) is irreducible, aperiodic, and positive recurrent.

If the transition matrix is positive recurrent, there exists a stationary distribution. If it is positive recurrent and irreducible, there exists a unique stationary distribution. If it is positive recurrent, irreducible, and aperiodic, the matrix Pⁿ converges elementwise to a matrix in which each column is the unique stationary distribution. The matrix Pⁿ is sometimes called the n-step transition matrix, as it gives the probability of a transition from one state to another in n steps.

Scientific applications

Markov chains are used to model various processes in queueing theory and statistics, and can also be used as a signal model in entropy coding techniques such as arithmetic coding. Markov chains also have many biological applications, particularly population processes, which are useful in modelling processes that are (at least) analogous to biological populations. Markov chains have been used in bioinformatics as well. An example is the genemark algorithm for coding region/gene prediction.

Markov processes can also be used to generate superficially "real-looking" text given a sample document: they are used in various pieces of recreational "parody generator" software (see Jeff Harrison).

See also

• Hidden Markov model
• Examples of Markov chains
• Mark V Shaney

References

• A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135-156, 1906. (Markov's original paper on Markov chains. A citation of a translation would be very helpful here.)

• Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. (See Chapter 7.)

• J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953.

External links

• Generating Text (About generating random text using a Markov chain.)

• The World’s Largest Matrix Computation (Google's PageRank as the stationary distribution of a random walk through the Web.)

• Disassociated Press in Emacs approximates a Markov process

• Markov Chains