Page 176 - A First Course In Stochastic Models

TRANSIENT STATE PROBABILITIES 169

distribution, the truncation integer M can be chosen as
√
M = νt + c νt
for some constant c with 0 < c ≤ c 0 (ε), where c 0 (ε) depends only on the tolerance
number ε. As a consequence the computational complexity of the uniformization
2
method is O(νtN ) where N is the number of states of the Markov chain. Hence
the uniformization method should be applied with the choice
ν = max ν i .
i∈I
The number νt is a crucial factor for the computational complexity of the uni-
formization method, as it is for the Runge–Kutta method, and is called the index
of stiffness. Also, the following remark may be helpful. For fixed initial state i,
the recursion scheme (4.5.6) boils down to the multiplication of a vector with the
matrix P. In many applications the matrix P is sparse. Then the computational effort
can be considerably reduced by using a data structure for sparse matrix multiplica-
tions. The uniformization results (4.5.5) and (4.5.6) need only a minor modification
when the initial state X(0) has a given probability distribution {π 0 (i), i ∈ I}. The
(n) (n) (n)
probability p should then be replaced by p = π 0 (i)p and this prob-
ij j i∈I ij
(n) (n−1)
ability can recursively be computed from p = p p kj starting with
j k∈I k
(0)
p = π 0 (j) for j ∈ I. For example, this modification may be used to compute
j
the transient state probabilities in finite-capacity queueing systems with a non-
stationary Poisson arrival process and exponential services, where the arrival rate
function λ(t) is (approximately) a piecewise-constant function. One then computes
the transient state probabilities for each interval separately on which λ(t) is constant
and uses the probability distribution of the state at the beginning of the interval as
the distribution of the initial state.

Expected transient rewards
Assume that a reward at rate r(j) is earned whenever the continuous-time Markov
chain {X(t)} is in state j, while a lump reward of F jk is earned each time the
process makes a transition from state j to state k ( = j). Let

R(t) = the total reward earned up to time t, t ≥ 0.
The following lemma shows that it is a simple matter to compute the expected
value of the reward variable R(t). The computation of the probability distribution
of R(t) is much more complex and will be addressed in Section 4.6.

Lemma 4.5.4 Suppose that the continuous-time Markov chain {X(t)} satisfies
Assumption 4.1.2. Then

E[R(t) | X(0) = i] = r(j)E ij (t) + E ij (t) q jk F jk , t > 0, (4.5.7)
j∈I j∈I k =j