In mathematics, a chain of events in which the probability of moving from one state to another depends on the existing state. These are often displayed in matrices, and a two-state Markov chain, one in which there are two possible states at each stage, is illustrated by the matrix 
. For example, a man travels home from work either by car or by train. If he travels by car any one day, the probability that he travels by car the next might be 0·4; if he travels by train one day, the probability that he travels by train the next might be 0·3. These would be shown in the transition matrix 
. The notion is named after the Soviet mathematician Andrey Andreyevich Markov (18561922).
In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property.
A Markov chain describes at successive times the states of a system. At these times the system may have changed from the state it was in the moment before to another state, or it may have stayed in the same state. The Markov property means that the conditional probability distribution of the state in the future, given the state of the process currently and in the past, depends only on its current state and not on its state in the past. with Markov property, namely that, given the present state, the future and past states are independent. Markov chains are often described by a directed graph, where the edges are labeled by the probabilities of going from one state to the other states.
A finite state machine is an example of a Markov chain. If the machine is in state y at time n, then the probability that it moves to state x at time n + 1 depends only on the current state and does not depend on the time n.
Properties of Markov chains
Define the probability of going from state i to state j in n time steps as
and the single-step transition as
The n-step transition satisfies the Chapman-Kolmogorov equation, that for any 0<k<n,
The marginal distribution Pr(Xn = x) is the distribution over states at time n.
Reducibility
A state j is said to be accessible from state i (written i → j) if, given that we are in state i, there is a non-zero probability that at some time in the future, we will be in state j. That is, that there exists an n such that
A state i is said to communicate with state j (written i ↔ j) if it is true that both i is accessible from j and that j is accessible from i.
Finally, a Markov chain is said to be irreducible if its state space is a communicating class; this means that it is possible to get to any state from any state in an irreducible Markov chain.
Periodicity
A state i has period k if any return to state i must occur in some multiple of k time steps and k is the largest number with this property. Formally, the period of a state is defined as
(where "gcd" is the greatest common divisor)
If k = 1, then the state is said to be aperiodic;
An irreducible Markov chain is said to be aperiodic if its states are aperiodic.
Recurrence
A state i is said to be transient if, given that we start in state i, there is a non-zero probability that we will never return back to i. Formally, let the random variable Ti be the next return time to state i (the "hitting time"):
Then, state i is transient if Ti is not finite with some probability:
If a state i is not transient (it has finite hitting time with probability 1), then it is said to be recurrent or persistent.
It can be shown that a state is recurrent if and only if
Ergodicity
A state i is said to be ergodic if it is aperiodic and positive recurrent.
Steady state analysis and limiting distributions
If the Markov chain is a stationary Markov chain, so that the process is described by a single, time-independent matrix pij, then the vector π is a stationary distribution if its entries πj sum to 1 and satisfy
An irreducible chain has a stationary distribution if and only if all of its states are not null-recurrent. In that case, π is unique and is related to the expected return time:
Further, if the chain is both irreducible and aperiodic, then for any i and j,
Note that there is no assumption on the starting distribution; However, if a state j is aperiodic, then
and for any other state i, let fij be the probability that the chain ever visits state j if it starts at i,
Markov chains with a finite state space
If the state space is finite, the transition probability distribution can be represented by a matrix, called the transition matrix, with the (i, j)'th element of P equal to
P is a stochastic matrix.
The stationary distribution π is a (row) vector which satisfies the equation
In other words, the stationary distribution π is a normalized left eigenvector of the transition matrix associated with the eigenvalue 1.
A Markov chain is said to be reversible if there is a π such that
πipi,j = πjpj,iFor reversible Markov chains, π is always a stationary distribution.
A Bernoulli scheme is a special case of a Markov chain where the transition probability matrix has identical rows, which means that the next state is even independent of the current state (in addition to being independent of the past states).
Scientific applications
Markovian systems appear extensively in physics, particularly statistical mechanics, whenever probabilities are used to represent unknown or unmodelled details of the system, if it can be assumed that the dynamics are time-invariant, and that no relevant history need be considered which is not already included in the state description.
Markov chain methods have also become very important for generating sequences of random numbers to accurately reflect very complicated desired probability distributions - a process called Markov chain Monte Carlo or MCMC for short.
1st-order matrix| Note | A | C# | Eb |
|---|---|---|---|
| A | 0.1 | 0.6 | 0.3 |
| C# | 0.25 | 0.05 | 0.7 |
| Eb | 0.7 | 0.3 | 0 |
| Note | A | D | G |
|---|---|---|---|
| AA | 0.18 | 0.6 | 0.22 |
| AD | 0.5 | 0.5 | 0 |
| AG | 0.15 | 0.75 | 0.1 |
| DD | 0 | 0 | 1 |
| DA | 0.25 | 0 | 0.75 |
| DG | 0.9 | 0.1 | 0 |
| GG | 0.4 | 0.4 | 0.2 |
| GA | 0.5 | 0.25 | 0.25 |
| GD | 1 | 0 | 0 |
A second-order Markov chain can be introduced by considering the current state and also the previous state, as indicated in the second table.
Markov parody generators
Markov processes can also be used to generate superficially "real-looking" text given a sample document: they are used in a variety of recreational "parody generator" software (see dissociated press, Jeff Harrison, Mark V Shaney or ).
User Comments Add a comment…