Markov chain

In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. A countably infinite sequence, in which the chain moves state at discrete time steps, gives a discrete-time Markov chain (DTMC). A continuous-time process is called a continuous-time Markov chain (CTMC). Markov processes are named in honor of the Russian mathematician Andrey Markov.

Markov chains have many applications as statistical models of real-world processes. They provide the basis for general stochastic simulation methods known as Markov chain Monte Carlo, which are used for simulating sampling from complex probability distributions, and have found application in areas including Bayesian statistics, biology, chemistry, economics, finance, information theory, physics, signal processing, and speech processing.

The adjectives Markovian and Markov are used to describe something that is related to a Markov process.

A Markov process is a stochastic process that satisfies the Markov property (sometimes characterized as "memorylessness"). In simpler terms, it is a process for which predictions can be made regarding future outcomes based solely on its present state and, most importantly, such predictions are just as good as the ones that could be made knowing the process's full history. In other words, conditional on the present state of the system, its future and past states are independent.

A Markov chain is a type of Markov process that has either a discrete state space or a discrete index set (often representing time), but the precise definition of a Markov chain varies. For example, it is common to define a Markov chain as a Markov process in either discrete or continuous time with a countable state space (thus regardless of the nature of time), but it is also common to define a Markov chain as having discrete time in either countable or continuous state space (thus regardless of the state space).

The system's state space and time parameter index need to be specified. The following table gives an overview of the different instances of Markov processes for different levels of state space generality for both discrete and continuous time:

Note that there is no definitive agreement in the literature on the use of some of the terms that signify special cases of Markov processes. Usually the term "Markov chain" is reserved for a process with a discrete set of times, that is, a discrete-time Markov chain (DTMC), but a few authors use the term "Markov process" to refer to a continuous-time Markov chain (CTMC) without explicit mention. In addition, there are other extensions of Markov processes that are referred to as such but do not necessarily fall within any of these four categories (see Markov model). Moreover, the time index need not necessarily be real-valued; like with the state space, there are conceivable processes that move through index sets with other mathematical constructs. Notice that the general state space continuous-time Markov chain is general to such a degree that it has no designated term.

While the time parameter is usually discrete, the state space of a Markov chain does not have any generally agreed-on restrictions: the term may refer to a process on an arbitrary state space. However, many applications of Markov chains employ finite or countably infinite state spaces, which have a more straightforward statistical analysis. Besides time-index and state-space parameters, there are many other variations, extensions and generalizations (see Variations). For simplicity, most of this article concentrates on the discrete-time, discrete state-space case, unless mentioned otherwise.

The changes of state of the system are called transitions. The probabilities associated with various state changes are called transition probabilities. The process is characterized by a state space, a transition matrix describing the probabilities of particular transitions, and an initial state (or initial distribution) across the state space. By convention, we assume all possible states and transitions have been included in the definition of the process, so there is always a next state, and the process does not terminate.

A discrete-time random process involves a system which is in a certain state at each step, with the state changing randomly between steps. The steps are often thought of as moments in time, but they can equally well refer to physical distance or any other discrete measurement. Formally, the steps are the integers or natural numbers, and the random process is a mapping of these to states. The Markov property states that the conditional probability distribution for the system at the next step (and in fact at all future steps) depends only on the current state of the system, and not additionally on the state of the system at previous steps.

Since the system changes randomly, it is generally impossible to predict with certainty the state of a Markov chain at a given point in the future. However, the statistical properties of the system's future can be predicted. In many applications, it is these statistical properties that are important.

Andrey Markov studied Markov processes in the early 20th century, publishing his first paper on the topic in 1906. Markov processes in continuous time were discovered long before his work in the early 20th century in the form of the Poisson process. Markov was interested in studying an extension of independent random sequences, motivated by a disagreement with Pavel Nekrasov who claimed independence was necessary for the weak law of large numbers to hold. In his first paper on Markov chains, published in 1906, Markov showed that under certain conditions the average outcomes of the Markov chain would converge to a fixed vector of values, so proving a weak law of large numbers without the independence assumption, which had been commonly regarded as a requirement for such mathematical laws to hold. Markov later used Markov chains to study the distribution of vowels in Eugene Onegin, written by Alexander Pushkin, and proved a central limit theorem for such chains.

