Moderate deviations for queues in critical loading.
We establish logarithmic asymptotics of moderate deviations for  queue-length and waiting-time processes in single server queues and  open queueing networks in critical loading. Our results complement earlier  diffusion approximation results.
Introduction
This paper complements the classical results on heavy-traffic approximation for queues in Kingman
[7], Prohorov [12], Iglehart and Whitt [5], Borovkov [1], and Reiman [19] by studying some
related large-deviation asymptotics. In a standard set-up, one considers a sequence of GI=GI=1
queues indexed by n with associated loads ae n ! 1 as n !1 so that
and establishes convergence in distribution of suitably time-scaled and normalized queue-related
processes to processes of diffusion type; say, the processes (n \Gamma1=2 W n (nt); t -
denotes the unfinished work (or virtual waiting time) in the n th system at time t , converge in
distribution in the Skorohod J 1 topology to a reflected Brownian motion with drift [5]. The
limits when j are different: in the context of the unfinished work again, if
then the n \Gamma1=2 W n (nt) converge to 0 in probability, and if p
a proper limit have the processes
. Our focus here is on large
deviation asymptotics for the latter case: j specifically, we assume that,
for some b n !1 with b
n) , we have thatb n
and study the logarithmic asymptotics of the large deviations of processes like (b \Gamma1
In Wentzell's classification of large deviations, Wentzell [23], this is the case of
"moderate deviations" since the choice b specifies "normal deviations", and b
large deviations". From an application viewpoint, we are concerned with the queue behaviour at
times much greater than (1 \Gamma ae) \Gamma2 for ae close to 1 while the standard heavy-traffic results refer
to time intervals of order (1 \Gamma ae) \Gamma2 . Accordingly, to distinguish from standard heavy traffic, we
refer to the regime specified by condition (1.2) as near-heavy traffic.
We now give an outline of the paper and a summary of the results. Section 2 contains technical
preliminaries. In Section 3 we consider FIFO single server queues in near-heavy traffic. Section
4 extends the results to the case of FIFO open queueing networks with homogeneous customer
population. The results mostly have the form of large deviation principles (LDPs) in the spaces
of right-continuous functions with left limits equipped with one of Skorohod's topologies, Skorohod
[21], for such processes as the processes of queue length, unfinished work, completed work,
waiting times, the number of departures, and departure times. Occasionally, we give LDPs for one-dimensional
projections. The rate functions that we obtain are quadratic in form and reminiscent
of the distributions of the diffusion processes arising in the corresponding heavy-traffic limit theo-
rems. Moreover, the ideas of the proofs are either borrowed from the proofs of the corresponding
convergence results or could be used to give them alternative proofs. So, in a sense, the paper
is another evidence of the analogy between large deviation theory and weak convergence theory,
Puhalskii [13]-[16].
2. Technical Preliminaries
We shall work in the function space D(R d of right-continuous R d -valued
functions on [0; 1) with left limits, endowed with the Skorohod [21] J 1 or M 1 topologies, or a
modification of the M 1 topology denoted by M 0
1 , we refer to [8], [11], [24], [9], [17] for details.
These spaces are metrizable as separable metric spaces and have Borel oe-fields coinciding with
the oe-field generated by the coordinate projections. For we denote by
x(t\Gamma) the left limit at t and by \Deltax(t) , the jump at
As in Varadhan [22], we say that a function I(x) defined on a metric space S and taking values
in [0; 1] is a rate function if the sets fx ag are compact for all a - 0, and a sequence
probability measures on the Borel oe-field of S (or a sequence of random elements
with values in S and distributions P n ) obeys a large deviation principle (LDP) for a
normalizing sequence a n !1 with the rate function I if
lim
log
for all closed F ae S, and
lim
log
for all open G ae S.
The standard choice of the normalizing sequence is a We mention that an LDP can
always be reduced to this standard form by reparametrizing the family fP
[22], however allowing a general normalizing sequence seems more convenient in applications. We
refer to [20], [22] and [17] for additional background.
We say that a sequence fX n ; n - 1g of random elements of a metric space (S; ae) converges
super-exponentially in probability at rate a n to an element x 0 2 S if, for all ffl ? 0,
lim
and we write X n
1=an
This mode of convergence plays a role in large deviations similar to
the role convergence in probability plays in weak convergence. Properties of super-exponential
convergence in probability that we invoke below can be found in Puhalskii and Whitt [17]. Here we
just mention that if (2.3) holds for with one of the topologies J 1 , M 1 or M 0and x 0
is a continuous function starting at 0 , then it also holds for the locally uniform metric on D(R d ) ,
[17, Lemma 4.2(a)].
The following easy consequence of the contraction principle [22] comes in handy below.
Lemma 2.1. Let X n , Y n and Z n be random variables with values in metric spaces SX , S Y
and SZ , respectively, and let S j SX \Theta S Y \Theta SZ be endowed with product topology. Assume that
the sequence f(X obeys an LDP in S for a normalizing sequence a n with rate
function I X;Y;Z (x; y; z) which is finite only if Y is a bijection. Then the
sequences with the respective rate functions
I X;Z and I Y;Z given by the equalities
I X;Z (x;
I Y;Z (y;
When dealing with an LDP for stationary waiting times, we will use the following version of
Lemma 4.1 in Puhalskii [15].
Lemma 2.2. Let fP n ; n - 1g be a sequence of probability measures on R and I be a rate
function on R . If the bounds (2.1) and (2.2) hold for the sets
obeys an LDP with the rate function I .
The proof follows by Lemma 4.1 in [15].
The next easy lemma is a consequence of the extended contraction principle [17] and continuity
of the supremum map, Whitt [24, Theorems 6.2 and 6.3], the latter theorems carrying over to the
0topology (see the argument of the proof of Theorem 5.1 in [17] for more detail).
Lemma 2.3. Let X with paths from D(R d ) . If the
sequence obeys an LDP in D(R d ) for one of the topologies J 1 , M 1 or M 0
1 and
normalizing sequence a n with rate function I X (x) , which equals infinity at elements of D(R d )
that are either discontinuous or not equal to 0 at 0 , then, for every " ? 0 and t ? 0 ,
lim
0-s-t
Rate functions in the limit theorems below are generally defined in terms of solutions to Skorohod
problems with skew reflection [4, 19, 3]. We now recall the relevant definitions. Let
be a K \Theta K matrix with nonnegative entries and spectral radius less than unity. Denote by P T
the transpose of P and let R P denote the map from D(R K ) into D(R K ) associating to each
that
1.
2. y is componentwise nondecreasing with y k
3. z k (t) - 0 and
The map R P is well defined and Lipshitz continuous for the locally uniform metric on D(R K ) ,
Harrison and Reiman [4], Reiman [19], Mandelbaum [10], Chen and Mandelbaum [2]. In the one-dimensional
case the reflection map, which we then denote R , has the explicit
The following characterization of skew reflection is in the spirit of Lemma 3.1 in [18] and Lemma 4.6
in [15], and is proved by the same argument.
Lemma 2.4. Let z 2 D(R K ) be componentwise nonnegative and x 2 D(R K ) be componentwise
absolutely continuous. Then z only if z is absolutely continuous, and there exists
an absolutely continuous function y 2 D(R K ) with the properties
and
Thus -
a.e. solves a linear complementarity problem [10, 2].
3. Moderate Deviations for Single Server Queues in Near-Heavy Traffic
We consider a sequence of FIFO single server queues indexed by n . We assume that the queues
are initially empty. Let A n (t) denote the number of arrivals by t , S n (t); the number of customers
served for the first t units of the server's busy time, D n (t) , the number of departures by t , Q n (t) ,
the queue length at t , W n (t) , the unfinished work at t , C n (t) , the completed work at t , H n (k) ,
the waiting time of the k th customer, and L n (k) , the departure time of the k th customer.
Let also
be the cumulative service time of the first k customers.
Denoting by ffi the composition map, we have the following obvious equalities
positive numbers. We define the
associated normalized and time-scaled processes by
(D
We assume that - and the near-heavy traffic condition
Note that (3.15) implies that - .
The next theorem parallels the results of Iglehart and Whitt [5], on the one hand, and Theorems
3.1 and 4.1 in Puhalskii and Whitt [18], on the other hand. Let us denote
Theorem 3.1.
(a) Assume that obeys an LDP in D(R 2 ) for one of the topologies J 1 , M 1 or M 0and normalizing sequence b 2
n with rate function I A;S (a; s). Then f(Q obeys an
LDP in D(R 3 ) for the same topology and normalizing sequence b 2
n with rate function
I Q;D;C (q; d; c) = inf
I
(b) Assume that obeys an LDP in D(R 2 ) for one of the topologies J 1 , M 1 or
1 and normalizing sequence b 2
n with rate function I A;V (a; v). Then f(W obeys an
LDP in D(R 2 ) for the same topology and normalizing sequence b 2
n with rate function
I W;C (w; c) = inf
I A;V (a; v) :
(c) Assume that obeys an LDP in D(R 2 ) for one of the topologies J 1 or M 0and normalizing sequence b 2
n with rate function I A;S (a; s), which, in the case of the J 1 topology, is
infinite when s is either discontinuous or not equal to 0 at 0 . Then f(Q
obeys an LDP in D(R 4 ) for the same topology and normalizing sequence b 2
n with rate function
I Q;D;W;C (q; d; w; c) = inf
I
(d) Assume that obeys an LDP in D(R 2 ) for one of the topologies J normalizing sequence b 2
n with rate function I A;S (a; s), which is infinite when either a or s is
either discontinuous or not equal to 0 at 0 . Then the sequence f(Q
1g obeys an LDP in D(R 6 ) for the J 1 topology and normalizing sequence b 2
n with rate function
I Q;D;W;C;H;L (q; d; w; c; h;
I Q;D;W;C;H;L (q; d; w; c; h;
Proof. We begin with a proof of (a). By (3.4), (3.5), (3.3), (3.11), (3.6) and (3.7),
where
Since Q n (t) is nonnegative and
ds increases only when Q
from (3.16) that the process (Q n (t); t - 0) is the Skorohod reflection of the process
and, by (3.18),
By the Lipshitz property of the reflection in the locally uniform metric, we have, for some K(t) ? 0 ,
The LDP for
imply that
lim
lim
1=an
sup
with a
. Hence, by (3.22) and (3.18), since p
ds P 1=an
so by (3.19) and Lemma 3.1 in [14], (for the locally uniform metric on D(R) ) C 0
1=an
e, and
an obvious extension of Lemma 4.3 in [17] implies by the LDP for
that the sequence
obeys an LDP with I A;S . The required now follows by
(3.20), (3.17), (3.21), continuity of the reflection, the near-heavy traffic condition (3.15), and the
contraction principle.
The argument for parts (b) and (c) is similar. For (b), write by (3.2), (3.3), (3.6), (3.8), (3.10),
and (3.12),
where A 0
note that the LDP for fA implies by [17, Lemma 4.2(b)]
that
1=an
-e: (3.24)
Part (c) follows by combining the preceding arguments if one notes that by (3.1) and Theorem 5.4
in [17] the assumptions imply that the sequence obeys an LDP in D(R 3 ) for
one of the topologies J 1 or M 0
1 and normalizing sequence b 2
n with rate function I A;S;V (a; s;
I A;S (a; s), when
We now prove (d). Since the rate function I A;S (a; s) equals infinity at elements of D(R 2 ) that
are either discontinuous or not equal to 0 at 0 , the extended contraction principle [17] implies
that under the assumptions obeys an LDP in D(R 2 ) for the J 1 topology with
the rate function I A;S (a; s).
Let
and U 0
By (3.24) and Lemma 4.2(c) in [17],
1=an
e: (3.26)
Noting also that L n we conclude by Lemma 4.3 and Theorem 5.4
in [17], and part (c) of the theorem we are proving that f(Q
obeys an LDP in D(R 6 ) for the J 1 topology with rate function I 0 (q; d; w; c; h;
when
We now prove that
1=an
which will conclude the proof by Lemma 4.1(c) in [17]. Since W n (U 0
we have that
sup
Since I A;S (a; s) equals infinity when either one of the arguments is either a discontinuous function
or not equal to 0 at 0 , part (c) of the theorem implies that fW n ; n - 1g obeys an LDP in D(R)
for the J 1 topology with rate function which equals infinity both at discontinuous functions from
D(R) and functions not equal to 0 at 0 so that by Lemma 2.3, for t ? 0 ,
sup
0-s-t
as n !1 . Putting together (3.26), (3.28) and (3.29) proves (3.27). The theorem is proved.
Remark 3.1. Let I n (t) denote the cumulative server's idle time at t , i.e., I n
0)ds , and I n
n) . Since obviously I n (see (3.18)), the theorem
provides an LDP for fI n ; n - 1g as well.
Remark 3.2. Parts (c) and (d) show that under the hypotheses "Little's law'' holds: if the rate
function is finite, then sufficient statistic" in the sense of Lemma 2.1.
We now consider the case of quadratic rate functions typical of LDPs for partial sums of triangular
arrays of i.i.d. sequences (see Lemma 6.1 of [17] or [14, Example 7.2]) or partial sums of
interarrival times in superpositions of renewal processes (see Theorem 7.2 of [17]). We adopt the
convention e.g., the rate function I A (a) below, in the case if oe
when
Theorem 3.2. Let condition (3.15) hold. Assume that obeys an LDP in D(R 2 )
for the J 1 topology and normalizing sequence b 2
n with rate function
I A;S (a;
where
I A (a)
A
Z 1-
for absolutely continuous functions a with
I S
Z 1-
for absolutely continuous functions s with otherwise. Then the following
holds.
(a) The sequence f(Q obeys an LDP in D(R 3 ) for the J 1 topology and normalizing
sequence b 2
n with rate function
I Q;D;C (q; d; c) =
A
dt
A
dt;
when q, d and c are absolutely continuous with
is nonpositive and nonincreasing, -
a.e. on the set q(t) ? 0 , and I Q;D;C (q; d;
otherwise.
(b) The sequence f(Q n ; D n ); n - 1g obeys an LDP in D(R 2 ) for the J 1 topology and normalizing
sequence b 2
n with rate function
I Q;D (q; d) =
A
dt
A
dt;
when q and d are absolutely continuous with nonnegative, and
I Q;D (q; d)
(c) The sequence f(Q obeys an LDP in D(R 2 ) for the J 1 topology and normalizing
sequence b 2
n with rate function
I Q;C (q; c) =2(oe 2
when q and c are absolutely continuous with nonnegative, c is nonpositive
and nonincreasing, -
a.e. on the set q(t) ? 0 , and I Q;C (q;
(d) The sequence fQ n ; n - 1g obeys an LDP in D(R) for the J 1 topology and normalizing sequence
n with rate function
I
when q is nonnegative and absolutely continuous with
(e) The sequence fC n ; n - 1g obeys an LDP in D(R) for the J 1 topology and normalizing sequence
n with rate function I C which is as follows. Let ess sup ft
0g.
I C (c) =2(oe 2
Z 1(-
when c is absolutely continuous,
otherwise.
If r - 0, then
I C
Z k(c)(-
when c is absolutely continuous,
Proof. An application of Theorem 3.1(a), Lemma 2.4 (or Lemma 3.1 in [18]) and Lemma 3.3 in
[15] yields the rate function of part (a). The rate functions in (b)-(e) follow by the contraction
principle. In particular, in part (e) it can be proved in analogy with the proof of Theorem 5.1(b)
in [18] that inf q I Q;C (q; c) is attained at
Remark 3.3. Let
nt
where U n (k) is defined by (3.25) and U n By (3.1) and an easy extension of Theorem 5.4 in
[17] to the multidimensional case, the assumed LDP for only if the sequence
obeys an LDP in D(R 2 ) for the J 1 topology and normalizing sequence b 2
n with
rate function I
I U (u) =2oe 2
U
Z 1-
for u absolutely continuous with
I
Z 1-
for v absolutely continuous with
A =- 3 and
More specifically, for a GI=GI=1 queue, i.e., when A n and S n are renewal processes, let us
denote by u n the generic interarrival time and by v n the generic service time. Then the LDP for
Var
and either one of the following conditions is met:
log n=b n !1;
This follows by Lemma 6.1 and Theorem 5.4 in [17].
Remark 3.4. It is interesting to compare I C with the rate function for the arrived work.
Since under the conditions of the theorem obeys an LDP with rate function
I easily follows that the processes ((V n ffi A n (nt) \Gamma nt)=(b n
obey an
LDP in D(R) for the J 1 topology and normalizing sequence b 2
n with rate function
Z 1(-
when x is absolutely continuous, the rate functions look
similarly.
Lemma 2.1 and part (d) of Theorem 3.1 allow us to obtain LDPs for the other processes. For
instance, we have the next result.
Corollary 3.1. Under the conditions of Theorem 3.2, the following holds.
(a) The sequence fW n ; n - 1g obeys an LDP in D(R) for the J 1 topology and normalizing
sequence b 2
n with rate function
I W (w) =2(oe 2
when w is nonnegative and absolutely continuous with
(b) The sequence fH n ; n - 1g obeys an LDP in D(R) for the J 1 topology and normalizing
sequence b 2
n with rate function
I H
when h is nonnegative and absolutely continuous with
Proof. For the proof, it suffices to observe that, by part (d) of Theorem 3.1 and Lemma 2.1,
I W
We can also project even more to get LDPs for one-dimensional distributions. To illustrate, we
give two examples. Denote r
Corollary 3.2. Let the conditions of Theorem 3.2 hold. Then
(a) the sequence fH n (t); n - 1g for t - 0 obeys an LDP in R+ for normalizing sequence b 2
n with
rate function
I H(t)
(b) the sequence fC n (t); n - 1g for t - 0 obeys an LDP in R \Gamma for normalizing sequence b 2
n with
rate function
I C(t)
\Gammaz
\Gamma2-rz
r
Remark 3.5. Note that in "the ergodic case" r ! 0 , the rate function for fC n (t); n - 1g is
the same as for the arrived work f(V n ffi A n
which follows by Remark 3.4.
Remark 3.6. We do not know an explicit expression for I D and I L .
We end the section by showing, analogously to diffusion approximation results, that the LDPs
for the processes of waiting and departure times can be established directly without invoking LDPs
for continuous-time processes, and that for the ergodic GI=GI=1 queue an LDP holds for stationary
waiting times as well (cf. Prohorov [12]). Let us denote by u between the i th and
th arrivals and by v n;i the service time of the i th customer in the n th system. The
associated partial-sum processes U 0
are
given by
so that, as above, V n (k) is the cumulative service time of the first k customers. The obvious
equations for waiting and departure times are
Let
~
Recall that if the n th queue is a GI=GI=1 queue with - then the waiting times H n (k)
converge in distribution as k ! 1 to a proper random variable (see, e.g., Borovkov [1]). We
denote the latter by H 0
n and let H 0
n) .
Theorem 3.3. Let (3.15) hold.
(a) Assume that f( ~
obeys an LDP in D(R 2 ) for one of the topologies J 1 , M 1 or M 0and normalizing sequence b 2
n with rate function I U;V (u; v).
obeys an LDP in D(R) for the same topology and normalizing sequence b 2
n with
rate function
I H
I U;V (u; v) :
If, in addition, I U;V (u; v) is infinite when v is either discontinuous or not equal to 0 at 0 , then
obeys an LDP in D(R 2 ) for the same topology and normalizing sequence b 2
n with
rate function
I H;L (h;
I A;V (a; v) :
(b) Consider a sequence of GI=GI=1 queues for which the conditions of Remark 3.3 hold. Assume
that r ! 0 . Then the sequence fH 0
obeys an LDP in R+ for the normalizing sequence
n with rate function
I H
Proof. We begin with part (a). For the part related to H n , we use that by (2.4), (3.33), (3.35),
(3.8), and (3.13)
e
For the second claim, we use that by (3.34), (3.35), (3.14), (3.13), and (3.8)
the fact that by the hypotheses and Lemma 2.3 sup s-t v n;bnsc+1 =(b n
n) P 1=an
in [17].
We now prove part (b). The argument is borrowed from the corresponding proofs of diffusion
approximation results [12]. Since H 0
n is distributed as sup k-0 (V n
we have, for a
Borel subset A of R+ ,
sup
coincides in distribution with H n (bntc
by Corollary 3.2(a) obeys an LDP with the rate function I H(t) (z) for which
lim t!1 inf z2A I H(t) Lemma 2.2 implies
that the required would follow by
lim
lim
where, as above, a
n .
Denoting we have, since
1-k-2 l
1-k-2 l
Limit (3.36) now follows by Lemma A.1 in the appendix and the near-heavy traffic condition
bn . The theorem is proved.
4. Moderate Deviations for Queueing Networks in Near-Heavy Traffic
We now extend some of the above results to the queueing-networks set-up. Our results here are
in the spirit of Reiman [19]. We consider a sequence of networks indexed by n. The nth network has
a homogeneous customer population and consists of K FIFO single server stations. The network
is open in that customers arrive from outside and eventually leave. Let A n;k
the cumulative number of customers who arrived at station k from outside the network during
the interval [0; t], and let S n;k denote the cumulative number of customers who are
served at station k for the first t units of busy time of that station. We call A
where A the arrival
process and service process respectively (note that some of the entries in A n may equal zero). We
associate with the stations of the network the processes \Phi
where \Phi denotes the cumulative number of customers
among the first m customers who depart station k that go directly to station l. The process
is referred to as the routing process. We consider the processes A n;k ,
S n;k and \Phi n;k as random elements of the respective Skorohod spaces D(R), D(R) and D(R K );
accordingly, A n , S n and \Phi n are regarded to be random elements of D(R K ),
respectively.
We next introduce normalized and time-scaled versions of the arrival process, service process
and routing process. Let - n;k - 0; - n;k - 0; and p kl 2 [0; 1],
A n;k nt
nt
nt
where as above b n !1 and b
Again the latter processes
are considered as random elements of D(R K ),
we denote -
The first two vectors as well as other elements of R K are regarded to be column-vectors.
In analogy with the hypotheses of Section 3, we assume that -
positive, and that the near-heavy
traffic condition holds: for some r 2 R K ,
in particular,
denotes taking the transpose of either a matrix or a vector.) We also assume that
the spectral radius of the matrix P is less than unity.
Our main concern here is the queue-length process Q
denoting the number of customers at station k at time t. Other
related processes can be treated analogously to Section 3. The associated normalized and time-scaled
process defined by
We fix some notation. If x 2 D(R K ) has componentwise nondecreasing nonnegative paths,
accordingly, if
. For a vector
0). For a subset J of f1;
we set F
denotes the K -vector with entries from J equal to 1
and the rest of the entries equal to 0 ; J c denotes the complement of J . We also denote: R 0
is the interior of R+ , 1 is the K -vector with all the components equal to 1 , K is the set of all
the subsets of f1; excluding the empty set. For vectors
Theorem 4.1. Let Q n;k and the near-heavy traffic condition (4.2) hold.
(a) Assume that the sequence obeys an LDP in D(R K \Theta R K \Theta R K \ThetaK ) for one
of the J 1 , M 1 or M 0
1 topologies and normalizing sequence b 2
n with rate function I A;S;\Phi (a; s; OE).
Then obeys an LDP in D(R K ) for the same topology and normalizing sequence b 2
with rate function
I
I A;S;\Phi (a; s; OE) :
(b) Assume, in addition, that I A;S;\Phi has the following form: for
I A;S;\Phi (a; s;
I A k (a k
I
I \Phi k (OE k );
where
I A k (a k ) =2oe 2
a;k
Z 1-
a k (t) 2 dt
for a k absolutely continuous with a k
I S k
Z 1-
for s k absolutely continuous with s k
I \Phi k
Z 1sup
dt;
for absolutely continuous with OE kl
are symmetric nonnegative-definite K \Theta K matrices.
Assume that the symmetric nonnegative-definite K \Theta K matrix \Gamma defined by
is positive definite.
Then obeys an LDP in D(R K ) for the J 1 topology and normalizing sequence b 2
with rate function
I
J2K2
dt;
when q is absolutely continuous with
(c) Assume that the processes A n;k are mutually
independent for each n. Assume that the processes A n;k and S n;k are renewal processes and let
u n;k denote the generic exogenous interarrival time and -
n;k , the generic service time, for station
k . Let the stations be indexed so that, for some K 0
and either one of the following conditions be met:
log n=b n !1;
If, in addition, the routing mechanism does not depend on n and is i.i.d. at each station with p kl
being the probability of going directly from station k to station l, then the conditions of part (b)
hold with
u;k
\Gammap kl p km
Also
I \Phi k (OE k ) =2
OE kl (t)
dt +2
Z 1-
for absolutely continuous with OE kl
Remark 4.1. If the matrix \Gamma is degenerate, then the LDP in part (b) holds with the same rate
function I Q provided in its definition expressions of the form 1x are understood
as sup -2R k(-
Remark 4.2. In the expression for I \Phi k
in part c) we again keep to the convention
that, e.g., if
I \Phi k
Z 1-
for absolutely continuous with OE kl
I \Phi k (OE k
Proof of Theorem 4.1. The proof is a straightforward extension of the proof of Theorem 3.1
(cf., a similar argument in the proofs of corresponding weak convergence results in [19, 3]). In
analogy with (3.4), (3.5) and (3.3), we have that for 1 - k - K
where
ds
Introducing
we then have by (4.1) and (4.4) that
n;l (t)
Z t1(Q n;k ds \Gamma
Z t1(Q n;l ds
which implies that
and hence
. The Lipshitz property of
R P , the LDP for (4.2), and the fact that I \Gamma P T is nonsingular yield by
the argument of the proof of (3.23), since - is componentwise positive,
Z t1(Q n;k ds P 1=an
where again a
implying that
1=an
e as
Then by Lemma 4.2(b) in [17]
after which Lemma 4.3 in [17] enables us to conclude that the sequence
1g obeys an LDP in D(R K \Theta R K \Theta R K \ThetaK ) with rate function I A;S;\Phi given by the equality
I A;S;\Phi (a; s; OE OE). The claim of part (a) follows by (4.6) and the contraction
principle.
Part (b) is a consequence of part (a) and Lemma 2.4. In more detail, we have by part (a),
Lemma 3.3 in [15] and Lemma 2.4
I
(a;s;OE)2D(R K \ThetaR K \ThetaR K \ThetaK
I A k (a k
I
I \Phi k (OE k )
Z 1inf
(ff;fi;/;fl)2R K \ThetaR K \ThetaR K \ThetaK \ThetaR K
a;k
dt:
By mean squares, the infimum in the integral over ff; fi and / , for fl fixed, equals ( -
This completes the proof of (b) .
The conditions of (c) imply the conditions of (b) by Lemma 6.1 in [17]. The expression for I \Phi k
in part (c) follows by the fact that if
then the matrix
\Sigma \Phi;k is nondegenerate with
\Phi;k
and
sup
\Phi;k
The theorem is proved.
Remark 4.3. Note that the matrix \Gamma in part (c) coincides with the covariance matrix in
Reiman's result [19].
Remark 4.4. The rate function in part (b) is not as explicit as in Theorem 3.2 in that on the
we need to solve quadratic programming problems. It appears that generally this has to
be done numerically.
Remark 4.5. The contraction principle allows us to deduce that under the conditions of the
theorem one-dimensional projections also obey LDPs. An open question is deriving explicitly the
rate functions as in Corollary 3.2. It is not difficult to see that the optimal paths q must be
piecewise linear. However, we can solve explicitly only the case
and Scherbakov [6]).
We now apply Theorem 4.1 to obtain LDPs for waiting and sojourn times (cf., Reiman [19]).
denote the virtual waiting time at station k at time t . Define
n) and let W . Next, for a vector
denote the number of customers with the
routing exogenously arrived by t , Y n;k (m) denote the sojourn time of the
th exogenous customer with the routing
n) ,
Corollary 4.1. (a). Assume that the sequence obeys an LDP in D(R K \Theta
R K \Theta R K \ThetaK ) for one of the J 1 or M 0
1 topologies and normalizing sequence b 2
n with rate function
I A;S;\Phi (a; s; OE), which, in the case of the J 1 topology, equals infinity unless s is continuous and equal
to 0 at 0 . Then the sequence f(Q n ; W n obeys an LDP in D(R K \Theta R K ) for the same
topology and normalizing sequence b 2
n with rate function I Q;W (q;
-\Omega w , and
I Q;W (q; In particular, the sequence fW n ; n - 1g obeys an LDP in D(R K )
with rate function I W
(-\Omega w) .
(b). Assume, in addition, that the rate function I A;S;\Phi (a; s; OE) equals infinity unless a; s and OE
are both continuous and equal to 0 at 0 , and
1=an
as
Then the sequence f(W obeys an LDP in D(R K \Theta R) for the J 1 topology and
normalizing sequence b 2
n with rate function I W;Y (w;
and I W;Y (w; In particular, the sequence fY n;k
1g obeys an LDP in D(R) for the J 1 topology and normalizing sequence b 2
n with rate function
I Y k
I W (w) .
Proof. The proof is much similar to that of Theorem 4.1. We only give a sketch. Let V n;k (m) ,
denote the cumulative service time of the first m customers
served at station
denote the total number of arrivals to station k by time
Introducing V n;k
we have, in analogy
with (4.5),
In analogy with (4.8) and in view of (4.3), Lemma 4.2(b) in [17] implies that
1=an
-e: (4.10)
Therefore, recalling (4.6), (4.8) and (4.7), we have that the sequence
1g obeys an LDP in D(R K \ThetaR K \ThetaR K \ThetaR K \ThetaK \ThetaR K \ThetaR K ) with rate function I A;S;V;\Phi;Q;W (a; s; v; OE; q; w)
such that whenever it is finite the following equations hold
By the contraction principle, the sequence fQ n ; W n obeys an LDP in D(R K \Theta R K ) with
rate function I Q:W (q; w) that is infinity unless
-\Omega w . An application of Lemma 2.1 ends the
proof of (a).
We now turn to (b) . Note first that the argument of the proof of part (a) implies that the
sequences for the J 1 topology with rate functions
which equal infinity both at discontinuous functions and functions not equal to 0 at 0 .
Next, let us denote by U n;k (m) the arrival time of the m th exogenous customer with the
routing vector k , by T n;k;i it arrives at the i th queue of its itinerary, by
H n;k;i (m) , the time it awaits service in the i th station, and by v n;k;i (m) , the time it is served in
the i th station. We obviously have
and
Inequalities (4.12) account for the fact that we make no assumptions about the mechanism of
resolving conflicts between simultaneous arrivals. Next, it is easily seen thatb n
t by the assumption A 0
1=an
and Lemma 4.2(c) in [17], W n;k (bntc)=n P 1=an
by the LDP for fW n ; n - 1g and Lemma 4.2(c) in
[17], and sup s-t j\DeltaV n;k (s)j P 1=an
by the fact that fV n ; n - 1g obeys an LDP with rate function
that equals infinity both at discontinuous functions and functions not equal to 0 at 0 and by
Lemma 2.3, it follows from (4.11), (4.12) and (4.13) that, for
and
sup
0: (4.
. The LDP for fW
(4.12) imply, by Lemmas 4.1(c) and 4.3 in [17] and Lemma 2.3, that f(H
1g obeys an LDP in D(R l \Theta R K ) with rate function I H k;1 ;:::;H k;l ;W (h
when h
e); and equal to infinity otherwise. The proof is completed by noting that
l
l
and using (4.15), Lemma 4.1(c) in [17], and the contraction principle. The corollary is proved.
Remark 4.6. If the routing mechansim is as described in part (c) of Theorem 4.1, then
convergence (4.9) in part (b) holds with - k
. This follows by Theorem 6.3 in
[18] and Lemma 4.2(b) in [17].

Acknowledgement

. I am grateful to Ward Whitt for fruitful discussions and suggesting
Theorem 3.3(a) and to Marty Reiman for valuable comments on the content of the paper.
A.

Appendix


We state and prove the lemma used in the proof of Theorem 3.3(b).
Lemma A.1. Let f- n;i be a triangular array of row-wise i.i.d. r.v. with zero
mean. Let b n !1 as n !1 , and ff ? 0 .
exist
(ii) If, for some
there exist n 0
(b n
Proof. The argument uses the ideas of the proof of Example 7.2 in [14]. Let the conditions of (i)
hold. We first prove that there exist C 1 ? 0 and t 0 such that for t - t 0
By Doob's inequality (see, e.g., Liptser and Shiryaev [9, Theorem 1.9.1]), for - ? 0 ,
Ee 2-
Ee 2-
so
Ee 2-
Choosing in
ff=2 , we get
Now note that, since E- by the Chebyshev inequality,
hence
so, by the fact that
large enough and t - t 0 ,
which together with (A.5) proves (A.3).
Estimate (A.1) now follows by (A.3), the inequalities
and
Part (i) is proved.
For part (ii), we write
Noting that the conditions of part (ii) imply the conditions of part (i), we estimate the first term
on the right with the help of (A.3). For the second, we use the inequality
We first work with the second probability on the right. We have, for - ? 0 , by the Chebyshev
inequality,
A
"' bntc
Next, for
c
A
nt
Taking
t=2 , it is not difficult to see by (A.9), (A.10) and the condition
large enough,
A - exp
\GammaC 00
By a similar argument, this bound is seen to hold for
Finally, the first term on the right of (A.8) is estimated as
nt Ee flj- n;1 j fi
e fl(b n
Substituting the estimates into (A.7) finishes the proof of (ii). The lemma is proved.



--R

Stochastic processes in queueing theory (in Russian: Nauka
systems
Diffusion Approximations for Open Queueing Networks with Service Interruptions
Reflected Brownian Motion on an Orthant
Multiple Channel Queues in Heavy Traffic
Boundary effects in large deviation problems
On queues in heavy traffic
Weak Convergence of Probability Measures and Random Functions in the Function Space D
Theory of Martingales (Kluwer
The Dynamic Complementarity Problem
A Unified Approach Via Graphs to Skorohod's Topologies on the Function Space D
Transient phenomena in queueing processes (in Russian)
On Functional Principle of Large Deviations
Large Deviations of Semimartingales Via Convergence of the Predictable Char- acteristics
Large Deviation Analysis of the Single Server Queue
Large Deviations of Semimartingales: a Maxingale Problem Approach.
Functional Large Deviation Principles for First Passage Time Processes
Functional Large Deviation Principles for Waiting and Departure Processes (submitted).
Open Queueing Networks in Heavy Traffic
Large Deviations for Performance Analysis (Chapman and Hall
Limit Theorems for Stochastic Processes
Large Deviations and Applications (SIAM
Limit Theorems on Large Deviations for Markov Random Processes (Nauka
Some Useful Functions for Functional Limit Theorems
--TR

--CTR
Kurt Majewski, Sample path moderate deviations for the cumulative fluid produced by an increasing number of exponential on-off sources, Queueing Systems: Theory and Applications, v.56 n.1, p.9-26, May       2007
queues;large deviation principle;heavy traffic