Page 170 - A First Course In Stochastic Models

TRANSIENT STATE PROBABILITIES 163

variation over time with peaks at certain hours of the day. Equilibrium models
are of no use in this kind of situation. The computation of transient solutions for
Markov systems is a very important issue that arises in numerous problems in
queueing, inventory and reliability. In this section we discuss two basic methods
for the computation of the transient state probabilities of a continuous-time Markov
chain. The next section deals with the computation of the transient distribution of
the cumulative reward in a continuous-time Markov chain with a reward structure.
The transient probabilities of a continuous-time Markov chain {X(t), t ≥ 0} are
defined by
p ij (t) = P {X(t) = j | X(0) = i}, i, j ∈ I and t > 0.

In Section 4.5.1 we discuss the method of linear differential equations. The proba-
bilistic method of uniformization will be discussed in Section 4.5.2. In Section 4.5.3
we show that the computation of first passage time probabilities can be reduced to
the computation of transient state probabilities by introducing an absorbing state.

4.5.1 The Method of Linear Differential Equations
This basic approach has a solid backing by tools from numerical analysis. We first
prove the following theorem.

Theorem 4.5.1 (Kolmogoroff’s forward differential equations) Suppose that
the continuous-time Markov chain {X(t), t ≥ 0} satisfies Assumption 4.1.2. Then
for any i ∈ I,

′
p (t) = q kj p ik (t) − ν j p ij (t), j ∈ I and t > 0. (4.5.1)
ij
k =j
Proof We sketch the proof only for the case of a finite state space I. The proof
of the validity of the forward equations for the case of an infinite state space is
very intricate. Fix i ∈ I and t > 0. Let us consider what may happen in (t, t + t]
with t very small. The number of transitions in any finite time interval is finite
with probability 1, so we can condition on the state that will occur at time t:

p ij (t + t) = P {X(t + t) = j | X(0) = i}

= P {X(t + t) = j | X(0) = i, X(t) = k}
k∈I
× P {X(t) = k | X(0) = i}

= P {X(t + t) = j | X(t) = k}p ik (t)
k∈I

= q kj tp ik (t) + (1 − ν j t)p ij (t) + o( t),
k =j