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 X1,X2,X3,.... of random variables taking values in a "state space", the value of Xn being "the state of the system at time n". The (discrete-time) Markov property says that the conditional distribution of the "future"
given the "past", X1,...,Xn, depends on the past only through Xn. 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
= 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.
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
External links
- http://www.cs.bell-labs.com/cm/cs/pearls/sec153.html
- http://www.mathworks.com/company/newsletter/clevescorner/oct02_cleve.shtml
- Disassociated Press in Emacs approximates a Markov process
Referenced By
A. A. Markov | Andrei Andreevich Markov | Andrey Markov | Applied discrete math | Applied probability | Cut-up technique | Data compression/entropy | Decision math | Decision mathematics | Decision maths | Discrete math | Discrete mathematics | Discrete maths | Examples of Markov chains | Finite mathematics | Information Theory | Information entropy | Laplace-Stieltjes transform | List of mathematical topics (M-O) | List of probability topics | Mark V Shaney | Markov algorithm | Markov chain example | Markov process | Markov property | Martingale | Matrix (Mathematics) | Matrix (math) | Matrix (mathematic) | Metropolis-Hastings Markov Chain Monte Carlo Sampling | Monte Carlo Method | Monte Carlo simulation | Nonsense | Population process | Random walk Monte Carlo | Shannon entropy | Square matrix | Stochastic matrix | Stochastic process | Stochastic processes | Theory of random functions | Traveling salesman problem | Travelling salesman problem | William Feller
|
