Page 352 - A First Course In Stochastic Models

THE M/G/1 QUEUE 347

The following simple idea is crucial for the derivation of a recurrence relation
for the probabilities p j . Divide a cycle into a random number of disjoint intervals
separated by the service completion epochs and calculate E(T j ) as the sum of the
contributions from the disjoint intervals to the expected sojourn time in state j
during one cycle. Thus, for k = 0, 1, . . . , we define the random variable N k by
N k = the number of service completion epochs in one cycle
at which k customers are left behind.
Using the lack of memory of the Poisson arrival process, define

A kj = the expected amount of time that j customers are present
during a given service time that starts with k customers present.

Then, noting that the first service in a cycle starts with one customer present,
j

E(T j ) = A 1j + E(N k )A kj , j = 1, 2, . . . . (9.2.4)
k=1
It should be pointed out that Wald’s equation is used to justify that E(N k )A kj
is the contribution to E(T j ) of those service intervals starting with k customers
present. To find another relation between E(T j ) and E(N k ), observe that for each
k = 0, 1, . . . , the number of downcrossings from state k +1 to state k in one cycle
equals the number of upcrossings from state k to state k + 1 in one cycle. The
expected number of downcrossings of the {L(t)} process from state k + 1 to state
k in one cycle equals E(N k ) by definition. On the other hand, since the arrival
process is a Poisson process, we have by Corollary 2.4.2 that the expected number
of upcrossings from state k to state k + 1 in one cycle equals λE(T k ). Thus
E(N k ) = λE(T k ), k = 0, 1, . . . . (9.2.5)

Together the relations (9.2.2) to (9.2.5) imply that
j

p j = λp 0 A 1j + λp k A kj , j = 1, 2, . . . . (9.2.6)
k=1
To specify the constants A kj , suppose that at epoch 0 a service starts when k
customers are present. Define the random variable I j (t) = 1 if at time t the service
is still in progress and j customers are present and let I j (t) = 0 otherwise. Then,
for j ≥ k,
∞ ∞

A kj = E I j (t) dt = E[I j (t)] dt
0 0
j−k
∞ ∞ (λt)
−λt
= P {I j (t) = 1} dt = {1 − B(t)}e dt. (9.2.7)
0 0 (j − k)!
Together (9.2.6) and (9.2.7) yield the desired result.