A continuous-time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of a stochastic matrix. An equivalent formulation describes the process as changing state according to the least value of a set of exponential random variables, one for each possible state it can move to, with the parameters determined by the current state.

is as follows: the process makes a transition after the amount of time specified by the holding time, where i. When a transition is to be made, the process moves according to the jump chain, a discrete-time Markov chain with stochastic matrix:

Equivalently, by the property of competing exponentials, this CTMC changes state from state i where the parameters are given by the Q-matrix

can be computed as the probability that the jump chain moves from state i to state j, divided by the expected holding time of state i. The diagonal entries are chosen so that each row sums to 0.

A CTMC satisfies the Markov property, that its behavior depends only on its current state and not on its past behavior, due to the memorylessness of the exponential distribution and of discrete-time Markov chains.

Definition

be a probability space with the discrete metric, so that we can make sense of right continuity. A continuous-time Markov chain is defined by:

• A probability vector (which below we will interpret as the initial distribution of the Markov chain), and

• A rate matrix such that

• ,

• is infinite, this sum is a priori) because each term appearing in the sum is nonnegative. A posteriori is stable or totally stable, i.e., every entry is real valued.)

. This situation contrasts with the situation for discrete-time Markov chains, where all row sums of the transition matrix equal unity.

being : via transition probabilities or via the jump chain and holding times.

As a prelude to a transition-probability definition, we first motivate the definition of a regular rate matrix to specify the dynamics of the Markov chain by means of generating a collection of transition matrices), via the following theorem. is regular to mean that we do have uniqueness for the above system, i.e., that there exists exactly one solution. is irregular. will be a stochastic matrix. is regular from the beginning of the following subsection up through the end of this section, even though it is conventional to not include this assumption. (Note for the expert: thus we are not defining continuous-time Markov chains in general but only non-explosive continuous-time Markov chains.)

Transition-probability definition

be the (unique) solution of the system ( is we can show the equivalence of the above statement containing (),

is almost surely right continuous (with respect to the discrete metric-null set.

Jump-chain/holding-time definition

Sequences associated to a right-continuous function

with the discrete metric). Define

let

be the holding-time sequence and let

be "the state sequence.

Definition of the jump matrix Π

The jump matrix is the zero set

Jump-chain/holding-time property

is (holding-time property).

Infinitesimal definition

is :

1. ,

, and the little-o term.

.

Properties

Communicating classes

Communicating classes, transience, recurrence and positive and null recurrence are defined identically as for discrete-time Markov chains.

Transient behaviour

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

1. ,

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

1. .

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

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

1. .

Computing direct solutions is complicated in larger matrices. The fact that Q is the generator for a semigroup of matrices

is used.

Stationary distribution

. Observe that for the two-state process considered earlier with P(t) given by

1. ,

as t→∞ the distribution tends to

1. .

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

with the constraint

1. .

Example 1

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

, subject to the constraint that elements must sum to 1 to obtain

Example 2

The image to the right describes a discrete-time Markov chain modeling Pac-Man with state-space {1,2,3,4,5,6,7,8,9}. The player controls Pac-Man through a maze, eating pac-dots. Meanwhile, he is being hunted by ghosts. For convenience, the maze shall be a small 3x3-grid and the ghosts move randomly in horizontal and vertical directions. A secret passageway between states 2 and 8 can be used in both directions. Entries with probability zero are removed in the following transition-rate matrix:

The central state and the border states 2 and 8 of the adjacent secret passageway are visited most and the corner states are visited least.

Time reversal

For a CTMC Xt. 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

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

From this, S may be written as

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.

such that

are greater than 0 and \|\varphi\|_1 = 1. From this, may be found as

(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 δ-skeletonthe (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

• Kolmogorov equations (Markov jump process)

Notes

References

• Leo Breiman (1992) [1968] Probability. Original edition published by Addison-Wesley; reprinted by Society for Industrial and Applied Mathematics . (See Chapter 7)

• J. L. Doob (1953) Stochastic Processes. New York: John Wiley and Sons .

• A. A. Markov (1971). "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons.

• S. P. Meyn and R. L. Tweedie (1993) Markov Chains and Stochastic Stability. London: Springer-Verlag . online: MCSS . Second edition to appear, Cambridge University Press, 2009.

• Classical text. cf Chapter 6 Finite Markov Chains pp.384ff.

• John G. Kemeny & J. Laurie Snell (1960) Finite Markov Chains, D. van Nostrand Company

• E. Nummelin. General irreducible Markov chains and non-negative operators. Cambridge University Press, 1984, 2004.

• Seneta, E. Non-negative matrices and Markov chains. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973)