Page 78 - A First Course In Stochastic Models

AN UP- AND DOWNCROSSING TECHNIQUE 69

2.7 AN UP- AND DOWNCROSSING TECHNIQUE

In this section we discuss a generally applicable up- and downcrossing technique
that, in conjunction with the PASTA property, can be used to establish relations
between customer-average and time-average probabilities in queueing systems. To
illustrate this, we consider the so-called GI/M/1 queue. In this single-server sys-
tem, customers arrive according to a renewal process and the service times of the
customers have a common exponential distribution. The single server can handle
only one customer at a time and there is ample waiting room for customers who
find the server busy upon arrival. The service times of the customers are indepen-
dent of each other and are also independent of the arrival process. Denoting by λ
the average arrival rate (1/λ = the mean interarrival time) and by β the service
rate (1/β = the mean service time), it is assumed that λ < β.
The continuous-time stochastic process {X(t), t ≥ 0} and the discrete-time
stochastic process {X n , n = 1, 2, . . . } are defined by
X(t) = the number of customers present at time t,

and

X n = the number of customers present just prior to the nth arrival epoch.

The stochastic processes {X(t)} and {X n } are both regenerative. The regeneration
epochs are the epochs at which an arriving customer finds the system empty. It
is stated without proof that the assumption of λ/β < 1 implies that the processes
have a finite mean cycle length. Thus we can define the time-average and the
customer-average probabilities p j and π j by
p j = the long-run fraction of time that j customers are present

and
π j = the long-run fraction of customers who find j other customers
present upon arrival

for j = 0, 1, . . . . Time averages are averages over time, and customer averages
t
I
are averages over customers. To be precise, p j = lim t→∞ (1/t) 0 j (u) du and
n
I
π j = lim n→∞ (1/n) k=1 k (j), where I j (t) = 1 if j customers are present at
time t and I j (t) = 0 otherwise, and I n (j) = 1 if j other customers are present just
before the nth arrival epoch and I n (j) = 0 otherwise. The probabilities p j and π j
are related to each other by
λπ j−1 = βp j , j = 1, 2, . . . . (2.7.1)

The proof of this result is instructive and is based on three observations. Before
giving the three steps, let us say that the continuous-time process {X(t)} makes
an upcrossing from state j − 1 to state j if a customer arrives and finds j − 1