Page 79 - A First Course In Stochastic Models

70 RENEWAL-REWARD PROCESSES

other customers present. The process {X(t)} makes a downcrossing from state j
to state j − 1 if the service of a customer is completed and j − 1 other customers
are left behind.
Observation 1 Since customers arrive singly and are served singly, the long-run
average number of upcrossings from j − 1 to j per time unit equals the long-run
average number of downcrossings from j to j − 1 per time unit. This follows by
noting that in any finite time interval the number of upcrossings from j − 1 to j
and the number of downcrossings from j to j − 1 can differ at most by 1.
Observation 2 The long-run fraction of customers seeing j − 1 other customers
upon arrival is equal to
the long-run average number of upcrossings from j − 1 to j per time unit
the long-run average number of arrivals per time unit
for j = 1, 2, . . . . In other words, the long-run average number of upcrossings
from j − 1 to j per time unit equals λπ j−1 .
The latter relation for fixed j is in fact a special case of the Little relation (2.4.1)
by assuming that each customer finding j − 1 other customers present upon arrival
pays $1 (using this reward structure observation 2 can also be obtained directly
from the renewal-reward theorem). Observations 1 and 2 do not use the assumption
of exponential services and apply in fact to any regenerative queueing process in
which customers arrive singly and are served singly.
Observation 3 For exponential services, the long-run average number of down-
crossings from j to j−1 per time unit equals βp j with probability 1 for each j ≥ 1.
The proof of this result relies heavily on the PASTA property. To make this
clear, fix j and note that service completions occur according to a Poisson process
with rate β as long as the server is busy. Equivalently, we can assume that an
exogenous Poisson process generates events at a rate of β, where a Poisson event
results in a service completion only when there are j customers present. Thus, by
part (a) of Theorem 2.4.1,

βE[I j (t)] = E[D j (t)] for t > 0 (2.7.2)
for any j ≥ 1, where I j (t) is defined as the amount of time that j customers are
present during (0, t] and D j (t) is defined as the number of downcrossings from
j to j − 1 in (0, t]. Letting the constant d j denote the long-run average number
of downcrossings from j to j − 1 per time unit, we have by the renewal-reward
theorem that lim t→∞ D j (t)/t = d j with probability 1. Similarly, lim t→∞ I j (t)/t =
p j with probability 1. The renewal-reward theorem also holds in the expected-value
version. Thus, for any j ≥ 1,
E[D j (t)] E[I j (t)]
lim = d j and lim = p j .
t→∞ t t→∞ t
Hence relation (2.7.2) gives that d j = βp j for all j ≥ 1. By observations 1 and 2
we have d j = λπ j−1 . This gives λπ j−1 = βp j for all j ≥ 1, as was to be proved.