WeiYa's Work Yard

A dog, who fell into the ocean of statistics, tries to write down his ideas and notes to save himself.

Continuous Time Markov Chain

Posted on
Tags: CTMC

This note is based on Karl Sigman’s IEOR 6711: Continuous-Time Markov Chains.

A stochastic process $\{X(t):t\ge 0\}$ with discrete state space $\cS$ is called a continuous-time Markov chain (CIMC) if for all $t\ge 0,s\ge 0,i\in\cS,j\in\cS$, $$ P(X(s+t)=j\mid X(s)=i,\{X(u):0\le u < s\}) = P(X(s+t)=j\mid X(s)=i)=P_{ij}(t)\,. $$

For each $t\ge 0$, there is a transition matrix $P(t)=(P_{ij}(t))$, and $P(0)=I$.

Unlike the discrete-time case, there is no smallest “next time” until the next transition, there is a continuum of such possible times $t$.

Suppose now that whenever a chain enters state $i\in\cS$, independent of the past, the length of time spent in state $i$ is a continuous, strictly positive (and proper) random variable $H_i$ called the holding time in state $i$. The holding times must have the memoryless property and thus are exponentially distributed.

A CTMC can simply be described by a transition matrix $P=(P_{ij})$, describing how the chain changes state step-by-step at transition epochs, together with a set of rates ${a_i:i\in \cS}$, the holding time rates. Each time state $i$ is visited, the chain spends, on average, $\E(H_i)=1/a_i$ units of time there before moving on.

Transition rate matrix

The matrix $Q=P'(0)$ is called the transition rate matrix, or infinitesimal generator, of the Markov chain.

Chapman-Kolmogorov equations

For all $t,s\ge 0$, $$ P(t+s) = P(s)P(t)\,, $$ that is, for all $t,s\ge 0, i,j\in\cS$, $$ P_{ij}(t+s) = \sum_{k\in\cS} P_{ik}(s)P_{kj}(t)\,. $$

Kolmogorov backward equations

For a (non-explosive) CTMC with transition rate matrix $Q=P'(0)$, the following set of linear differential equations is satisfied by $\{P(t)\}$: $$ P'(t)= QP(t),\;t\ge 0,\; P(0)=I\,, $$ that is, $$ P_{ij}'(t) = -a_iP_{ij}(t) + \sum_{k\neq i}a_iP_{ik}P_{kj}(t),\quad i,j\in\cS, t\ge 0\,. $$ The unique solution is thus of the exponential form: $$ P(t) = e^{Qt},\;t\ge 0\,. $$

Published in categories Note