Continuous-time Markov chain

From Wikipedia, the free encyclopedia
  (Redirected from Continuous-time Markov process)
Jump to: navigation, search

In probability theory, a continuous-time Markov chain (CTMC[1] or continuous-time Markov process[2]) is a mathematical model which takes values in some finite or countable set and for which the time spent in each state takes non-negative real values and has an exponential distribution. It is a continuous-time stochastic process with the Markov property which means that future behaviour of the model (both remaining time in current state and next state) depends only on the current state of the model and not on historical behaviour. The model is a continuous-time version of the Markov chain model, named because the output from such a process is a sequence (or chain) of states.

Definitions[edit]

A continuous-time Markov chain (Xt)t ≥ 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.

There are three equivalent definitions of the process.[3]

Infinitesimal definition[edit]

Let Xt be the random variable describing the state of the process at time t, and assume that the process is in a state i at time t. Then Xt + h is independent of previous values (Xs : s≤ t) and as h → 0 uniformly in t for all j

\Pr(X(t+h) = j | X(t) = i) = \delta_{ij} + q_{ij}h + o(h)

using little-o notation. The qij can be seen as measuring how quickly the transition from i to j happens

Jump chain/holding time definition[edit]

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 the distribution of Si is given by −qYiYi.

Transition probability definition[edit]

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} | 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.

Properties[edit]

Irreducibility[edit]

The state space S can be partitioned into communicating classes. i and j are said to communicate (and therefore be in the same communicating class) if it is possible to get to state j from state i, that is if

\operatorname{Pr}_i(X_t=j \text{ for some } t \geq 0)>0.

A CTMC is irreducible if there is a single communicating class.[3][4]

Recurrence and transience[edit]

A state i is recurrent if, starting in state i, the probability the process returns unboundedly many times to the state is 1, that is[5]

\operatorname{Pr}_i(\{t \geq 0 : X_t = i \} \text{ is unbounded}) = 1

and a state i is transient if this quantity has probability zero,[5]

\operatorname{Pr}_i(\{t \geq 0 : X_t = i \} \text{ is unbounded}) = 0.

If the expected return time (the time starting in state i until the next visit to state i) is finite the state is positive recurrent, otherwise it is null recurrent.

Transient behaviour[edit]

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 equation

P'(t) = P(t) Q

where the prime denotes differentiation with respect to t. The solution to this equation is given by a matrix exponential

P(t) = e^{tQ}

In a simple case such as a CTMC on the state space {1,2}. The general Q matrix for such a process is the following 2 × 2 matrix with α,β > 0

Q = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}.

The above relation for forward matrix can be solved explicitly in this case to give

P(t) = \begin{pmatrix}
\frac{\beta}{\alpha+\beta} + \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} - \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} \\
\frac{\beta}{\alpha+\beta} - \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} + \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t}
\end{pmatrix}

However, direct solutions are complicated to compute for larger matrices. The fact that Q is the generator for a semigroup of matrices

P(t+s) = e^{Q(t+s)} = e^{tQ} e^{sQ} = P(t) P(s)

is used.

Stationary distribution[edit]

The 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 by

P(t) = \begin{pmatrix}
\frac{\beta}{\alpha+\beta} + \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} - \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} \\
\frac{\beta}{\alpha+\beta} - \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} + \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t}
\end{pmatrix}

as t → ∞ the distribution tends to

P_\pi = \begin{pmatrix}
\frac{\beta}{\alpha+\beta} &
\frac{\alpha}{\alpha+\beta} \\
\frac{\beta}{\alpha+\beta}  &
\frac{\alpha}{\alpha+\beta} 
\end{pmatrix}

Observe that each row has the same distribution as this does not depend on starting state. The row vector π may be found by solving[5]

\pi Q = 0.

with the additional constraint that

\sum_{i \in S} \pi_i = 1.

Example[edit]

Directed graph representation of a continuous-time Markov chain describing the state of financial markets (note: numbers are made-up).

The image to the right describes a continuous-time Markov chain with state-space {Bull market, Bear market, Stagnant market} and transition rate matrix

Q=\begin{pmatrix}
-0.025 & 0.02 & 0.005 \\
0.3 & -0.5 & 0.2 \\
0.02 & 0.4 & -0.42
\end{pmatrix}.

The stationary distribution of this chain can be found by solving π Q = 0 subject to the contraint that elements must sum to 1 to obtain

\pi = \begin{pmatrix}0.885 & 0.071 & 0.044 \end{pmatrix}.

