Continuous-time Markov chain

Let ${\displaystyle P}$ be the (unique) solution of the system (0). (Uniqueness guaranteed by our assumption that ${\displaystyle Q}$ is regular.) We say ${\displaystyle X}$ is Markov with initial distribution ${\displaystyle \lambda }$ and rate matrix ${\displaystyle Q}$ to mean: for any nonnegative integer ${\displaystyle n\geq 0}$, for all ${\displaystyle t_{0},\dots ,t_{n+1}\in T}$ such that ${\displaystyle t_{0}<\dots <t_{n+1},}$ for all ${\displaystyle i_{0},\dots ,i_{n+1}\in I,}$

${\displaystyle \Pr(X_{0}=i_{0},\dots ,X_{t_{n+1}}=i_{n+1})=\lambda _{i_{0}}\prod _{k\in \mathbb {Z} :0\leq k\leq n}P(t_{k+1}-t_{k})_{i_{k},i_{k+1}}}$.[10]

(1)

Using induction and the fact that ${\displaystyle \forall A,B\in {\cal {A}}~~\Pr(B)\neq 0\rightarrow \Pr(A\cap B)=\Pr(A\mid B)\Pr(B),}$ we can show the equivalence of the above statement containing (1) and the following statement: for all ${\displaystyle i\in I,~\Pr(X_{0}=i)=\lambda _{i}}$ and for any nonnegative integer ${\displaystyle n\geq 0}$, for all ${\displaystyle t_{0},\dots ,t_{n+1}\in T}$ such that ${\displaystyle t_{0}<\dots <t_{n+1},}$ for all ${\displaystyle i_{0},\dots ,i_{n+1}\in I}$ such that ${\displaystyle 0<\Pr(X_{0}=i_{0},\dots ,X_{t_{n}}=i_{n})}$ (it follows that ${\displaystyle 0<\Pr(X_{t_{n}}=i_{n})}$),

${\displaystyle \Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{n}}=i_{n},\dots ,X_{t_{0}}=i_{0})=P(t_{n+1}-t_{n})_{i_{n},i_{n+1}}.}$

(2)

It follows from continuity of the functions ${\displaystyle (P(t)_{i,j})_{t\in T}}$ (${\displaystyle i,j\in S}$) that the trajectory ${\displaystyle (X_{t}(\omega ))_{t\in T}}$ is almost surely right continuous (with respect to the discrete metric on ${\displaystyle S}$): there exists a ${\displaystyle \Pr }$-null set ${\displaystyle N}$ such that ${\displaystyle \{\omega \in \Omega$ :(X_{t}(\omega ))_{t\in T}{\text{ is right continuous}}\}\subseteq N} .[13]

Let ${\displaystyle f:T\to S}$ be right continuous (when we equip ${\displaystyle S}$ with the discrete metric). Define

${\displaystyle h=h(f)=(\inf\{u\in (0,+\infty ):f(t+u)\neq f(t)\})_{t\in T})\cup \{+\infty ,0\},}$

let

${\displaystyle H=H(f)=(h^{\circ n}0)_{n\in \mathbb {Z} _{\geq 0}}}$

be the holding-time sequence associated to ${\displaystyle f}$, choose ${\displaystyle s\in S,}$ and let

${\displaystyle y=y(f)=\left({\begin{cases}f(\sum _{k\in n}H_{k})&{\text{ if }}\sum _{k\in n}H_{k}<+\infty ,\\s&{\text{ else}}\end{cases}}\right)_{n\in \omega }}$

be "the state sequence" associated to ${\displaystyle f}$.

The jump matrix ${\displaystyle \Pi }$, alternatively written ${\displaystyle \Pi (Q)}$ if we wish to emphasize the dependence on ${\displaystyle Q}$, is the matrix

$${\displaystyle \Pi =([i=j])_{i\in Z,j\in S}\cup \bigcup _{i\in S\setminus Z}(\{((i,j),(-Q_{i,i})^{-1}Q_{i,j}):j\in S\setminus \{i\}\}\cup \{((i,i),0)\}),}$$

where ${\displaystyle Z=Z(Q)=\{k\in S:q_{k,k}=0\}}$ is the zero set of the function ${\displaystyle (q_{k,k})_{k\in S}.}$[14]

We say ${\displaystyle X}$ is Markov with initial distribution ${\displaystyle \lambda }$ and rate matrix ${\displaystyle Q}$ to mean: the trajectories of ${\displaystyle X}$ are almost surely right continuous, let ${\displaystyle f}$ be a modification of ${\displaystyle X}$ to have (everywhere) right-continuous trajectories, ${\displaystyle \sum _{n\in \mathbb {Z} _{\geq 0}}H(f(\omega ))_{n}=+\infty }$ almost surely (note to experts: this condition says ${\displaystyle X}$ is non-explosive), the state sequence ${\displaystyle y(f(\omega ))}$ is a discrete-time Markov chain with initial distribution ${\displaystyle \lambda }$ (jump-chain property) and transition matrix ${\displaystyle \Pi (Q),}$ and ${\displaystyle \forall n\in \mathbb {Z} _{\geq 0}~\forall B\in {\cal {B}}(\mathbb {R} _{\geq 0})~\Pr(H_{n}(f)\in B)=\operatorname {Exp} (-q_{Y_{n},Y_{n}})(B)}$ (holding-time property).

