Continuous-time Markov chain

In probability theory, a continuous-time Markov process is a stochastic process { X(t) : t ≥ 0 } that satisfies the Markov property and takes values from a set called the state space. The Markov property states that at any times s > t > 0, the conditional probability distribution of the process at time s given the whole history of the process up to and including time t, depends only on the state of the process at time t. In effect, the state of the process at time s is conditionally independent of the history of the process before time t, given the state of the process at time t.

Mathematical definitions

Intuitively, one can define a time-homogeneous Markov process as follows. Let X(t) be the random variable describing the state of the process at time t. Now prescribe that, given that the process starts in a state i at time t, it has made the transition to some other state j (j ≠ i) at time t + h with probability given by

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

and, for j = i, the probability is given by

$\Pr(X(t+h)=i|X(t)=i)=1-q_{ii}h+o(h),\,$

where o(h) represents a quantity that goes to zero faster than h goes to zero (see the article on order notation). Hence, over a sufficiently small interval of time, the probability of a particular transition (between different states) is roughly proportional to the duration of that interval.

Continuous-time Markov processes are most easily defined by specifying the transition rates q_ij, and these are typically given as the ij-th elements of the transition rate matrix Q. For the probabilities to be conserved, i.e., to add up to one, the off-diagonal elements of Q must be non-negative and the diagonal elements must satisfy

$q_{ii}=-\sum _{j\neq i}q_{ij}.$

With this notation, and letting p_t = $\Pr(X(t)=j)$, the evolution of a continuous-time Markov process is given by the first-order differential equation

${\frac {\partial }{\partial t}}p_{t}=p_{t}Q$

The probability that no transition happens in some time r is

$\Pr(X(s)=i~\forall ~s\in (t,t+r]\,|\,X(t)=i)=e^{-q_{ii}r}.$

That is, the probability distribution of the waiting time until the first transition is an exponential distribution with rate parameter q_ii, and continuous-time Markov processes are thus memoryless processes.

A time dependent (time heterogeneous) Markov process is a Markov process as above, but with the q-rate a function of time, denoted q_ij(t).

Embedded Markov chain

One method of finding the stationary probability distribution, π, of an ergodic Continuous-time Markov process, 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 s_ij, and represents the conditional probability of transitioning from state i into state j. These conditional probabilities may be found by

$s_{ij}=\left\{{\begin{matrix}{q_{ij} \over \sum _{k\neq i}q_{ik}}&\mathrm {if} \quad i\neq j\\0&\mathrm {otherwise} .\end{matrix}}\right.$

From this, S may be written as

$S=I-D_{Q}^{-1}Q,$

where D_Q = diag{Q} is the diagonal matrix of Q.

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

$\phi (I-S)=0,$

with φ being a row vector, such that all elements in φ are greater than 0 and ||φ||₁ = 1, and the 0 on the right side also being a row vector of 0's. From this, π may be found as

$\pi ={-\phi D_{Q}^{-1} \over \left\|\phi D_{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.

See also

• Markov chain
• Master equation (physics)
• Queueing theory
• Phase-type distribution
• Semi-Markov process
• Variable-order Markov model

References

• William J. Stewart (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press. pp. 17–23. ISBN 0691036993.