Page 223 - Applied Probability

10. Molecular Phylogeny
209
10.4 Review of Continuous-Time Markov Chains
As a prelude to the model-based approach, let us pause to review the theory
of finite-state, continuous-time Markov chains. Just as in the discrete-time
theory summarized in Chapter 9, the behavior of a Markov chain can be
described by an indexed family Z t of random variables giving the state oc-
cupied by the chain at each time t. Of fundamental theoretical importance
are the probabilities p ij (t)=Pr(Z t = j | Z 0 = i). For a chain having a
finite number of states, these probabilities can be found by solving a ma-
trix differential equation. To derive this equation, we use the short-time
approximation
p ij (t)= λ ij t + o(t) (10.2)
for i = j, where λ ij is the transition rate (or infinitesimal transition
probability) from state i to state j. Equation (10.2) implies the further
short-time approximation
p ii (t) = 1 − λ i t + o(t), (10.3)

where λ i = λ ij .
j =i
Now consider the Chapman-Kolmogorov relation

p ij (t + h)= p ij (t)p jj (h)+ p ik (t)p kj (h), (10.4)
k =j
which simply says the process must pass through some intermediate state k
at time t en route to state j at time t+h. Substituting the approximations
(10.2) and (10.3) in (10.4) yields

p ij (t + h)= p ij (t)(1 − λ j h)+ p ik (t)λ kj h + o(h).
k =j
Sending h to 0 in the difference quotient
p ij (t + h) − p ij (t) o(h)
= −p ij (t)λ j + p ik (t)λ kj +
h h
k =j
produces the forward differential equation

p (t) = −p ij (t)λ j + p ik (t)λ kj . (10.5)
ij
k =j
The system of differential equations (10.5) can be summarized in matrix
notation by introducing the matrices P(t)= [p ij (t)] and Λ = (Λ ij ), where
Λ ij = λ ij for i = j and Λ ii = −λ i . The forward equations in this notation
become
P (t)= P(t)Λ (10.6)

P(0) = I,