In 1912 Henri Poincaré studied Markov chains on finite groups with an aim to study card shuffling. Other early uses of Markov chains include a diffusion model, introduced by Paul and Tatyana Ehrenfest in 1907, and a branching process, introduced by Francis Galton and Henry William Watson in 1873, preceding the work of Markov. After the work of Galton and Watson, it was later revealed that their branching process had been independently discovered and studied around three decades earlier by Irénée-Jules Bienaymé. Starting in 1928, Maurice Fréchet became interested in Markov chains, eventually resulting in him publishing in 1938 a detailed study on Markov chains.

Andrey Kolmogorov developed in a 1931 paper a large part of the early theory of continuous-time Markov processes. Kolmogorov was partly inspired by Louis Bachelier's 1900 work on fluctuations in the stock market as well as Norbert Wiener's work on Einstein's model of Brownian movement. He introduced and studied a particular set of Markov processes known as diffusion processes, where he derived a set of differential equations describing the processes. Independent of Kolmogorov's work, Sydney Chapman derived in a 1928 paper an equation, now called the Chapman-Kolmogorov equation, in a less mathematically rigorous way than Kolmogorov, while studying Brownian movement. The differential equations are now called the Kolmogorov equations or the Kolmogorov-Chapman equations. Other mathematicians who contributed significantly to the foundations of Markov processes include William Feller, starting in 1930s, and then later Eugene Dynkin, starting in the 1950s.

• Mark V. Shaney is a third-order Markov chain program, and a Markov text generator. It ingests the sample text (the Tao Te Ching, or the posts of a Usenet group) and creates a massive list of every sequence of three successive words (triplet) which occurs in the text. It then chooses two words at random, and looks for a word which follows those two in one of the triplets in its massive list. If there is more than one, it picks at random (identical triplets count separately, so a sequence which occurs twice is twice as likely to be picked as one which only occurs once). It then adds that word to the generated text. Then, in the same way, it picks a triplet that starts with the second and third words in the generated text, and that gives a fourth word. It adds the fourth word, then repeats with the third and fourth words, and so on.
• Random walks based on integers and the gambler's ruin problem are examples of Markov processes. Some variations of these processes were studied hundreds of years earlier in the context of independent variables. Two important examples of Markov processes are the Wiener process, also known as the Brownian motion process, and the Poisson process, which are considered the most important and central stochastic processes in the theory of stochastic processes. These two processes are Markov processes in continuous time, while random walks on the integers and the gambler's ruin problem are examples of Markov processes in discrete time.
• A famous Markov chain is the so-called "drunkard's walk", a random walk on the number line where, at each step, the position may change by +1 or −1 with equal probability. From any position there are two possible transitions, to the next or previous integer. The transition probabilities depend only on the current position, not on the manner in which the position was reached. For example, the transition probabilities from 5 to 4 and 5 to 6 are both 0.5, and all other transition probabilities from 5 are 0. These probabilities are independent of whether the system was previously in 4 or 6.
• A series of independent states (for example, a series of coin flips) satisfies the formal definition of a Markov chain. However, the theory is usually applied only when the probability distribution of the next state depends on the current one.

Suppose that there is a coin purse containing five coins worth 25¢ (quarters), five coins worth 10¢ (dimes) and five coins worth 5¢ (nickels). One by one, coins are randomly drawn from the purse and are set on a table. If \(X_n\) represents the total value of the coins set on the table after n draws, with \(X_0 = 0\), then the sequence \(\{X_n : n\in\mathbb{N}\}\) is not a Markov process.

