Markov chain

There are also continuous-time Markov chains.

A Markov chain is a sequence X₁, X₂, X₃, ... of random variables. The range of these variables, i.e., the set of their possible values, is called the state space, the value of X_n being the state of the process at time n.
If the conditional probability distribution of X_n+1 on past states is a function of X_n alone, then:

Andrei Markov produced the first results (1906) for these processes.
A generalization to countably infinite state spaces was given by Kolmogorov (1936).
Markov chains are related to Brownian motion and the ergodic hypothesis, two topics in physics which were important in the early years of the twentieth century, but Markov appears to have pursued this out of a mathematical motivation, namely the extension of the law of large numbers to dependent events.

Properties of Markov chains

A Markov chain is characterized by the conditional distribution

The marginal distribution P(X_n) is the distribution over states at time n. The initial distribution is P(X₀). The evolution of the process through one time step is described by

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 process.
Irreducible means that every state is accessible from every other state.
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. When the state space of a Markov chain is not irreducible, it may be partitioneded into a set of (irreducible) communicating classes, each of which may be classified as above. The problem of classification is an important one in the mathematical study of Markov chains and related stochastic processes.

If the Markov chain is positive recurrent,
there exists a stationary distribution.
If it is positive recurrent and irreducible,
there exists a unique stationary distribution,
and furthermore the process constructed by taking the stationary distribution as the initial distribution is ergodic.
Then the average of a function f over samples of the Markov chain is equal to the average with respect to the stationary distribution,

Furthermore,
the equivalence of averages also holds if f is the indicator function on some subset A of the state space.

Markov chains in discrete state spaces

If the state space is finite,
the transition probability distribution can be represented as a matrix,
called the transition matrix,
with the (i, j)'th element equal to

Writing P for the transition matrix,
a stationary distribution is a vector which satisfies the equation

.

If the transition matrix P is irreducible, and aperiodic, then P^k converges elementwise to a matrix in which each column is the unique stationary distribution , with

,

A transition matrix which is positive (that is, every element of the matrix is positive) is irreducible and aperiodic. A matrix is a stochastic matrix if and only if it is the matrix of transition probabilities of some Markov chain.

Note: In this formulation, element (i, j) is the probability of a transition from j to i. An equivalent formulation is sometimes given with element (i, j) equal to the probability of a transition from i to j. In that case the transition matrix is just the transpose of the one given here. Also, the stationary distribution of the system is then given by the left eigenvector of the transition matrix, instead of the right eigenvector.

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. Hidden Markov models have been used in bioinformatics as well, e.g. 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, Mark V Shaney). Markov chains have also been used in music composition.

See also

• Hidden Markov model
• Examples of Markov chains
• Markov decision process
• 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.

• A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.

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

• J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.
  

  External links

• Markov Chains

• 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

• [1] Markov chains used to produce semi-coherent English.