Page 177 - A First Course In Stochastic Models

170 CONTINUOUS-TIME MARKOV CHAINS

where E ij (t) is the expected amount of time that the process {X(t)} is in state j up
to time t when the process starts in state i. For any i, j ∈ I,

∞ k k−1
1 −νt (νt) (n)
E ij (t) = e p ij , t > 0. (4.5.8)
ν k!
k=1 n=0
Proof The first term on the right-hand side of the relation for the expected reward
is obvious. To explain the second term, we use the PASTA property. Fix j, k ∈ I
with k = j. Observe that the transitions out of state j occur according to a Poisson
process with rate ν j whenever the process {X(t)} is in state j. Hence, using part (b)
of Theorem 1.1.3, transitions from state j to state k( = j) occur according to a
Poisson process with rate q jk (= p jk ν j ) whenever the process {X(t)} is in state j.
Next, by applying part (a) of Theorem 2.4.1, it is readily seen that the expected
number of transitions from state j to state k up to time t equals q jk times the
expected amount of time the process {X(t)} is in state j up to time t. This proves
(4.5.7). To prove (4.5.8), note that the representation (4.5.5) implies

∞
t t (νu) n (n)
E ij (t) = p ij (u) du = e −νu p ij du
0 0 n!
n=0
∞ t n
(n) −νu
(νu)
= p e du.
ij n!
n=0 0
Except for a factor ν we have an integral over an Erlang (n + 1, ν) density. Thus
∞ ∞ k
1 (n) −νt (νt)
E ij (t) = p ij e .
ν k!
n=0 k=n+1
By interchanging the order of summation, we next get the desired result.

4.5.3 First Passage Time Probabilities
In this section it is assumed that the state space I of the continuous-time Markov
chain {X(t)} is finite. For a given set C of states with C = I, define

τ C = the first epoch at which the continuous-time Markov chain {X(t)}
makes a transition into a state of the set C.
Also, define the first passage time probability Q iC (t) by

Q iC (t) = P {τ C > t | X(0) = i}, i /∈ C and t > 0.

The computation of the first passage time probabilities Q iC (t) can be reduced to
the computation of the transient state probabilities in a modified continuous-time
Markov chain with an absorbing state. The most convenient way to model an