To see why this is the case, suppose that in the first six draws, all five nickels and a quarter are drawn. Thus \(X_6 = \$0.50\). If we know not just \(X_6\), but the earlier values as well, then we can determine which coins have been drawn, and we know that the next coin will not be a nickel; so we can determine that \(X_7 \geq \$0.60\) with probability 1. But if we do not know the earlier values, then based only on the value \(X_6\) we might guess that we had drawn four dimes and two nickels, in which case it would certainly be possible to draw another nickel next. Thus, our guesses about \(X_7\) are impacted by our knowledge of values prior to \(X_6\).

However, it is possible to model this scenario as a Markov process. Instead of defining \(X_n\) to represent the total value of the coins on the table, we could define \(X_n\) to represent the count of the various coin types on the table. For instance, \(X_6 = 1,0,5\) could be defined to represent the state where there is one quarter, zero dimes, and five nickels on the table after 6 one-by-one draws. This new model could be represented by \(6\times 6\times 6=216\) possible states, where each state represents the number of coins of each type (from 0 to 5) that are on the table. (Not all of these states are reachable within 6 draws.)

Suppose that the first draw results in state \(X_1 = 0,1,0\). The probability of achieving \(X_2\) now depends on \(X_1\); for example, the state \(X_2 = 1,0,1\) is not possible. After the second draw, the third draw depends on which coins have so far been drawn, but no longer only on the coins that were drawn for the first state (since probabilistically important information has since been added to the scenario). In this way, the likelihood of the \(X_n = i,j,k\) state depends exclusively on the outcome of the \(X_{n-1}= \ell,m,p\) state.

A discrete-time Markov chain is a sequence of random variables X₁, X₂, X₃, ... with the Markov property, namely that the probability of moving to the next state depends only on the present state and not on the previous states:

\(\Pr(X_{n+1}=x\mid X_1=x_1, X_2=x_2, \ldots, X_n=x_n) = \Pr(X_{n+1}=x\mid X_n=x_n),\) if both conditional probabilities are well defined, that is, if \(\Pr(X_1=x_1,\ldots,X_n=x_n)>0.\)

The possible values of X_i form a countable set S called the state space of the chain.

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_{ij} = \Pr(X_{n+1}=j\mid X_n=i).\)

Since each row of P sums to one and all elements are non-negative, P is a right stochastic matrix.

A continuous-time Markov chain \((X_t)_{t\geq 0}\) is defined by a finite or countable state space S, a transition rate matrix Q with dimensions equal to that of the state space and initial probability distribution defined on the state space. For i ≠ j, the elements q_ij are non-negative and describe the rate of the process transitions from state i to state j. The elements q_ii are chosen such that each row of the transition rate matrix sums to zero, while the row-sums of a probability transition matrix in a (discrete) Markov chain are all equal to one.

There are three equivalent definitions of the process.

The definition of Markov processes in continuous time with general state space is more technical than the above.

A continuous-time Markov process \(X=(X_t)_{t\geq 0}\) is a stochastic process adapted to a filtration \(\mathbb F=(\mathcal F_t)_{t\geq 0}\) with values in a locally compact Polish space \((S,\mathcal B(S))\) (e.g., \((\R,\mathcal B(\R))\)). The latter essentially ensures that the conditional expectations of \(X_t\) are regular, which, in simple terms, means that they behave "nicely". Then \(X\) is called a Markov process, if it satisfies the Markov property, i.e., for all \(t\geq s\geq 0\) and \(A\in \mathcal B(S)\)

\(P(X_t\in A\mid \mathcal F_s)=P(X_t\in A\mid X_s)\).

Moreover, \(X\) is called time-homogeneous, if it satisfies the weak Markov property for all \(t,s\geq 0\):

\(P(X_{t+s}\in A\mid \mathcal F_s)=P(X_t\in A\mid X_0=x)|_{x=X_s}=: P_t(X_s,A)\).

