- Source: Discrete-time Markov chain
In probability, 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
X
0
,
X
1
,
X
2
,
.
.
.
{\displaystyle X_{0},X_{1},X_{2},...}
then
X
0
{\displaystyle X_{0}}
is the state which the machine starts in and
X
10
{\displaystyle X_{10}}
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.
A Markov chain can be described by a stochastic 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 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
X
0
,
X
1
,
X
2
,
.
.
.
{\displaystyle X_{0},X_{1},X_{2},...}
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
∣
X
1
=
x
1
,
X
2
=
x
2
,
…
,
X
n
=
x
n
)
=
Pr
(
X
n
+
1
=
x
∣
X
n
=
x
n
)
,
{\displaystyle \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
,
…
,
X
n
=
x
n
)
>
0.
{\displaystyle \Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.}
The possible values of Xi form a countable set S called the state space of the chain.
Markov chains are often described by a sequence of directed graphs, 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,
Pr
(
X
n
+
1
=
x
∣
X
n
=
x
n
)
.
{\displaystyle \Pr(X_{n+1}=x\mid X_{n}=x_{n}).}
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
Pr
(
X
1
=
x
1
)
.
{\displaystyle \Pr(X_{1}=x_{1}).}
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
Pr
(
X
n
=
x
∣
X
1
=
x
1
)
{\displaystyle \Pr(X_{n}=x\mid X_{1}=x_{1})}
of the machine's state can be analyzed as the statistical behavior of the machine with an element
x
1
{\displaystyle x_{1}}
of the state space as input, or as the behavior of the machine with the initial distribution
Pr
(
X
1
=
y
)
=
[
x
1
=
y
]
{\displaystyle \Pr(X_{1}=y)=[x_{1}=y]}
of states as input, where
[
P
]
{\displaystyle [P]}
is the Iverson bracket.
= Variations
=Time-homogeneous Markov chains (or stationary Markov chains) are processes where
Pr
(
X
n
+
1
=
x
∣
X
n
=
y
)
=
Pr
(
X
n
=
x
∣
X
n
−
1
=
y
)
{\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}
for all n. The probability of the transition is independent of n.
A Markov chain with memory (or a Markov chain of order m)
where m is finite, is a process satisfying
Pr
(
X
n
=
x
n
∣
X
n
−
1
=
x
n
−
1
,
X
n
−
2
=
x
n
−
2
,
…
,
X
1
=
x
1
)
=
Pr
(
X
n
=
x
n
∣
X
n
−
1
=
x
n
−
1
,
X
n
−
2
=
x
n
−
2
,
…
,
X
n
−
m
=
x
n
−
m
)
for
n
>
m
{\displaystyle {\begin{aligned}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\={}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}
In other words, the future state depends on the past m states. It is possible to construct a chain
(
Y
n
)
{\displaystyle (Y_{n})}
from
(
X
n
)
{\displaystyle (X_{n})}
which has the 'classical' Markov property by taking as state space the ordered m-tuples of X values, ie.
Y
n
=
(
X
n
,
X
n
−
1
,
…
,
X
n
−
m
+
1
)
{\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}
.
n-step transitions
The probability of going from state i to state j in n time steps is
p
i
j
(
n
)
=
Pr
(
X
n
=
j
∣
X
0
=
i
)
{\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)}
and the single-step transition is
p
i
j
=
Pr
(
X
1
=
j
∣
X
0
=
i
)
.
{\displaystyle p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).}
For a time-homogeneous Markov chain:
p
i
j
(
n
)
=
Pr
(
X
k
+
n
=
j
∣
X
k
=
i
)
{\displaystyle p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)}
and
p
i
j
=
Pr
(
X
k
+
1
=
j
∣
X
k
=
i
)
.
{\displaystyle p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i).}
The n-step transition probabilities satisfy the Chapman–Kolmogorov equation, that for any k such that 0 < k < n,
p
i
j
(
n
)
=
∑
r
∈
S
p
i
r
(
k
)
p
r
j
(
n
−
k
)
{\displaystyle p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}}
where S is the state space of the Markov chain.
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
Pr
(
X
n
=
j
)
=
∑
r
∈
S
p
r
j
Pr
(
X
n
−
1
=
r
)
=
∑
r
∈
S
p
r
j
(
n
)
Pr
(
X
0
=
r
)
.
{\displaystyle \Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).}
(The superscript (n) is an index, and not an exponent).
Communicating classes and properties
A state j is said to be accessible from a state i (written i → j) if a system started in state i has a non-zero probability of transitioning into state j at some point. Formally, state j is accessible from state i if there exists an integer nij ≥ 0 such that
Pr
(
X
n
i
j
=
j
∣
X
0
=
i
)
=
p
i
j
(
n
i
j
)
>
0.
{\displaystyle \Pr(X_{n_{ij}}=j\mid X_{0}=i)=p_{ij}^{(n_{ij})}>0.}
A state i is said to communicate with state j (written i ↔ j) if both i → j and j → i. A communicating class is a maximal set of states C such that every pair of states in C communicates with each other. Communication is an equivalence relation, and communicating classes are the equivalence classes of this relation.
A communicating class is closed if the probability of leaving the class is zero, namely if i is in C but j is not, then j is not accessible from i. The set of communicating classes forms a directed, acyclic graph by inheriting the arrows from the original state space. A communicating class is closed if and only if it has no outgoing arrows in this graph.
A state i is said to be essential or final if for all j such that i → j it is also true that j → i. A state i is inessential if it is not essential. A state is final if and only if its communicating class is closed.
A Markov chain is said to be irreducible if its state space is a single communicating class; in other words, if it is possible to get to any state from any state.: 20
= Periodicity
=A state
i
{\displaystyle i}
has period
k
{\displaystyle k}
if any return to state
i
{\displaystyle i}
must occur in multiples of
k
{\displaystyle k}
time steps. Formally, the period of state
i
{\displaystyle i}
is defined as
k
=
gcd
{
n
>
0
:
Pr
(
X
n
=
i
∣
X
0
=
i
)
>
0
}
{\displaystyle k=\gcd\{n>0:\Pr(X_{n}=i\mid X_{0}=i)>0\}}
(where
gcd
{\displaystyle \gcd }
is the greatest common divisor) provided that this set is not empty. Otherwise the period is not defined. Note that even though a state has period
k
{\displaystyle k}
, it may not be possible to reach the state in
k
{\displaystyle k}
steps. For example, suppose it is possible to return to the state in
{
6
,
8
,
10
,
12
,
…
}
{\displaystyle \{6,~8,~10,~12,\dots \}}
time steps;
k
{\displaystyle k}
would be
2
{\displaystyle 2}
, even though
2
{\displaystyle 2}
does not appear in this list.
If
k
=
1
{\displaystyle k=1}
, then the state is said to be aperiodic. Otherwise (
k
>
1
{\displaystyle k>1}
), the state is said to be periodic with period
k
{\displaystyle k}
. Periodicity is a class property—that is, if a state has period
k
{\displaystyle k}
then every state in its communicating class has period
k
{\displaystyle k}
.
= Transience and 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 to i. Formally, let the random variable Ti be the first return time to state i (the "hitting time"):
T
i
=
inf
{
n
≥
1
:
X
n
=
i
}
.
{\displaystyle T_{i}=\inf\{n\geq 1:X_{n}=i\}.}
The number
f
i
i
(
n
)
=
Pr
(
T
i
=
n
∣
X
0
=
i
)
{\displaystyle f_{ii}^{(n)}=\Pr(T_{i}=n\mid X_{0}=i)}
is the probability that we return to state i for the first time after n steps.
Therefore, state i is transient if
Pr
(
T
i
<
∞
∣
X
0
=
i
)
=
∑
n
=
1
∞
f
i
i
(
n
)
<
1.
{\displaystyle \Pr(T_{i}<\infty \mid X_{0}=i)=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1.}
State i is recurrent (or persistent) if it is not transient. Recurrence and transience are class properties, that is, they either hold or do not hold equally for all members of a communicating class.
A state i is recurrent if and only if the expected number of visits to i is infinite:
∑
n
=
0
∞
p
i
i
(
n
)
=
∞
.
{\displaystyle \sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .}
Positive recurrence
Even if the hitting time is finite with probability 1, it need not have a finite expectation. The mean recurrence time at state i is the expected return time Mi:
M
i
=
E
[
T
i
]
=
∑
n
=
1
∞
n
⋅
f
i
i
(
n
)
.
{\displaystyle M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.}
State i is positive recurrent (or non-null persistent) if Mi is finite; otherwise, state i is null recurrent (or null persistent). Positive and null recurrence are classes properties.
Absorbing states
A state i is called absorbing if it is impossible to leave this state. Therefore, the state i is absorbing if and only if
p
i
i
=
1
and
p
i
j
=
0
for
i
≠
j
.
{\displaystyle p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.}
If every state can reach an absorbing state, then the Markov chain is an absorbing Markov chain.
= Reversible Markov chain
=A Markov chain is said to be reversible if there is a probability distribution π over its states such that
π
i
Pr
(
X
n
+
1
=
j
∣
X
n
=
i
)
=
π
j
Pr
(
X
n
+
1
=
i
∣
X
n
=
j
)
{\displaystyle \pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)}
for all times n and all states i and j. This condition is known as the detailed balance condition (or local balance equation).
Considering a fixed arbitrary time n and using the shorthand
p
i
j
=
Pr
(
X
n
+
1
=
j
∣
X
n
=
i
)
,
{\displaystyle p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i)\,,}
the detailed balance equation can be written more compactly as
π
i
p
i
j
=
π
j
p
j
i
.
{\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}\,.}
The single time-step from n to n + 1 can be thought of as each person i having πi dollars initially and paying each person j a fraction pij of it. The detailed balance condition states that upon each payment, the other person pays exactly the same amount of money back. Clearly the total amount of money π each person has remains the same after the time-step, since every dollar spent is balanced by a corresponding dollar received. This can be shown more formally by the equality
∑
i
π
i
p
i
j
=
∑
i
π
j
p
j
i
=
π
j
∑
i
p
j
i
=
π
j
,
{\displaystyle \sum _{i}\pi _{i}p_{ij}=\sum _{i}\pi _{j}p_{ji}=\pi _{j}\sum _{i}p_{ji}=\pi _{j}\,,}
which essentially states that the total amount of money person j receives (including from himself) during the time-step equals the amount of money he pays others, which equals all the money he initially had because it was assumed that all money is spent (that is, pji sums to 1 over i). The assumption is a technical one, because the money not really used is simply thought of as being paid from person j to himself (that is, pjj is not necessarily zero).
As n was arbitrary, this reasoning holds for any n, and therefore for reversible Markov chains π is always a steady-state distribution of Pr(Xn+1 = j | Xn = i) for every n.
If the Markov chain begins in the steady-state distribution, that is, if
Pr
(
X
0
=
i
)
=
π
i
{\displaystyle \Pr(X_{0}=i)=\pi _{i}}
, then
Pr
(
X
n
=
i
)
=
π
i
{\displaystyle \Pr(X_{n}=i)=\pi _{i}}
for all
n
{\displaystyle n}
and the detailed balance equation can be written as
Pr
(
X
n
=
i
,
X
n
+
1
=
j
)
=
Pr
(
X
n
+
1
=
i
,
X
n
=
j
)
.
{\displaystyle \Pr(X_{n}=i,X_{n+1}=j)=\Pr(X_{n+1}=i,X_{n}=j)\,.}
The left- and right-hand sides of this last equation are identical except for a reversing of the time indices n and n + 1.
Kolmogorov's criterion gives a necessary and sufficient condition for a Markov chain to be reversible directly from the transition matrix probabilities. The criterion requires that the products of probabilities around every closed loop are the same in both directions around the loop.
Reversible Markov chains are common in Markov chain Monte Carlo (MCMC) approaches because the detailed balance equation for a desired distribution π necessarily implies that the Markov chain has been constructed so that π is a steady-state distribution. Even with time-inhomogeneous Markov chains, where multiple transition matrices are used, if each such transition matrix exhibits detailed balance with the desired π distribution, this necessarily implies that π is a steady-state distribution of the Markov chain.
Closest reversible Markov chain
For any time-homogeneous Markov chain given by a transition matrix
P
∈
R
n
×
n
{\displaystyle P\in \mathbb {R} ^{n\times n}}
, any norm
|
|
⋅
|
|
{\displaystyle ||\cdot ||}
on
R
n
×
n
{\displaystyle \mathbb {R} ^{n\times n}}
which is induced by a scalar product, and any probability vector
π
{\displaystyle \pi }
, there exists a unique transition matrix
P
∗
{\displaystyle P^{*}}
which is reversible according to
π
{\displaystyle \pi }
and which is closest to
P
{\displaystyle P}
according to the norm
|
|
⋅
|
|
.
{\displaystyle ||\cdot ||.}
The matrix
P
∗
{\displaystyle P^{*}}
can be computed by solving a quadratic-convex optimization problem.
For example, consider the following Markov chain:
This Markov chain is not reversible. According to the Frobenius Norm the closest reversible Markov chain according to
π
=
(
1
3
,
1
3
,
1
3
)
{\displaystyle \pi =\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}
can be computed as
If we choose the probability vector randomly as
π
=
(
1
4
,
1
4
,
1
2
)
{\displaystyle \pi =\left({\frac {1}{4}},{\frac {1}{4}},{\frac {1}{2}}\right)}
, then the closest reversible Markov chain according to the Frobenius norm is approximately given by
Stationary distributions
A distribution
π
{\displaystyle \pi }
is a stationary distribution of the Markov chain with stochastic matrix
P
{\displaystyle P}
if and only if
π
P
=
π
{\displaystyle \pi P=\pi }
. This can be written as:
∀
j
∈
S
:
∑
i
∈
S
π
i
p
i
j
=
π
j
{\displaystyle \forall j\in \mathbb {S} :\sum _{i\in \mathbb {S} }\pi _{i}p_{ij}=\pi _{j}}
.
This condition implies that
π
P
n
=
π
{\displaystyle \pi P^{n}=\pi }
and hence if the Markov chain
(
X
n
,
n
∈
N
)
{\displaystyle (X_{n},n\in \mathbb {N} )}
has initial distribution
X
0
=
π
{\displaystyle X_{0}=\pi }
then
X
n
=
π
{\displaystyle X_{n}=\pi }
(in distribution) for any
n
∈
N
{\displaystyle n\in \mathbb {N} }
.
If a Markov chain is irreducible then it has a stationary distribution if and only if it is positive recurrent, in which case the unique such distribution is given by
π
i
=
1
M
i
{\displaystyle \pi _{i}={\frac {1}{M_{i}}}}
where
M
i
=
E
(
T
i
)
{\displaystyle M_{i}=\mathbb {E} (T_{i})}
is the mean recurrence time of i.
If a chain has more than one closed communicating class, its stationary distributions will not be unique (consider any closed communicating class
C
i
{\displaystyle C_{i}}
in the chain; each one will have its own unique stationary distribution
π
i
{\displaystyle \pi _{i}}
. Extending these distributions to the overall chain, setting all values to zero outside the communication class, yields that the set of invariant measures of the original chain is the set of all convex combinations of the
π
i
{\displaystyle \pi _{i}}
's). However, if a state j is aperiodic, then
lim
n
→
∞
p
j
j
(
n
)
=
C
M
j
{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{jj}^{(n)}={\tfrac {C}{M_{j}}}}
and for any other state i, let fij be the probability that the chain ever visits state j if it starts at i,
lim
n
→
∞
p
i
j
(
n
)
=
C
f
i
j
M
j
.
{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ij}^{(n)}=C{\tfrac {f_{ij}}{M_{j}}}.}
If a state i is periodic with period k > 1 then the limit
lim
n
→
∞
p
i
i
(
n
)
{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(n)}}
does not exist, although the limit
lim
n
→
∞
p
i
i
(
k
n
+
r
)
{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(kn+r)}}
does exist for every integer r.
= Steady-state analysis and the time-inhomogeneous Markov chain
=A Markov chain need not necessarily be time-homogeneous to have an equilibrium distribution. If there is a probability distribution over states
π
{\displaystyle {\boldsymbol {\pi }}}
such that
π
j
=
∑
i
∈
S
π
i
Pr
(
X
n
+
1
=
j
∣
X
n
=
i
)
{\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}\,\Pr(X_{n+1}=j\mid X_{n}=i)}
for every state j and every time n then
π
{\displaystyle {\boldsymbol {\pi }}}
is an equilibrium distribution of the Markov chain. Such can occur in Markov chain Monte Carlo (MCMC) methods in situations where a number of different transition matrices are used, because each is efficient for a particular kind of mixing, but each matrix respects a shared equilibrium distribution.
Hitting times
The 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.
= Expected hitting times
=For a subset of states A ⊆ S, the vector kA of hitting times (where element
k
i
A
{\displaystyle k_{i}^{A}}
represents the expected value, starting in state i that the chain enters one of the states in the set A) is the minimal non-negative solution to
k
i
A
=
0
for
i
∈
A
−
∑
j
∈
S
q
i
j
k
j
A
=
1
for
i
∉
A
.
{\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}
Ergodic theorem
An instance of ergodic theory, the ergodic theorem for states that for an irreducible aperiodic Markov chain, for any two states i and j,
p
i
,
j
(
n
)
→
1
M
j
{\displaystyle p_{i,j}^{(n)}\rightarrow {\frac {1}{M_{j}}}}
as
n
→
∞
{\displaystyle n\rightarrow \infty }
.
Notes
References
Kata Kunci Pencarian:
- Daftar algoritme
- Discrete-time Markov chain
- Markov chain
- Continuous-time Markov chain
- Absorbing Markov chain
- Markov renewal process
- List of things named after Andrey Markov
- Hidden Markov model
- Discrete phase-type distribution
- Markov property
- Stationary distribution
