Probability and Stochastic Processes

86 A. K. MAJEE

9. Continuous-time Markov chain (CTMC)
We now discuss an important class of stochastic process, called continuous-time Markov
chain (CTMC).
Definition 9.1. Let X = {Xt : t ≥ 0} be a stochastic process with countable state space S.
i) We say that the process is a continuous-time Markov chain (CTMC) if
   
P Xtn = j Xt1 = i1 , . . . , Xtn−1 = in−1 = P Xtn = j Xtn−1 = in−1 (9.1)
for all j, i1 , i2 , . . . , in−1 ∈ S and for all 0 ≤ t1 < t2 < . . . < tn .
ii) We say that the CTMC is homogeneous if and only if the probabilities


P Xt+s = j Xs = i
is independent of s for all t.
iii) The probability

pij (t) = P Xt+s = j Xs = i s, t ≥ 0
is called transition probability for the CTMC. Denote P (t) = (pij (t)) for all i, j ∈ S. We
say that P (t) is a transition probability matrix.
Let {Xt : t ≥ 0} be a homogeneous CTMC. Then the following properties hold:


a) pij (t) = P Xt = j X0 = i
and hence 0 ≤ pij (t) ≤ 1 for any t ≥ 0 and i, j ∈ S.
b) pij (0) = P X0 = j X0 = i = δij .
X X

c) pij (t) = P Xt = j X0 = i = 1.
j∈S j∈S

Example 9.1. At time t = 0, exactly N systems start operating. Their lifetimes are indepen-
dent, identically distributed exponential random variables with parameter λ . If X(t) denotes
the number of systems still operating at time t, then {X(t) : t ≥ 0} is a CTMC with state space
S = {0, 1, 2, . . . , N }.
9.1. Kolmogorov forward and backward equations: Observe that
X  
pij (t + T ) = P Xt+T = j, Xt = k X0 = i
k
 
X P Xt+T = j, X0 = i, Xt = k
=
P(X0 = i)
k
 
X P Xt = k, X0 = i P Xt+T = j, X0 = i, Xt = k


= ·

P(X0 = i) P Xt = k, X 0 = i
k
X    
= P Xt = k X0 = i · P Xt+T = j X0 = i, Xt = k
k
X  
= pik (t)P Xt+T = j X0 = i, Xt = k .
k
Since the process {Xt : t ≥ 0} is time homogeneous Markov, we have
   
P Xt+T = j X0 = i, Xt = k = P Xt+T = j Xt = k = pkj (T ).
Thus, we get
X
pij (t + T ) = pik (t)pkj (T )
k

, PROBABILITY AND STOCHASTIC PROCESS 87

which holds for all states i, j and t, T ≥ 0. It is called Chapman-Kolmogorov equation. In
matrix notation, it can be written as
P (t + T ) = P (t)P (T ).
P
Remark 9.1. Let pj (t) = P(Xt = j). Then j∈S pj (t) = 1 for each t ≥ 0. Indeed,
X
X
X
pj (t) = P Xt = j, X0 = i = P(X0 = i)P Xt = j X0 = i = pij (t)P(X0 = i).
i i∈S i
P P
Since j pij (t) = 1, we get that j pj (t) = 1.
d
Transition density matrix. Assume that qij = dt pij (t) t=0 exists, i.e.,

pij (h) − pij (0)
qij = lim .
h→0 h
Then, it is easily seen that
(
1 + hqii + o(h) i = j
pij (h) =
hqij + o(h) i 6= j

where f (h) = o(h) as h → 0 if f (h)
h → 0 as h → 0. Let Q = (qij ). Then one can easily check
that X
qii ≤ 0, qij ≥ 0 for i 6= j, qij = 0.
j
The matrix Q is known as transition density matrix or rate matrix of the process.
Example 9.2. Let N (t) be a Poisson process with intensity λ. Then it is a time-continuous
Markov chain. Observe that, for small ∆t,
pi,i+1 (∆t) = P(N (∆t) = 1) = λ∆t + o(∆t),
pi,j (∆t) = o(∆t) for j 6= i, i + 1 ,


pii (∆t) = P N (t + ∆t) = i N (t) = i = P(N (∆t) = 0) = 1 − λ∆t + o(∆t).
 
−λ λ 0 0 0 ...
 0 −λ λ 0 0 . . .
So, Q, the transition density matrix, is given by Q =  0 .
 
0 −λ λ 0 . . .
.. .. .. .. ..
 
. . . . .
Kolmogorov forward and backward equations. For h > 0 and t ≥ 0, we have from
Chapman-Kolmogorov equation
pij (t + h) − pij (h) 1X  1
1X
= pik (h)pkj (t) − pij (t) = pii (h) − 1 pij (t) + pik (h)pkj (t)
h h h h
k∈S k6=i
pij (t + h) − pij (h) X
=⇒ p0ij (t) = lim = qii pij (t) + qik pkj (t).
h→0 h
k6=i

Hence, in matrix notation
P 0 (t) = QP (t).
This is known as Kolmogorov backward equation. Similarly, by using the fact that
X
pij (t + h) = pik (t)pkj (h),
k∈S