The continuous time Markov chain is characterized by the transition rates, the derivatives with respect to time of the transition probabilities between states i and j.

We say ${\displaystyle X}$ is Markov with initial distribution ${\displaystyle \lambda }$ and rate matrix ${\displaystyle Q}$ to mean: for all ${\displaystyle i\in S,}$ ${\displaystyle \Pr(X(0)=i)=\lambda _{i}}$ and for all ${\displaystyle i,j}$, for all ${\displaystyle t}$ and for small strictly positive values of ${\displaystyle h}$, the following holds for all ${\displaystyle t\in T}$ such that ${\displaystyle 0<\Pr(X(t)=i)}$:

${\displaystyle \Pr(X(t+h)=j\mid X(t)=i)=[i=j]+q_{i,j}h+o(h)}$,

where the term ${\displaystyle [i=j]}$ is ${\displaystyle 1}$ if ${\displaystyle i=j}$ and otherwise ${\displaystyle 0}$, and the little-o term ${\displaystyle o(h)}$ depends in a certain way on ${\displaystyle i,j,h}$.[15][16]

The above equation shows that ${\displaystyle q_{i,j}}$ can be seen as measuring how quickly the transition from ${\displaystyle i}$ to ${\displaystyle j}$ happens for ${\displaystyle i\neq j}$, and how quickly the transition away from ${\displaystyle i}$ happens for ${\displaystyle i=j}$.

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

Write P(t) for the matrix with entries p_ij = P(X_t = j | X₀ = i). Then the matrix P(t) satisfies the forward equation, a first-order differential equation

${\displaystyle 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

${\displaystyle 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

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

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

${\displaystyle 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

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

is used.

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

${\displaystyle 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

${\displaystyle 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

${\displaystyle \pi Q=0}$

with the constraint

${\displaystyle \sum _{i\in S}\pi _{i}=1}$.

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

${\displaystyle 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 ${\displaystyle \pi Q=0}$, subject to the constraint that elements must sum to 1 to obtain

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

Transition graph with transition probabilities, exemplary for the states 1, 5, 6 and 8. There is a bidirectional secret passage between states 2 and 8.

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 monsters 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:

${\displaystyle Q={\begin{pmatrix}-1&{\frac {1}{2}}&&{\frac {1}{2}}\\{\frac {1}{4}}&-1&{\frac {1}{4}}&&{\frac {1}{4}}&&&{\frac {1}{4}}\\&{\frac {1}{2}}&-1&&&{\frac {1}{2}}\\{\frac {1}{3}}&&&-1&{\frac {1}{3}}&&{\frac {1}{3}}\\&{\frac {1}{4}}&&{\frac {1}{4}}&-1&{\frac {1}{4}}&&{\frac {1}{4}}\\&&{\frac {1}{3}}&&{\frac {1}{3}}&-1&&&{\frac {1}{3}}\\&&&{\frac {1}{2}}&&&-1&{\frac {1}{2}}\\&{\frac {1}{4}}&&&{\frac {1}{4}}&&{\frac {1}{4}}&-1&{\frac {1}{4}}\\&&&&&{\frac {1}{2}}&&{\frac {1}{2}}&-1\end{pmatrix}}}$

This Markov chain is irreducible, because the ghosts can fly from every state to every state in a finite amount of time. Due to the secret passageway, the Markov chain is also aperiodic, because the monsters can move from any state to any state both in an even and in an uneven number of state transitions. Therefore, a unique stationary distribution exists and can be found by solving ${\displaystyle \pi Q=0}$, subject to the constraint that elements must sum to 1. The solution of this linear equation subject to the constraint is ${\displaystyle \pi =(7.7,15.4,7.7,11.5,15.4,11.5,7.7,15.4,7.7)\%.}$ 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.

For a CTMC X_t, the time-reversed process is defined to be ${\displaystyle {\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.

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 s_ij, and represents the conditional probability of transitioning from state i into state j. These conditional probabilities may be found by

${\displaystyle 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

${\displaystyle 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 ${\displaystyle \varphi }$ such that

${\displaystyle \varphi S=\varphi ,}$

with ${\displaystyle \varphi }$ being a row vector, such that all elements in ${\displaystyle \varphi }$ are greater than 0 and ${\displaystyle \|\varphi \|_{1}}$ = 1. From this, π may be found as

${\displaystyle \pi ={-\varphi (\operatorname {diag} (Q))^{-1} \over \left\|\varphi (\operatorname {diag} (Q))^{-1}\right\|_{1}}.}$

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