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 state space 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.



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

Infinitesimal definition[edit]



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


Jump chain/holding time definition[edit]


Transition probability definition[edit]


\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)


P'(t) = P(t) Q

with initial condition P(0) is the identity matrix.



A state j is said to be accessible from a state i (written i → j) if it is possible to get to j from i, that is if

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

A state i is said to communicate with a state j (written i ↔ j) if both i → j and j → i. A set of states C is a communicating class if every pair of states in C communicates with each other, and no state in C communicates with any state not in C. Since the communication is an equivalence relation, the state space S can be partitioned into communicating classes. A CTMC is irreducible if the entire S 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]


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]


P'(t) = P(t) Q


P(t) = e^{tQ}


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


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}


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

is used.

Stationary distribution[edit]


P(t) = \begin{pmatrix}

as t → ∞ the distribution tends to

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


\pi Q = 0.

with the additional constraint that

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




-0.025 & 0.02 & 0.005 \\
0.3 & -0.5 & 0.2 \\
0.02 & 0.4 & -0.42

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

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

Hitting times[edit]


Expected hitting times[edit]


k_i^A = 0 & \text{ for } i \in A\\
-\sum_{j \in S} q_{ij} k_j^A = 1&\text{ for } i \notin A.

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.


Embedded Markov chain[edit]


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

From this, S may be written as

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


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




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]


Queueing theory[edit]

Main article: Queueing theory



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

See also[edit]


  1. ^ Baier, C.; Katoen, J. P.; Hermanns, H. (1999). "Approximative Symbolic Model Checking of Continuous-Time Markov Chains". CONCUR'99 Concurrency Theory (PDF). Lecture Notes in Computer Science 1664. p. 146. doi:10.1007/3-540-48320-9_12. ISBN 978-3-540-66425-3. 
  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. 
  4. ^ Norris, J. R. (1997). "Discrete-time Markov chains". Markov Chains. p. 1. doi:10.1017/CBO9780511810633.003. ISBN 9780511810633. 
  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. 
  • William J. Stewart (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press. pp. 17–23. ISBN 0-691-03699-3. 
  • Kishor Trivedi (2001). Probability and Statistics with Reliability, Queuing and Computer Science Applications. John Wiley.