Discrete-time Markov chain 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: :\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
Xi form a
countable set S called the state space of the chain.
Variations • Time-homogeneous Markov chains are processes where \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. • Stationary Markov chains are processes where \Pr(X_{0}=x_0, X_{1} = x_1, \ldots, X_{k} = x_k) = \Pr(X_{n}=x_0, X_{n+1} = x_1, \ldots, X_{n+k} = x_k) for all
n and
k. Every stationary chain can be proved to be time-homogeneous by Bayes' rule.A necessary and sufficient condition for a time-homogeneous Markov chain to be stationary is that the distribution of X_0 is a stationary distribution of the Markov chain. • A Markov chain with memory (or a Markov chain of order
m) where
m is finite, is a process satisfying \begin{align} {} &\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{align} In other words, the future state depends on the past
m states. It is possible to construct a chain (Y_n) from (X_n) which has the 'classical' Markov property by taking as state space the ordered
m-tuples of
X values, i.e., Y_n= \left( X_n,X_{n-1},\ldots,X_{n-m+1} \right).
Finite state space 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.
Stationary distribution relation to eigenvectors and simplices 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. By comparing this definition with that of an
eigenvector we see that the two concepts are related and that :\pi=\frac{e}{\sum_i{e_i}} is a normalized (\sum_i \pi_i=1) multiple of a left eigenvector
e of the transition matrix
P with an
eigenvalue of 1. If there is more than one unit eigenvector then a weighted sum of the corresponding stationary states is also a stationary state. But for a Markov chain one is usually more interested in a stationary state that is the limit of the sequence of distributions for some initial distribution. The values of a stationary distribution \textstyle \pi_i are associated with the state space of
P and its eigenvectors have their relative proportions preserved. Since the components of π are positive and the constraint that their sum is unity can be rewritten as \sum_i 1 \cdot \pi_i=1 we see that the
dot product of π with a vector whose components are all 1 is unity and that π lies on a
simplex.
Time-homogeneous Markov chain with a finite state space If the Markov chain is time-homogeneous, then the transition matrix
P is the same after each step, so the
k-step transition probability can be computed as the
k-th power of the transition matrix,
Pk. 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 : :\lim_{k\to\infty}\mathbf{P}^k=\mathbf{1}\pi where
1 is the column vector with all entries equal to 1. This is stated by the
Perron–Frobenius theorem. If, by whatever means, \lim_{k\to\infty}\mathbf{P}^k 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. For some stochastic matrices
P, the limit \lim_{k\to\infty}\mathbf{P}^k does not exist while the stationary distribution does, as shown by this example: :\mathbf P=\begin{pmatrix} 0& 1\\ 1& 0 \end{pmatrix} \qquad \mathbf P^{2k}=I \qquad \mathbf P^{2k+1}=\mathbf P :\begin{pmatrix}\frac{1}{2}&\frac{1}{2}\end{pmatrix}\begin{pmatrix} 0& 1\\ 1& 0 \end{pmatrix}=\begin{pmatrix}\frac{1}{2}&\frac{1}{2}\end{pmatrix} (This example illustrates a periodic Markov chain.) Because there are a number of different special cases to consider, the process of finding this limit if it exists can be a lengthy task. However, there are many techniques that can assist in finding this limit. Let
P be an
n×
n matrix, and define \mathbf{Q} = \lim_{k\to\infty}\mathbf{P}^k. It is always true that :\mathbf{QP} = \mathbf{Q}. Subtracting
Q from both sides and factoring then yields :\mathbf{Q}(\mathbf{P} - \mathbf{I}_{n}) = \mathbf{0}_{n,n} , 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 (see the definition above). It is sometimes sufficient to use the matrix equation above and the fact that
Q is a stochastic matrix to solve for
Q. Including the fact that the sum of each the rows in
P is 1, there are
n+1 equations for determining
n unknowns, so it is computationally easier if on the one hand one selects one row in
Q and substitutes each of its elements by one, and on the other one substitutes the corresponding element (the one in the same column) in the vector
0, and next left-multiplies this latter vector by the inverse of transformed former matrix to find
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. If [
f(
P −
In)]−1 exists then) Let
U be the matrix of eigenvectors (each normalized to having an L2 norm equal to 1) where each column is a left eigenvector of
P and let
Σ be the diagonal matrix of left eigenvalues of
P, that is,
Σ = diag(
λ1,
λ2,
λ3,...,
λn). Then by
eigendecomposition : \mathbf{P} = \mathbf{U\Sigma U}^{-1} . Let the eigenvalues be enumerated such that: : 1 = |\lambda_1 |> |\lambda_2 | \geq |\lambda_3 | \geq \cdots \geq |\lambda_n|. Since
P is a row stochastic matrix, its largest left eigenvalue is 1. If there is a unique stationary distribution, then the largest eigenvalue and the corresponding eigenvector is unique too (because there is no other '
which solves the stationary distribution equation above). Let u'
i be the
i-th column of
U matrix, that is,
ui is the left eigenvector of
P corresponding to λ
i. Also let
x be a length
n row vector that represents a valid probability distribution; since the eigenvectors
ui span \R^n, we can write : \mathbf{x}^\mathsf{T} = \sum_{i=1}^n a_i \mathbf{u}_i, \qquad a_i \in \R. If we multiply
x with
P from right and continue this operation with the results, in the end we get the stationary distribution '
. In other words, = a1 u1 ← xPP...P = xP'
k as
k → ∞. That means :\begin{align} \boldsymbol{\pi}^{(k)} &= \mathbf{x} \left (\mathbf{U\Sigma U}^{-1} \right ) \left (\mathbf{U\Sigma U}^{-1} \right )\cdots \left (\mathbf{U\Sigma U}^{-1} \right ) \\ &= \mathbf{xU\Sigma}^k \mathbf{U}^{-1} \\ &= \left (a_1\mathbf{u}_1^\mathsf{T} + a_2\mathbf{u}_2^\mathsf{T} + \cdots + a_n\mathbf{u}_n^\mathsf{T} \right )\mathbf{U\Sigma}^k\mathbf{U}^{-1} \\ &= a_1\lambda_1^k\mathbf{u}_1^\mathsf{T} + a_2\lambda_2^k\mathbf{u}_2^\mathsf{T} + \cdots + a_n\lambda_n^k\mathbf{u}_n^\mathsf{T} && u_i \bot u_j \text{ for } i\neq j \\ & = \lambda_1^k\left\{a_1\mathbf{u}_1^\mathsf{T} + a_2\left(\frac{\lambda_2}{\lambda_1}\right)^k\mathbf{u}_2^\mathsf{T} + a_3\left(\frac{\lambda_3}{\lambda_1}\right)^k\mathbf{u}_3^\mathsf{T} + \cdots + a_n\left(\frac{\lambda_n}{\lambda_1}\right)^k\mathbf{u}_n^\mathsf{T}\right\} \end{align} Since '
is parallel to u1(normalized by L2 norm) and '(
k) is a probability vector, ''''
(k
) approaches to a1 u1 = ''
as k
→ ∞ with a speed in the order of λ
2/λ
1 exponentially. This follows because |\lambda_2| \geq \cdots \geq |\lambda_n|, hence λ
2/λ
1 is the dominant term. The smaller the ratio is, the faster the convergence is. Random noise in the state distribution '''' can also speed up this convergence to the stationary distribution.
Continuous-time Markov chain 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
qij are non-negative and describe the rate of the process transitions from state
i to state
j. The elements
qii 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.
Infinitesimal definition Let X_t be the random variable describing the state of the process at time
t, and assume the process is in a state
i at time
t. Then, knowing X_t = i, X_{t+h}=j is independent of previous values \left( X_s : s , and as
h → 0 for all
j and for all
t, \Pr(X(t+h) = j \mid X(t) = i) = \delta_{ij} + q_{ij}h + o(h), where \delta_{ij} is the
Kronecker delta, using the
little-o notation. The q_{ij} can be seen as measuring how quickly the transition from
i to
j happens.
Jump chain/holding time definition Define a discrete-time Markov chain
Yn to describe the
nth jump of the process and variables
S1,
S2,
S3, ... to describe holding times in each of the states where
Si follows the
exponential distribution with rate parameter −''q'
Y'i'
Y'i''.
Transition probability definition For any value
n = 0, 1, 2, 3, ... and times indexed up to this value of
n:
t0,
t1,
t2, ... and all states recorded at these times
i0,
i1,
i2,
i3, ... it holds that :\Pr(X_{t_{n+1}} = i_{n+1} \mid X_{t_0} = i_0 , X_{t_1} = i_1 , \ldots, X_{t_n} = i_n ) = p_{i_n i_{n+1}}( t_{n+1} - t_n) where
pij is the solution of the
forward equation (a
first-order differential equation) :P'(t) = P(t) Q with initial condition P(0) is the
identity matrix.
Locally interacting Markov chains "Locally interacting Markov chains" are Markov chains with an evolution that takes into account the state of other Markov chains. This corresponds to the situation when the state space has a (Cartesian-) product form. See
interacting particle system and
stochastic cellular automata (probabilistic cellular automata). See for instance
Interaction of Markov Processes or.
Discrete-time Markov process with general state space Harris chains Many results for discrete-time Markov chains with finite state space can be generalized to chains with uncountable state space through
Harris chains. The use of Markov chains in
Markov chain Monte Carlo methods covers cases where the process follows a continuous state space.
Continuous-time Markov process with general state space 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., • P_t is
Markov kernel for all t\geq 0, • 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), • 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, A_1,...,A_n\in\mathcal B(S) the underlying probability measure P satisfies : 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. In other words, Markov processes can be defined either as stochastic processes X on a filtered probability space, or indirectly in terms of a transition semigroup (i.e., the transition probabilities of the process), which induces a probability space under which X has the Markov property. ==Properties==