Page 172 - A First Course In Stochastic Models

TRANSIENT STATE PROBABILITIES 165

Example 4.5.2 Transient analysis for the M/M/1 queue
In the M/M/1 queue customers arrive according to a Poisson process with rate
λ and the service times of the customers have an exponential distribution with
mean 1/µ. Letting X(t) denote the number of customers present at time t, the pro-
cess {X(t)} is a continuous-time Markov chain. Kolmogoroff’s forward differential
equations are as follows for the M/M/1 queue:

p (t) = µp i,j+1 (t) + λp i,j−1 (t) − (λ + µ)p ij (t), i, j = 0, 1, . . . and t > 0
′
ij
with p i,−1 (t) = 0. An explicit solution of these equations is given by
2 (j−i)/2 π e −µtγ (y) (1 − ρ)ρ , ρ < 1,
j
p ij (t) = ρ a i (y)a j (y) dy +
π 0 γ (y) 0, ρ ≥ 1,
for i, j = 0, 1, . . . , where ρ = λ/µ and the functions γ (y) and a k (y) are
defined by
√ √
γ (y) = 1 + ρ − 2 ρ cos(y) and a k (y) = sin(ky) − ρ sin[(k + 1)y].
A proof of this explicit solution is not given here; see Morse (1955) and Tak´ acs
(1962). The trigonometric integral representation for p ij (t) is very convenient for
numerical computations. A recommended numerical integration method is Gauss–
Legendre integration. Integral representations can also be given for the first two
moments of the number of customers in the system. The formulas will only be
given for the case of ρ < 1. Denoting by L(i, t) the number of customers in the
system at time t when initially there are i customers present, we have

2 (1−i)/2 π e −µtγ (y) ρ
E[L(i, t)] = ρ a i (y) sin(y) dy +
2
π 0 γ (y) 1 − ρ
and
4(1 − ρ) π e −µtγ (y)
2 (1−i)/2
E[L (i, t)] = ρ a i (y) sin(y) dy
3
π 0 γ (y)
−2
+ 2ρ(1 − ρ) − E[L(i, t)],
assuming that ρ < 1. If ρ < 1, the transient probabilities p ij (t) converge to the
j
equilibrium probabilities p j = (1 − ρ)ρ as t → ∞ and, similarly, E[L(i, t)]
converges to ρ/(1 − ρ) as t → ∞. A natural question is how fast the convergence
occurs. A heuristic answer to this question has been given by Odoni and Roth (1983)
2
in the context of the M/G/1 queue. Letting c denote the squared coefficient of
S
variation of the service time, the M/G/1 queue will ‘forget’ its initial state after a
time comparable to
2
(1 + c )E(S)
S
t relax = √ 2
2.8(1 − ρ)
provided that the system is empty at epoch 0.