In
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
, a discrete-time Markov chain (DTMC) is a sequence of random variables, known as a
stochastic process, in which the value of the next variable depends only on the value of the current variable, and not any variables in the past. For instance, a machine may have two states, ''A'' and ''E''. When it is in state ''A'', there is a 40% chance of it moving to state ''E'' and a 60% chance of it remaining in state ''A''. When it is in state ''E'', there is a 70% chance of it moving to ''A'' and a 30% chance of it staying in ''E''. The sequence of states of the machine is a Markov chain. If we denote the chain by
then
is the state which the machine starts in and
is the
random variable describing its state after 10 transitions. The process continues forever, indexed by the
natural numbers.
An example of a stochastic process which is not a Markov chain is the model of a machine which has states ''A'' and ''E'' and moves to ''A'' from either state with 50% chance if it has ever visited ''A'' before, and 20% chance if it has never visited ''A'' before (leaving a 50% or 80% chance that the machine moves to ''E''). This is because the behavior of the machine depends on the whole history—if the machine is in ''E'', it may have a 50% or 20% chance of moving to ''A'', depending on its past values. Hence, it does not have the
Markov property
In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It is named after the Russian mathematician Andrey Markov. The term strong Markov property is similar to the Markov propert ...
.
A Markov chain can be described by a
stochastic matrix
In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It is also called a probability matrix, transition matrix, ...
, which lists the probabilities of moving to each state from any individual state. From this matrix, the probability of being in a particular state ''n'' steps in the future can be calculated. A Markov chain's state space can be partitioned into communicating classes that describe which states are reachable from each other (in one transition or in many). Each state can be described as transient or recurrent, depending on the probability of the chain ever returning to that state. Markov chains can have properties including periodicity, reversibility and stationarity. A
continuous-time Markov chain
A continuous-time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of ...
is like a discrete-time Markov chain, but it moves states continuously through time rather than as discrete time steps. Other stochastic processes can satisfy the Markov property, the property that past behavior does not affect the process, only the present state.
Definition
A discrete-time Markov chain is a sequence of
random variables
with the
Markov property
In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It is named after the Russian mathematician Andrey Markov. The term strong Markov property is similar to the Markov propert ...
, namely that the probability of moving to the next state depends only on the present state and not on the previous states:
:
if both
conditional probabilities
In probability theory, conditional probability is a measure of the probability of an event occurring, given that another event (by assumption, presumption, assertion or evidence) has already occurred. This particular method relies on event B occur ...
are well defined, that is, if
The possible values of ''X''
''i'' form a
countable set ''S'' called the state space of the chain.
Markov chains are often described by a sequence of
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, where the edges of graph ''n'' are labeled by the probabilities of going from one state at time ''n'' to the other states at time ''n'' + 1,
The same information is represented by the transition matrix from time ''n'' to time ''n'' + 1. However, Markov chains are frequently assumed to be time-homogeneous (see variations below), in which case the graph and matrix are independent of ''n'' and are thus not presented as sequences.
These descriptions highlight the structure of the Markov chain that is independent of the initial distribution
When time-homogeneous, the chain can be interpreted as a
state machine assigning a probability of hopping from each vertex or state to an adjacent one. The probability
of the machine's state can be analyzed as the statistical behavior of the machine with an element
of the state space as input, or as the behavior of the machine with the initial distribution