Page 252 - A First Course In Stochastic Models

THE RELATIVE VALUE FUNCTION 245

(b) Let {g, υ i } be any solution to (6.3.2). We first verify by induction that the
following identity holds for each m = 1, 2, . . . .

m−1
(t) (m)

υ i = p (R)c j (R j ) − mg + p (R)υ j , i ∈ I. (6.3.3)
ij ij
t=0 j∈I j∈I
Clearly, (6.3.3) is true for m = 1. Suppose that (6.3.3) is true for m = n. Substitut-
ing equations (6.3.2) into the right-hand side of (6.3.3) with m = n, it follows that
n−1

(t) (n)
υ i = p (R)c j (R j )−ng + p (R) c j (R j ) − g + p jk (R j )υ k
ij ij
t=0 j∈I j∈I k∈I
 
n

(t) (n)

= p (R)c j (R j ) − (n + 1)g+ p (R)p jk (R j ) υ k , i ∈ I.
ij ij
 
t=0 j∈I k∈I j∈I
where the latter equality involves an interchange of the order of summation. Next,
using (6.2.1), we get (6.3.3) for m = n + 1, which completes the induction step.
Using the relation (6.2.2) for the total expected costs over the first m decision
epochs, we can rewrite (6.3.3) in the more convenient form
(m)
υ i = V m (i, R) − mg + p (R)υ j , i ∈ I. (6.3.4)
ij
j∈I
Since V m (i, R)/m → g(R) as m → ∞ for each i, the result g = g(R) follows
by dividing both sides of (6.3.4) by m and letting m → ∞. To prove the second
part of assertion (b), let {g, υ i } and {g , υ } be any two solutions to (6.3.1). Since
′
′
i
g = g = g(R), it follows from the representation (6.3.4) that
′
(m)
′ ′
υ i − υ = p (R){υ j − υ }, i ∈ I and m ≥ 1.
i ij j
j∈I
By summing both sides of this equation over m = 1, . . . , n and then dividing by
n, it follows after an interchange of the order of summation that

n
1

′ (m) ′
υ i − υ = p ij (R) (υ j − υ ), i ∈ I and n ≥ 1.
j
i
n
j∈I m=1
Next, by letting n → ∞ and using (6.2.5), we obtain

′ ′
υ i − υ = π j (R)(υ j − υ ), i ∈ I.
i j
j∈I
The right-hand side of this equation does not depend on i. This proves part (b).

(c) Since j p ij (R i ) = 1 for each i ∈ I, it follows that for any constant c the
numbers g and υ i = w i (R) + c, i ∈ I, satisfy (6.3.2). Hence the equations (6.3.2)