language-icon Old Web
English
Sign In

Markov chain

A Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.A Markov chain is a stochastic process with the Markov property. The term 'Markov chain' refers to the sequence of random variables such a process moves through, with the Markov property defining serial dependence only between adjacent periods (as in a 'chain'). It can thus be used for describing systems that follow a chain of linked events, where what happens next depends only on the current state of the system.Andrey Markov studied Markov chains in the early 20th century. 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. See Markov chain central limit theorem.Suppose that you start with $10, and you wager $1 on an unending, fair, coin toss indefinitely, or until you lose all of your money. If X n {displaystyle X_{n}}   represents the number of dollars you have after n tosses, with X 0 = 10 {displaystyle X_{0}=10}  , then the sequence { X n : n ∈ N } {displaystyle {X_{n}:nin mathbb {N} }}   is a Markov process. If I know that you have $12 now, then it would be expected that with even odds, you will either have $11 or $13 after the next toss. This guess is not improved by the added knowledge that you started with $10, then went up to $11, down to $10, up to $11, and then to $12.The Markov property refers to the memoryless property of a stochastic process.A discrete-time Markov chain is a sequence of random variables X1, X2, X3, ... 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:The probability of going from state i to state j in n time steps isA Markov chain is said to be irreducible if it is possible to get to any state from any state. The following explains this definition more formally.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 toA Markov chain is said to be reversible if there is a probability distribution π over its states such thatA 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.For an overview of Markov chains on a general state space, see Markov chains on a measurable state space.In some cases, apparently non-Markovian processes may still have Markovian representations, constructed by expanding the concept of the 'current' and 'future' states. For example, let X be a non-Markovian process. Then define a process Y, such that each state of Y represents a time-interval of states of X. Mathematically, this takes the form:Write P(t) for the matrix with entries pij = P(Xt = j | X0 = i). Then the matrix P(t) satisfies the forward equation, a first-order differential equationThe stationary distribution for an irreducible recurrent CTMC is the probability distribution to which the process converges for large values of t. Observe that for the two-state process considered earlier with P(t) given byThe hitting time is the time, starting in a given set of states until the chain arrives in a given state or set of states. The distribution of such a time period has a phase type distribution. The simplest such distribution is that of a single exponentially distributed transition.For a CTMC Xt, the time-reversed process is defined to be X ^ t = X T − t {displaystyle scriptstyle {hat {X}}_{t}=X_{T-t}}  . By Kelly's lemma this process has the same stationary distribution as the forward process.One method of finding the stationary probability distribution, π, of an ergodic continuous-time Markov chain, Q, is by first finding its embedded Markov chain (EMC). Strictly speaking, the EMC is a regular discrete-time Markov chain, sometimes referred to as a jump process. Each element of the one-step transition probability matrix of the EMC, S, is denoted by sij, and represents the conditional probability of transitioning from state i into state j. These conditional probabilities may be found byResearch has reported the application and usefulness of Markov chains in a wide range of topics such as physics, chemistry, medicine, music, game theory and sports.

[ "Algorithm", "Statistics", "Machine learning", "Mathematical optimization", "markov systems", "probabilistic model checking", "finite state", "markov random walk", "state markov chain" ]
Parent Topic
Child Topic
    No Parent Topic