Page 182 - A First Course In Stochastic Models

TRANSIENT DISTRIBUTION OF CUMULATIVE REWARDS 175

n

= P {Y 1 + · · · + Y k ≤ x} α(n, k)
k=0
n n
x j
n x n−j

= α(n, k) 1 − , 0 ≤ x < t.
j t t
k=0 j=k
This gives the desired expression
∞ n n
x j

−νt (νt) n n x n−j
P {O(t) ≤ x} = e α(n, k) 1 − (4.6.1)
n! j t t
n=0 k=0 j=k
for 0 ≤ x < t. The random variable O(t) assumes the value t if the uniformized
process visits only operational states in (0, t). Thus
∞ n
−νt (νt)
P {O(t) = t} = α(n, n + 1)e .
n!
n=0
The above expression for P {O(t) ≤ x} is well suited for numerical computations,
since the summations involve only positive terms. As before, the infinite sum can
be truncated to M terms, where the error associated with the truncation is bounded
n
by ∞ e −νt (νt) /n! so that M can be determined beforehand for a given error
n=M
tolerance.
Computation of the α(n, k)

The probabilities α(n, k) are determined by the discrete-time Markov chain {X n }
that governs the state transitions in the uniformized process. The one-step transition
probabilities of this discrete-time Markov chain are given by p = (ν i /ν)p ij for
ij
j = i and p = 1−ν i /ν, where p ij = q ij /ν i . To calculate the α(n, k), let α(n, k, j)
ii
be the joint probability that the discrete-time Markov chain {X t } visits k times an
operational state over the first n state transitions and is in state j after the nth
transition. Then

α(n, k) = α(n, k, j), k = 0, 1, . . . , n + 1 and n = 0, 1, . . . .
j∈I
The probabilities α(n, k, j) can be recursively computed. In the recursion we have
to distinguish between states j ∈ I 0 and states j ∈ I f . Obviously,

α(n, k, j) = α(n − 1, k − 1, i)p , j ∈ I 0
ij
i∈I
and

α(n, k, j) = α(n − 1, k, i)p , j ∈ I f .
ij
i∈I