At each step the system may change its state from the current state to another state, or remain in the same state, according to a certain probability distribution. The changes of state are called transitions, and the probabilities associated with various state-changes are called transition probabilities.
An example of a Markov chain is a simple random walk where the state space is a set of vertices of a graph and the transition steps involve moving to any of the neighbors of the current vertex with equal probability (regardless of the history of the walk).
The possible values of Xi form a countable set S called the state space of the chain.
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.
Time-homogeneous Markov chains (or, Markov chains with time-homogeneous transition probabilities) are processes where
for all n.
A Markov chain of order m (or a Markov chain with memory m) where m is finite, is where
for all n. It is possible to construct a chain (Yn) from (Xn) which has the 'classical' Markov property as follows: Let Yn = (Xn, Xn−1, ..., Xn−m+1), the ordered m-tuple of X values. Then Yn is a Markov chain with state space Sm and has the classical Markov property.
A finite state machine can be used as a representation of a Markov chain. Assuming a sequence of independent and identically distributed input signals (for example, symbols from a binary alphabet chosen by coin tosses), 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.
A thorough development and many examples can be found in the on-line monograph Meyn & Tweedie 2005 The appendix of Meyn 2007 , also available on-line, contains an abridged Meyn & Tweedie.
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 k such that 0 < k < n,
The marginal distribution Pr (Xn = x) is the distribution over states at time n. The initial distribution is Pr (X0 = x). The evolution of the process through one time step is described by
The superscript is intended to be an integer-valued label only; however, if the Markov chain is time-homogeneous, then this superscript can also be interpreted as a "raising to the power of", discussed further below.
A state j is said to be accessible from a different 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. Formally, state j is accessible from state i if there exists an integer n≥0 such that
Allowing n to be zero means that every state is defined to be accessible from itself.
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. A set of states C is a communicating class if every pair of states in C communicates with each other, and no state in C communicates with any state not in C. (It can be shown that communication in this sense is an equivalence relation). A communicating class is closed if the probability of leaving the class is zero, namely that if i is in C but j is not, then j is not accessible from i.
Finally, a Markov chain is said to be irreducible if its state space is a communicating class; this means that, in an irreducible Markov chain, it is possible to get to any state from any state.
If k = 1, then the state is said to be aperiodic; otherwise (k>1), the state is said to be periodic with period k.
It can be shown that every state in a communicating class must have the same period.
A finite state irreducible Markov chain is said to be ergodic if its states are aperiodic.
Then, state i is transient iff:
If a state i is not transient (it has finite hitting time with probability 1), then it is said to be recurrent or persistent. Although the hitting time is finite, it need not have a finite expectation. Let Mi be the expected return time,
Then, state i is positive recurrent if Mi is finite; otherwise, state i is null recurrent (the terms non-null persistent and null persistent are also used, respectively).
It can be shown that a state is recurrent if and only if
A state i is called absorbing if it is impossible to leave this state. Therefore, the state i is absorbing if and only if
An irreducible chain has a stationary distribution if and only if all of its states are positive-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; the chain converges to the stationary distribution regardless of where it begins.
If a chain is not irreducible, its stationary distributions will not be unique (consider any closed communicating class in the chain; each one will have its own unique stationary distribution. Any of these will extend to a stationary distribution for the overall chain, where the probability outside the class is set to zero). 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,
P is a stochastic matrix, which is an important fact to keep in mind for the rest of this discussion. When the Markov chain is a time-homogeneous Markov chain, so that the transition matrix P always remains the same at each step, then the k-step transition probability can be computed as the k'th power of the transition matrix, Pk.
The stationary distribution π is a (row) vector whose entries sum to 1 that satisfies the equation
Alternatively, π can be viewed as a fixed point of the linear (hence continuous) transformation on the unit simplex associated to the matrix P. As any continuous transformation in the unit simplex has a fixed point, a stationary distribution always exists, but is not guaranteed to be unique, in general. However, if the Markov chain is irreducible and aperiodic, then there is a unique stationary distribution π. Additionally, in this case Pk converges to a rank-one matrix in which each row is the stationary distribution π, that is,
where 1 is the column vector with all entries equal to 1. This is stated by the Perron-Frobenius theorem. If, by whatever means, is found, then the stationary distribution of the Markov chain in question can be easily determined for any starting distribution, as will be explained below.
Since P is a stochastic matrix, always exists. Because there are a number of different special cases to consider, the process of finding this limit can be a lengthy task. All the same, there are several general rules and guidelines to keep in mind. Let P be an n×n matrix, and define
It is always true that
Subtracting Q from both sides and factoring then yields
where In is the identity matrix of size n, and 0n,n is the zero matrix of size n×n. Multiplying together stochastic matrices always yields another stochastic matrix, so Q must be a stochastic matrix. It is sometimes sufficient to use the matrix equation above and the fact that Q is a stochastic matrix to solve for Q.
Here is one method for doing so: first, define the function f(A) to return the matrix A with its right-most column replaced with all 1's. Then evaluate the following equation:
This equation does not work when [f(P – In)]–1 does not exist. If this is the case, then it is necessary to take into account more information in order to find Q. One thing to notice is that if P has an element Pi,i on its main diagonal that is equal to 1 and the ith row or column is otherwise filled with 0's, then that row or column will remain unchanged in all of the subsequent powers Pk. Hence, the ith row or column of Q will have the 1 and the 0's in the same positions as in P.
In most cases, Pk approaches but never actually equals its limit. There are numerous exceptions to this, however, such as the case in which
If A0 (which is a row vector) represents the starting distribution, then the stationary distribution is equal to A0Q. Note that any distribution, regardless of the number of steps it is away from the starting distribution, can be used in place of A0 without affecting the result for the stationary distribution.
The idea of a reversible Markov chain comes from the ability to "invert" a conditional probability using Bayes' Rule:
It now appears that time has been reversed. Thus, a Markov chain is said to be reversible if there is a π such that
This condition is also known as the detailed balance condition.
Summing over gives
so for 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). A Bernoulli scheme with only two possible states is known as a Bernoulli process.
Many results for Markov chains with finite state space can be generalized to chains with uncountable state space through Harris chains. The main idea is to see if there is a point in the state space that the chain hits with probability one. Generally, it is not true for continuous state space, however, we can define sets A and B along with a positive number ε and a probability measure ρ, such that
Then we could collapse the sets into an auxiliary point α, and a recurrent Harris chain can be modified to contain α. Lastly, the collection of Harris chains is a comfortable level of generality, which is broad enough to contain a large number of interesting examples, yet restrictive enough to allow for a rich theory.
Markov models have also been used to analyze web navigation behavior of users. A user's web link transition on a particular website can be modeled using first- or second-order Markov models and can be used to make predictions regarding future navigation and to personalize the web page for an individual user.
Markov chains also have many applications in biological modelling, particularly population processes, which are useful in modelling processes that are (at least) analogous to biological populations. The Leslie matrix is one such example, though some of its entries are not probabilities (they may be greater than 1). Another important example is the modeling of cell shape in dividing sheets of epithelial cells. The distribution of shapes -- predominantly hexagonal -- was a long standing mystery until it was explained by a simple Markov Model, where a cell's state is its number of sides. Empirical evidence from frogs, fruit flies, and hydra further suggests that the stationary distribution of cell shape is exhibited by almost all multicellular animals. Yet another example is the state of Ion channels in cell membranes.
Markov chains can be used to model many games of chance. The children's games Snakes and Ladders and "Hi Ho! Cherry-O", for example, are represented exactly by Markov chains. At each turn, the player starts in a given state (on a given square) and from there has fixed odds of moving to certain other states (squares).
A second-order Markov chain can be introduced by considering the current state and also the previous state, as indicated in the second table. Higher, nth-order chains tend to "group" particular notes together, while 'breaking off' into other patterns and sequences occasionally. These higher-order chains tend to generate results with a sense of phrasal structure, rather than the 'aimless wandering' produced by a first-order system.