1. INTRODUCTION
Consider a GI/GI/1 queue where the mean service time is equal or nearly equal to the mean interarrival time and at least one is nondeterministic. The asymptotic behavior of the queue length Qn just prior to the nth arrival is usually studied by the “continuous mapping approach” (see, e.g., Whitt [9] and Robert [6]). This approach starts with the observation that
where Xi is the difference between the ith service time and the (i + 1)st interarrival time. As this is a continuous mapping of a random walk process, which, suitably scaled, converges to Brownian motion, the continuous-mapping theorem of weak convergence theory (see Billingsley [1]) states that a suitably scaled Qn converges to the same mapping of a Brownian motion. This argument involves invoking the topology of uniform convergence on the space of continuous functions.
In this article we give a somewhat more direct argument for convergence to reflected Brownian motion using Skorokhod embeddings. This type of argument is one of the ingredients in functional central limit theorems (see Durrett [3]) and has been applied to the GI/GI/1 queue in Rosenkrantz [7] to assess the accuracy of Brownian approximations. It is also a key ingredient in what are called “strong approximation” theorems of queuing theory; see Chen and Yao [2]. Although the argument we give here is therefore not new and is straightforward to put together, it seems to have previously appeared in the literature only as an ingredient in other somewhat more complex results. Our contribution is to record and publicize this direct and simple argument as a method to prove convergence to reflected Brownian motion for a GI/GI/1 queue. In Section 2 we present the main result and give its proof.
2. MAIN RESULTS
Here we show how a suitably scaled queue length converges to reflected Brownian motion. This type of limit theorem goes back to Kingman [4] and there has been a very large literature developed from this (see, e.g., Whitt [9]). Below we use the notation Ra(t) to denote reflected Brownian motion with downward drift a, defined as
for standard Brownian motion B(t). We also use →d to denote convergence in distribution.
Theorem 1: Suppose X1,X2,… are independent and identically distributed (i.i.d.) random variables with mean zero and variance σ2 > 0, and
for a given c. Then for any t ≥ 0, we have
.
This theorem applied with c = 0 corresponds to the setting of a critical GI/GI/1 queue where Un is the service time of the nth customer, Vn is the interarrival time between the nth and (n + 1)st customer, and Xn = Un − Vn. In this setting, the variable Qn is the amount of work in the queue just prior to the arrival of the nth customer.
The theorem applied with c = 1 corresponds to a setting where we are looking at a sequence of increasingly congested GI/GI/1 queuing models with
representing the difference between the (i + 1)st interarrival time and the ith service time in the nth model. In this case each model will have a stable queue, but as n → ∞, these models approach a critical queuing model. The variable Qn in this case will represent the amount of work in the nth queuing model immediately before the arrival there of the nth customer.
The next result gives convergence in the space of continuous sample paths.
Theorem 2: With the above definitions and Qnt* = (nt − [nt])Qnt+1 + (1 − nt + [nt])Qnt, we have
, where →d denotes weak convergence of the sample paths in the space of continuous sample paths C[0,∞).
To prove these results we will make use of the following representation result, due to Skorokhod [8] (see also Obłój [5] or Durrett [3]).
Proposition 3: If E [X] = 0 and E [X2] < ∞, then there is a stopping time T for Brownian motion so that B(T) =d X and E [T] = E [X2].
We also make use of the following well-known scaling lemma (see, e.g., Durrett [3]).
Lemma 4: If B(0) = 0, then for any n > 0,
Proof (of Theorem 1): Proposition 3 states we can create an i.i.d. sequence of stopping times ti with
so we have
. If we let
by the scaling lemma (Lemma 4), we have
For a given t,ε > 0, since B(t) is uniformly continuous on [0,t], we can pick δ small enough so that
and then we can pick n large enough so that
and, because Tk /(kσ2) →a.s. 1, also
and thus
Together these give
and so
Proof (of Theorem 2): It suffices (see Durrett [3, lemmas (6.8) and (6.9)] and the discussion following them) to show
Since for 0 ≤ t ≤ 1 the function
is uniformly continuous, we can pick δ small enough and n large enough so that
holds in addition to conditions (1)–(3) for all 0 < t < 1. Together these give
and so the theorem is proved. █
