Markov chain

In mathematics, a (discrete-time) Markov chain, named after Andrei Markov, is a discrete-time stochastic process with the Markov property. In such a process, the past is irrelevant for predicting the future given knowledge of the present.

Related Topics:
Mathematics - Andrei Markov - Stochastic process - Markov property

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

There are also continuous-time Markov chains.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A Markov chain is a sequence X1, X2, X3, ... of random variables. The range of these variables, i.e., the set of their possible values, is called the state space, the value of Xn being the state of the process at time n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If the conditional probability distribution of Xn+1 on past states is a function of Xn alone, then:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: P(X_{n+1}=x|X_0, X_1, X_2, ldots, X_n) = P(X_{n+1}=x|X_n). ,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Where x is some state of the process. The identity above identifies the Markov property.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Brownian motion - Ergodic hypothesis - Twentieth century - Law of large numbers

~ ~ ~ ~ ~ ~ ~ ~ ~ ~