The function \((t,x,A)\mapsto P_t(x,A)\) is the so-called transition function of \(X\) and \((P_t)_{t\geq 0}\) the transition semigroup of the process. Transition functions are generalizations of the transition matrices used in the setting with finite state space.

In a more abstract way, Markov processes can also be defined or constructed the other way around: Let \((P_t)_{t\geq 0}\) be a transition semigroup, i.e.,

1. \(P_t\) is Markov kernel for all \(t\geq 0\),
2. \(P_{t+s}(x,A)=\int_S P_t(y,A)P_s(x,dy) \quad \forall t,s\geq 0, x\in \R,A\in\mathcal B(S)\) (Chapman-Kolmogorov-equation),
3. \(P_0(x,\cdot)=\delta_x\),

where \(\delta_x\) is the Dirac-measure in \(x\), and \(X:\Omega\times [0,\infty)\to S\). Then \(X\) is a homogeneous Markov process w.r.t. the natural filtration \(\mathbb F^X = (\sigma(X_s:0\leq s\leq t))_{t\geq 0}\), if for all \(0\leq t_1<...

\(P(X_{t_1}\in A_1,...,X_{t_n}\in A_n\mid X_0=x)= \int_{A_1}...\int_{A_{n-1}} P_{t_n-t_{n-1}}(x_{n-1},A_n)\cdots P_{t_1}(x,dx_1)\).

Or, if no probability measure \(P\) has been specified, the above equation defines a measure \(P^x:=P(\cdot\mid X_0=x)\) on \(\sigma(X_s:s\geq 0)\) under which the process \(X\) started in \(x\) is a Markov process by construction.

Condensed: the full section is in Wikipedia.

Two states are said to communicate with each other if both are reachable from one another by a sequence of transitions that have positive probability. This is an equivalence relation which yields a set of communicating classes. A class is closed if the probability of leaving the class is zero. A Markov chain is irreducible if there is one communicating class, the state space.

A state i has period k if k is the greatest common divisor of the number of transitions by which i can be reached, starting from i. That is:

\(k = \gcd\{ n > 0: \Pr(X_n = i \mid X_0 = i) > 0\}\)

The state is periodic if \(k > 1\); otherwise \(k = 1\) and the state is aperiodic.

A state i is said to be transient if, starting from i, there is a non-zero probability that the chain will never return to i. It is called recurrent (or persistent) otherwise. For a recurrent state i, the mean hitting time is defined as:

\(M_i = E[T_i]=\sum_{n=1}^\infty n\cdot f_{ii}^{(n)}\) where \(f_{ii}^{(n)} := \Pr(\min\{m > 0 : X_m = i\} = n \mid X_0 = i)\).

State i is positive recurrent if \(M_i\) is finite and null recurrent otherwise. Periodicity, transience, recurrence and positive and null recurrence are class properties. That is, if one state has the property then all states in its communicating class have the property.

A stationary distribution π is a (row) vector, whose entries are non-negative and sum to 1, is unchanged by the operation of transition matrix P on it and so is defined by

\(\pi\mathbf{P} = \pi.\)

A state i is called absorbing if there are no outgoing transitions from the state.

Since periodicity is a class property, if a Markov chain is irreducible, then all its states have the same period. In particular, if one state is aperiodic, then the whole Markov chain is aperiodic.

If a finite Markov chain is irreducible, then all states are positive recurrent, and it has a unique stationary distribution given by \(\pi_i = 1/E[T_i]\).

A state i is said to be ergodic if it is aperiodic and positive recurrent. In other words, a state i is ergodic if it is recurrent, has a period of 1, and has finite mean recurrence time.

If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic. Equivalently, there exists some integer \(k\) such that all entries of \(M^k\) are positive.

It can be shown that a finite state irreducible Markov chain is ergodic if it has an aperiodic state.

A Markov chain with more than one state and just one out-going transition per state is either not irreducible or not aperiodic, hence cannot be ergodic.