Page 216 - A First Course In Stochastic Models

A PHASE METHOD 209

processor-sharing queue corresponds to the case of
1
f (i) = , i = 1, 2, . . . .
i

In this case φ(i) = i! for i = 0, 1, . . . and the above formulas reduce to
s
j
p j = (1 − ρ)ρ , j = 0, 1, . . . and E(W | s) = , s > 0.
1 − ρ
In other words, in the standard M/G/1 processor-sharing queue with general ser-
vice times, the equilibrium distribution of the number of customers present is the
same as in the M/M/1 queue with the first-come first-served discipline. This find-
ing also applies to the M/G/1 queue with the pre-emptive resume, last-in first-out
discipline. Under this service discipline each customer begins service upon arrival,
pre-empting anyone in service, and at each time, the most recently arrived customer
receives service.

5.5 A PHASE METHOD
The phase method makes it possible to use the continuous-time Markov chain
approach for a wide variety of practical probability problems in which the under-
lying probability distributions are not necessarily exponential. The method essen-
tially goes back to A.K. Erlang, who did pioneering work on stochastic pro-
cesses at the beginning of the twentieth century. In his analysis of telephone
problems, Erlang devised the trick of considering the duration of a call as the
sum of a number of sequential phases whose lengths are exponentially distributed.
There are several versions of the phase method (or method of stages). A very
useful version is the one that approximates a positive random variable by a ran-
dom sum of exponentials with the same means. In other words, the probabil-
ity distribution of the positive random variable is approximated by a mixture of
Erlangian distributions with the same scale parameters. The theoretical basis for
the use of such mixtures of Erlangian distributions is provided by the follow-
ing theorem.
Theorem 5.5.1 Let F(t) be the probability distribution function of a positive ran-
dom variable. For fixed > 0 define the probability distribution function F (x) by
 
∞ j−1
 k 
−x/ (x/ )
F (x) = p j ( ) 1 − e , x ≥ 0, (5.5.1)
k!
 
j=1 k=0
where p j ( ) = F(j ) − F((j − 1) ), j = 1, 2, . . . . Then
lim F (x) = F(x)
→0
for each continuity point x of F(t).