Hitting times[edit]

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[edit]

For a subset of states A ⊆ S, the vector kA of hitting times (where element kAi 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[5]

\begin{align}
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{align}

Time reversal[edit]

For a CTMC Xt, the time-reversed process is defined to be \scriptstyle \hat X_t = X_{T-t}. By Kelly's lemma this process has the same stationary distribution as the forward process.

A chain is said to be reversible if the reversed process is the same as the forward process. Kolmogorov's criterion states that the necessary and sufficient condition for a process to be reversible is that the product of transition rates around a closed loop must be the same in both directions.

Embedded Markov chain[edit]

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 by


s_{ij} = \begin{cases}
\frac{q_{ij}}{\sum_{k \neq i} q_{ik}} & \text{if } i \neq j \\
0 & \text{otherwise}.
\end{cases}

From this, S may be written as

S = I - \left( \operatorname{diag}(Q) \right)^{-1} Q

where I is the identity matrix and diag(Q) is the diagonal matrix formed by selecting the main diagonal from the matrix Q and setting all other elements to zero.

To find the stationary probability distribution vector, we must next find \phi such that

\phi S = \phi, \,

with \phi being a row vector, such that all elements in \phi are greater than 0 and ||\phi||_1 = 1. From this, π may be found as

\pi = {-\phi (\operatorname{diag}(Q))^{-1} \over \left\|  \phi (\operatorname{diag}(Q))^{-1} \right\|_1}.

Note that S may be periodic, even if Q is not. Once π is found, it must be normalized to a unit vector.

Another discrete-time process that may be derived from a continuous-time Markov chain is a δ-skeleton—the (discrete-time) Markov chain formed by observing X(t) at intervals of δ units of time. The random variables X(0), X(δ), X(2δ), ... give the sequence of states visited by the δ-skeleton.

Applications[edit]

Markov chains are used to describe physical processes where a system evolves in constant time. Sometimes, rather than a single systems, they are applied to an ensemble of identical, independent systems, and the probabilities are used to find how many members of the ensemble are in a given state. A master equation treatment is often used to analyse systems that evolve as Markov chains,[citation needed] with approximations possible for complicated systems .[citation needed]

Chemical reactions[edit]

Imagine a large number n of molecules in solution in state A, each of which can undergo a chemical reaction to state B with a certain average rate. Perhaps the molecule is an enzyme, and the states refer to how it is folded. The state of any single enzyme follows a Markov chains, and since the molecules are essentially independent of each other, the number of molecules in state A or B at a time is n times the probability a given molecule is in that state.

Queueing theory[edit]

Main article: Queueing theory

Numerous queueing models use continuous-time Markov chains. For example, an M/M/1 queue is a CTMC on the non-negative integers where upward transitions from i to i + 1 occur at rate λ according to a Poisson process and describe job arrivals, while transitions from i to i – 1 (for i > 1) occur at rate μ (job service times are exponentially distributed) and describe completed services (departures) from the queue.

Extensions[edit]

A time dependent (time heterogeneous) CTMC is as above, but with the transition rate matrix a function of time Q(t).

See also[edit]

References[edit]

  1. ^ Baier, C.; Katoen, J. P.; Hermanns, H. (1999). "Approximative Symbolic Model Checking of Continuous-Time Markov Chains". "CONCUR'99 Concurrency Theory". Lecture Notes in Computer Science 1664. p. 146. doi:10.1007/3-540-48320-9_12. ISBN 978-3-540-66425-3.  edit
  2. ^ Serfozo, R. F. (1979). "Technical Note--An Equivalence Between Continuous and Discrete Time Markov Decision Processes". Operations Research 27 (3): 616–620. doi:10.1287/opre.27.3.616. JSTOR 170221.  edit
  3. ^ a b Norris, J. R. (1997). "Continuous-time Markov chains I". "Markov Chains". p. 60. doi:10.1017/CBO9780511810633.004. ISBN 9780511810633.  edit
  4. ^ Norris, J. R. (1997). "Discrete-time Markov chains". "Markov Chains". p. 1. doi:10.1017/CBO9780511810633.003. ISBN 9780511810633.  edit
  5. ^ a b c d Norris, J. R. (1997). "Continuous-time Markov chains II". "Markov Chains". p. 108. doi:10.1017/CBO9780511810633.005. ISBN 9780511810633.  edit
  • William J. Stewart (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press. pp. 17–23. ISBN 0-691-03699-3.