Markov Chain

Domain	Definitions
Computing	Markov chain (Named after Andrei Markov) A model of sequences of events where the probability of an event occurring depends upon the fact that a preceding event occurred. A Markov process is governed by a Markov chain. In simulation, the principle of the Markov chain is applied to the selection of samples from a probability density function to be applied to the model. Simscript II.5 uses this approach for some modelling functions. [Better explanation?] (1995-02-23). Source: The Free On-line Dictionary of Computing.
Math	A finite state machine with probabilities for each transition, that is, a probability that the next state is sj given that the current state is si. (references)
Mathematics	An expression used in two different senses, both relating to a Markov process:i)in one sense a process(xt)is called a chain if the time parameter is discontinuous; ii)in the other it is called a chain if the values of x are discontinuous. The former appears preferable. Source: European Union. (references)
Source: compiled by the editor from various references; see credits.

Specialty Definition: 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"

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

= 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 queuing 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. Furthemore, the concept of Markov chains has 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).

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

Commercial Usage: Markov Chain

Domain	Title
Books	Algorithms for Random Generation and Counting: A Markov Chain Approach (Progress in Theoretical Computer Science) (reference) An Introduction to Markov Chain Analysis (reference) Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A Mathematical Introduction (Applications of Mathematics) (reference) Lecture notes on limit theorems for Markov chain transition probabilities (reference) Markov Chain Models--Rarity and Exponentiality (reference) (more book examples)
Source: compiled by the editor from various references; see credits.

Frequency of Internet Keywords: Markov Chain

Modern Translations: Markov Chain

Language		Translations for "Markov chain"; alternative meanings/domain in parentheses.
Danish		Markov kæde. (various references)

Dutch		Markovketen (Markov process). (various references)

Finnish		Markovin ketju. (various references)

French		chaîne de Markov (Markov process). (various references)

German		Markovsche Kette. (various references)

Greek		αλυσίδα Markov. (various references)

Italian		catena di Markov. (various references)

Pig Latin		arkovmay ainchay

Portuguese		cadeia de Markov. (various references)

Spanish		cadena de Markov. (various references)

Swedish		Markovkedja. (various references)
Source: compiled by the editor from various translation references.

Anagrams: Markov Chain

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "a-a-c-h-i-k-m-n-o-r-v"
	-2 letters: harmonica.
	-3 letters: armonica, chairman, harmonic, macaroni, marocain, omniarch.
	-4 letters: acromia, corvina, hackman, kachina, mahonia, manioca, minorca, monarch, nomarch, ocarina, ovarian.
	-5 letters: acinar, airman, anarch, anchor, anomic, anorak, archon, arnica, caiman, camion, carina, carman, caviar, chakra, charka, chimar, choana, chroma, crania, harmin, havior, inarch, karmic, macron, maniac, manioc, marina, micron, mikron, mikvah, mohair, rancho, vomica.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.