Continuous-time Markov chain

An example of a CTMC with three states ${\displaystyle \{0,1,2\}}$ is as follows: the process makes a transition after the amount of time specified by the holding time—an exponential random variable ${\displaystyle E_i}$, where i is its current state. Each random variable is independent and such that ${\displaystyle E_0\sim \text{Exp}(6)}$, ${\displaystyle E_1\sim \text{Exp}(12)}$ and ${\displaystyle E_2\sim \text{Exp}(18)}$. When a transition is to be made, the process moves according to the jump chain, a discrete-time Markov chain with stochastic matrix:

${\displaystyle \left[\begin{array}{ccc}0& \frac{1}{2}& \frac{1}{2}\\ \frac{1}{3}& 0& \frac{2}{3}\\ \frac{5}{6}& \frac{1}{6}& 0\end{array}\right].}$

Equivalently, by the property of competing exponentials, this CTMC changes state from state i according to the minimum of two random variables, which are independent and such that ${\displaystyle E_{i,j}\sim \text{Exp}(q_{i,j})}$ for ${\displaystyle i\ne j}$ where the parameters are given by the Q-matrix ${\displaystyle Q=(q_{i,j})}$

${\displaystyle \left[\begin{array}{ccc}-6& 3& 3\\ 4& -12& 8\\ 15& 3& -18\end{array}\right].}$

Each non-diagonal entry ${\displaystyle q_{i,j}}$ 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

Let ${\displaystyle (\mathrm{\Omega },\mathcal{A},Pr)}$ be a probability space, let ${\displaystyle S}$ be a countable nonempty set, and let ${\displaystyle T={\mathbb{R}}_{\ge 0}}$ (${\displaystyle T}$ for "time"). Equip ${\displaystyle S}$ with the discrete metric, so that we can make sense of right continuity of functions ${\displaystyle {\mathbb{R}}_{\ge 0}\to S}$. A continuous-time Markov chain is defined by:

• A probability vector ${\displaystyle \lambda }$ on ${\displaystyle S}$ (which below we will interpret as the initial distribution of the Markov chain), and
• A rate matrix ${\displaystyle Q}$ on ${\displaystyle S}$, that is, a function ${\displaystyle Q:S^2\to \mathbb{R}}$ such that

1. for all distinct ${\displaystyle i,j\in S,0\le q_{i,j}}$,
2. for all ${\displaystyle i\in S,}$ ${\displaystyle \sum _{j\in S:j\ne i}{q}_{i,j}=-q_{i,i}.}$ (Even if ${\displaystyle S}$ is infinite, this sum is a priori well defined (possibly equalling ${\displaystyle +\mathrm{\infty }}$) because each term appearing in the sum is nonnegative. A posteriori, we know the sum must also be finite (not equal to ${\displaystyle +\mathrm{\infty }}$), since we're assuming it's equal to ${\displaystyle -q_{i,i}}$ and we've assumed ${\displaystyle Q}$ is real valued. Some authors instead use a definition that's word-for-word the same except for a modified stipulation ${\displaystyle Q:S^2\to \mathbb{R}\cup \{-\mathrm{\infty }\}}$, and say ${\displaystyle Q}$ is stable or totally stable to mean ${\displaystyle \mathrm{range}Q\subseteq \mathbb{R}}$, i.e., every entry is real valued.)

Note that the row sums of ${\displaystyle Q}$ are 0: ${\displaystyle \mathrm{\forall }i\in S,\sum _{j\in S}{q}_{i,j}=0,}$ or more succinctly, ${\displaystyle Q\cdot 1=0}$. This situation contrasts with the situation for discrete-time Markov chains, where all row sums of the transition matrix equal unity.

Now, let ${\displaystyle X:T\to S^{\mathrm{\Omega }}}$ such that ${\displaystyle \mathrm{\forall }t\in TX(t)}$ is ${\displaystyle (\mathcal{A},\mathcal{P}(S))}$-measurable. There are three equivalent ways to define ${\displaystyle X}$ being Markov with initial distribution ${\displaystyle \lambda }$ and rate matrix ${\displaystyle Q}$: 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. We will use the transition-rate matrix ${\displaystyle Q}$ to specify the dynamics of the Markov chain by means of generating a collection of transition matrices ${\displaystyle P(t)}$ on ${\displaystyle S}$ (${\displaystyle t\in {\mathbb{R}}_{\ge 0}}$), via the following theorem.

Existence of solution to Kolmogorov backward equations ()—There exists ${\displaystyle P\in ([0,1{]}^{S\times S}{)}^T}$ such that for all ${\displaystyle i,j\in S}$ the entry ${\displaystyle (P(t{)}_{i,j}{)}_{t\in T}}$ is differentiable and ${\displaystyle P}$ satisfies the Kolmogorov backward equations:

We say ${\displaystyle Q}$ is regular to mean that we do have uniqueness for the above system, i.e., that there exists exactly one solution. We say ${\displaystyle Q}$ is irregular to mean ${\displaystyle Q}$ is not regular. If ${\displaystyle S}$ is finite, then there is exactly one solution, namely ${\displaystyle P=(e^{tQ}{)}_{t\in T},}$ and hence ${\displaystyle Q}$ is regular. Otherwise, ${\displaystyle S}$ is infinite, and there exist irregular transition-rate matrices on ${\displaystyle S}$. If ${\displaystyle Q}$ is regular, then for the unique solution ${\displaystyle P}$, for each ${\displaystyle t\in T}$, ${\displaystyle P(t)}$ will be a stochastic matrix. We will assume ${\displaystyle Q}$ 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

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\ge 0}$, for all ${\displaystyle t_0,\dots ,t_{n+1}\in T}$ such that ${\displaystyle t_0<\cdots <t_{n+1},}$ for all ${\displaystyle i_0,\dots ,i_{n+1}\in I,}$

Using induction and the fact that ${\displaystyle \mathrm{\forall }A,B\in \mathcal{A}Pr(B)\ne 0\to 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\ge 0}$, for all ${\displaystyle t_0,\dots ,t_{n+1}\in T}$ such that ${\displaystyle t_0<\cdots <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)}$),

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 \mathrm{\Omega }:(X_t(\omega ){)}_{t\in T}\text{ is right continuous}\}\subseteq N}$.

Jump-chain/holding-time definition

Sequences associated to a right-continuous function

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,+\mathrm{\infty }):f(t+u)\ne f(t)\}{)}_{t\in T})\cup \{+\mathrm{\infty },0\},}$

let

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

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

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

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

Definition of the jump matrix Π

The jump matrix ${\displaystyle \mathrm{\Pi }}$, alternatively written ${\displaystyle \mathrm{\Pi }(Q)}$ if we wish to emphasize the dependence on ${\displaystyle Q}$, is the matrix $${\displaystyle \mathrm{\Pi }=([i=j]{)}_{i\in Z,j\in S}\cup \bigcup _{i\in S\setminus Z}(\{((i,j),-q_{i,j}/q_{i,i}):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}.}$

Jump-chain/holding-time property

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}}_{\ge 0}}H(f(\omega ){)}_n=+\mathrm{\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 \mathrm{\Pi }(Q),}$ and ${\displaystyle \mathrm{\forall }n\in {\mathbb{Z}}_{\ge 0}\mathrm{\forall }B\in \mathcal{B}({\mathbb{R}}_{\ge 0})Pr(H_n(f)\in B)=\mathrm{Exp}(-q_{Y_n,Y_n})(B)}$ (holding-time property).

Infinitesimal definition

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

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\ne j}$, and how quickly the transition away from ${\displaystyle i}$ happens for ${\displaystyle i=j}$.