The Single Server Queue and the Storage Model: Large Deviations and Fixed Points

Moez DRAIEF Statistical Laboratory, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB UK Tel: +44 1223337945 E-mail: M.Draief@cam.ac.uk

Abstract
We consider the coupling of a single server queue and a storage model defined as a Queue/Store model in [6, 7] . We establish that if the input variables both arrivals to the queue and to the store satisfy large deviations principles and are linked through an exponential tilting than the output variables (departures from each system) satisfy large deviations principles with the same rate function. This generalizes to the context of large deviations the extension of Burke's Theorem derived in [6, 7] .
Résumé
Nous établissons un résultat de point fixe dans le cadre des grandes déviations pour le modèle File d'attente/Modèle de Stockage introduit dans [6, 7] . Plus précisément si les variables d'entrée du système vérifient des principes de grandes déviations avec des fonctions de taux liées par une relation d'inclinaison exponentielle alors il en est de même pour les variables de sortie dont les fonctions de taux sont les mêmes que celles des variables d'entrée.
Keywords: Single server queue, storage model, large deviations, Burke's theorem.

1 Introduction

A celebrated theorem of Burke's [1] asserts that when a Poisson process { a n , n ∈ Z }   with mean inter-arrival time 1 / λ   is input to a single server queue whose service times { s n , n ∈ Z }   are i.i.d. exponentials (./M/1/ ∞   following the Kendall nomenclature) with mean 1 / μ < 1 / λ   , the equilibrium departure process { d n , n ∈ Z }   from the queue is also a mean 1 / λ   Poisson process.
In this sense the mean 1 / λ   Poisson process is a fixed point for the ./M/1/ ∞   operator. In [6, 7] , we generalized to the couple of departures and the sequence of times spent at the very back of the queue { r n , n ∈ Z }   , that can also be seen as the sequence departures from a storage model, where s n   is the amount of P   Supplied at slot n + 1   , and a n   is the amount of P   Asked for at the same slot. More precisely, we show that under the conditions of Burke's theorem the couple of output variables from the Queue/Store model { ( d n , r n ) , n ∈ Z }   has the same law as the couple of input variables { ( a n , s n ) , n ∈ Z }   .
In this paper, we consider the fixed point question at large deviations scaling. A similar result have been presented by Ganesh et al. in [11] for discrete-time queues. Assuming that the input variables satisfy a large deviation principle, we show that if their laws are linked through an exponential tilting that than the large deviation principle is preserved by the Queue/Store system, i.e. the output variables satisfy large deviations principles with the same rate functions as the input variables.
The paper is organized as follows: section  2 is devoted to giving some background on large deviations that will be useful for our analysis. The Queue/Store model is presented in section  3 . Section  4 focuses on the workload process. We define the concept of effective bandwidth in section  5 . At last, in section  6 , we derive a large deviations principle for the output variables of the Queue/Store model (§ 6.1 ) and we give the condition on the rate functions of the input variables (§ 6.2 ) which are preserved by the Queue/Store operator.

2 Large deviations

We are not going to give a survey on large deviations, we are just aiming to make the work self contained, for more details on large deviations we refer to Dembo and Zeitouni's reference book [5] .
Let x = { x n , n ∈ N }   be a sequence of i.i.d. random variables and define X = { X n , n ∈ N }   by X n = ∑ i = 1 n x i .   If E | x 0 | < ∞   , than X   satisfies the strong law of large numbers, i.e., lim n → ∞ X n n = E x 0 a . s .   We also focus on the fluctuation of a random variable around its mean. Suppose E x 0 2 < ∞   then the central limit theorem gives the fluctuations of the scale of O ( 1 / n )   , of X n / n   around E x 0   . More precisely the sequence n ( X n n − E x 0 )   converges in law to the normal law with mean zero and variance the one of x 0   . Large deviations theory deals with the fluctuations of the scale of O ( 1 )   .
Definition 2.1. Let X   be a Hausdorff space. A function I : X → R ¯ + = R + ∪ { ∞ }   is a rate function if I   is lower semi-continuous, i.e. the sets { x : I ( x ) ≤ α }   are closed, for all α ∈ R   . In addition, if these sets are compact than I   is a good rate function.
Definition 2.2. A sequence { x n , n ∈ N }   in X   satisfies a large deviations principle with the rate function I : X → R ¯ +   , if for all Borel set ℬ   of X   ,
− inf x ∈ ℬ ∘ I ( x ) ≤ liminf n → ∞ 1 n log P ( x n ∈ ℬ )
≤ limsup n → ∞ 1 n log P ( x n ∈ ℬ ) ≤ − inf x ∈ ℬ ¯ I ( x ) ,
where ℬ ∘   denotes the interior of ℬ   and ℬ ¯   its closure.
Throughout the rest of this section, we are interested in real-valued random variables.
Definition 2.3. The cumulant generating function of a real-valued random variable x   is given by Λ X ( θ ) = log E e θ x , ∀ θ ∈ R ,   which can be infinite.
Using Hölder inequality and Fatou lemma we check that Λ X   is convex, lower semi-continuous and for all θ   in the effective domain of Λ X   (i.e. { θ | Λ X ( θ ) < ∞ }   ), we have Λ X ′ ( θ ) = E ( X 0 e θ X 0 ) e Λ X ( θ ) .  
Definition 2.4. The Legendre transform of Λ X   is defined by
I X ( x ) = sup θ ∈ R { θ x − Λ X ( θ ) } . (1)
The function I X   is positive, convex, and lower semi-continuous. If Λ X   is finite at the origin then Λ X ′ ( 0 ) = E X 0 , I X ( E X 0 ) = 0 .   Moreover, we check easily that
I X ( x ) = sup θ ≥ 0 { θ x − Λ X ( θ ) } for x ≥ E x 0
I X ( x ) = sup θ ≤ 0 { θ x − Λ X ( θ ) } for x ≤ E x 0 . (2)
We recall the statement of Cramér theorem for real-valued random variables.
Theorem 2.5. Let { x n , n ∈ N }   be an i.i.d. sequence of real-valued random variables and let Λ X   be its cumulant generating function which we suppose finite at the origin, then the sequence of random variables { X n / n , n ∈ N * }   , where X n = ∑ i = 1 n x i   , satisfies a large deviations principle with rate function I X   defined in ( 1 ):
for all closet set F   of R   ,
limsup n → ∞ 1 n log P ( S n ∈ F ) ≤ − inf x ∈ F I X ( x ) . (3)
and for all open set O   of R  
liminf n → ∞ 1 n log P ( S n ∈ O ) ≥ − inf x ∈ O I X ( x ) . (4)
The inequalities ( 3 ) and ( 4 ) are known as the upper bound and the lower bound of the large deviations principle. For the different extensions of Cramér theorem we refer to [5] . We can have a large deviations principle for a couple of independent random variables.
Theorem 2.6. Let { x n , n ∈ N }   and { y n , n ∈ N }   be two sequences in X   and Y   two Hausdorff spaces satisfying large deviations principles on X   and Y   , with rate functions I X   and I Y   . Suppose that they are independent, then the sequence { ( x n , y n ) , n ∈ N }   satisfies a large deviations principle on X × Y   with rate function I X , Y ( x , y ) = I X ( x ) + I Y ( y ) .  
In this paper, we will establish large deviations principles relying on indirect methods. Once we have a large deviations principle for one sequence of random variables, we can effortlessly obtain large deviations principles for a whole class of random sequences, namely those obtained via continuous transformations. We present the contraction principle, the tool that enables this.
Theorem 2.7. If { x n , n ∈ N }   satisfies a large deviations principle on X   with rate function I X   , and if f : X → Y   is a continuous function. Then the sequence { y n , n ∈ N }   defined by y n = f ( x n )   satisfies a large deviations principle on Y   with rate function I Y ( y ) = inf x , f ( x ) = y I X ( x ) .  
Sometimes f   is ”almost continuous”, i.e. the sequence { y n , n ∈ N }   is close to a sequence { f ( x n ) , n ∈ N }   , where f   is continuous.
Definition-Proposition 2.8. Let { x n , n ∈ N }   and { y n , n ∈ N }   be two sequences of X   with metric | | | |   . They are said exponentially equivalent, if for all ε > 0   , limsup n → ∞ log P ( | | x n − y n | | > ε ) = − ∞ .   In this case, if { x n , n ∈ N }   satisfies a large deviation principle then { y n , n ∈ N }   satisfies a large deviations principle, and I X = I Y   .
Theorem 2.9. If { x n , n ∈ N }   satisfies a large deviations principle on X   with rate function I X   , and if { y n , n ∈ N }   and { f ( x n ) , n ∈ N }   are exponentially equivalent, with f : X → Y   continuous, then { y n , n ∈ N }   satisfies a large deviations principle on Y   with rate function I Y ( y ) = inf x ∈ X , f ( x ) = y I X ( x ) .  

3 The Model

Let A = { A n , n ∈ Z }   be a point process and assume that A 0 ≤ 0 < A 1   and A n < A n + 1 , ∀ n ∈ Z   . We define the R + *   -valued sequence of r.v's a = { a n , n ∈ Z }   by a n = A n + 1 − A n   . Let s = { s n , n ∈ Z }   be another R + *   -valued sequence of r.v's. The sequences a   and s   are the input variables of the model.
Define the sequence of r.v.'s D = { D n , n ∈ Z }   by
D n = sup k ≤ n [ A k + ∑ i = k n s i ] . (5)
A priori the D n   's are valued in R ∪ { + ∞ }   . Assume from now on that a   and s   are such that the D n   's are almost surely finite. Set d n = D n + 1 − D n   and d = { d n , n ∈ Z }   . Define an additional sequence of r.v.'s r = { r n , n ∈ Z }   , valued in R + *   , by
r n = min ( D n , A n + 1 ) − A n . (6)
The sequences d   and r   are the output variables of the model. In view of the future analysis, it is convenient to define the following auxiliary variables. Let w = { w n , n ∈ Z }   be the sequence of r.v.'s valued in R +   and defined by
w n = D n − s n − A n = sup k ≤ n − 1 [ ∑ i = k n − 1 ( s i − a i ) ] + . (7)
These r.v.'s satisfy the recursive equations:
w n + 1 = [ w n + s n − a n ] + . (8)
Using the variables w n   , we can give alternative definitions of D n   and r n   :
∀ l ≤ n , D n = [ w l + A l + ∑ i = l n s i ] ∨ max l < k ≤ n [ A k + ∑ i = k n s i ] , (9)
r n = min { w n + s n , a n } = s n + w n − w n + 1 . (10)
We now interpret the variables defined above in two different contexts: a queueing model and a storage model.

3.1 The single-server queue

A bi-infinite string of customers is served at a queueing facility with a single server. Each customer is characterized by an instant of arrival in the queue and a service demand. Customers are served upon arrival in the queue and in their order of arrival. Since there is a single server, a customer may have to wait in a buffer before the beginning of its service. Using Kendall's nomenclature, our model is a . / . / 1 / ∞ /   FIFO queue. The customers are numbered by Z   according to their order of arrival in the queue (customer 1 being the first one to arrive strictly after instant 0). Let A n   be the instant of Arrival of customer n   and s n   its Service time.
Then the variables defined in ( 5 )-( 8 ) have the following interpretations:
  • ∙ D n   is the instant of departure of customer n   from the queue, after completion of its service; { d n , n ∈ Z }   is the sequence of inter-departure times;
  • ∙ w n   is the waiting time of customer n   in the buffer between its arrival and the beginning of its service;
  • ∙ r n   is the time spent by customer n   at the very back of the queue.
The variables { r n , n ∈ Z }   are less classical in queueing theory although they have already been considered by Gallager and Prabhakar [9] . They should be viewed as being dual to the services { s n , n ∈ Z }   .

3.2 The storage model

Some product P   is supplied, sold and stocked in a store in the following way. Events occur at integer-valued epochs, called slots. At each slot, an amount of P   is supplied and an amount of P   is asked for by potential buyers. The rule is to meet all the demand, if possible. The demand of a given slot which is not met is lost. The supply of a given slot which is not sold is not lost and is stocked for future consideration.
Let s n   be the amount of P   Supplied at slot n + 1   , and let a n   be the amount of P   Asked for at the same slot. The variables in ( 5 )-( 8 ) can be interpreted in this context:
  • ∙ w n   is the level of the stock at the end of slot n   . It evolves according to ( 8 );
  • ∙ r n   is the demand met at slot n + 1   , see equation ( 10 ); it is the amount of P   departing at slot n + 1   ;
The variables { D n , n ∈ Z }   do not have a natural interpretation in this model.
It is important to remark that while the equations driving the single server queue and the storage model are exactly the same, it is not the same variables that make sense in the two models. The important variables are the ones corresponding to the departures from the system.
The departures are coded in the variables { d n , n ∈ Z }   for the single server queue and in the variables { r n , n ∈ Z }   for the storage model. For a more evolved discussion on these two models we refer to [7] .

3.3 Rare events

We recall that w n   the waiting time of customer n   before it starts its service (respectively the level of the stock at the end of slot n   ) is given by
w n = ( w n − 1 + s n − 1 − a n − 1 ) + = sup m ≤ n [ ∑ k = m n − 1 s k − a k ] . (11)
We assume that the sequences a = { a n , n ∈ Z }   and s = { s n , n ∈ Z }   are stationary and ergodic. Under the stability condition E s 0 < E a 0   , we can use the above expression of w n   to give its asymptotic behaviour using the large deviations properties of the input variables a = { a n , n ∈ Z }   and s = { s n , n ∈ Z }   . We start with an example.

Example

Suppose that the customers arrive in a deterministic fashion, i.e. a n = 1 , ∀ n   , and that the sequence { s n , n ∈ Z }   is i.i.d. with P ( s n = 2 ) = 1 − P ( s n = 0 ) = p < 1 2 .   The process { w n , n ∈ Z }   is a discrete time Birth-and-Death with stationary distribution P ( w 0 ≥ q ) = ( p 1 − p ) q .   We get 1 n log P ( w 0 ≥ n q ) = − δ q ,   where δ = log 1 − p p   .
This approximation remains true under general conditions on the input variables, with an expression of δ   that depends on the rate functions associated to the sequences a   and s   . Indeed it has been proved [2, 8, 13] that the stationary version of w n   satisfies the following property
lim n → ∞ 1 n log P ( w 0 > n q ) = − δ q . (12)
We will rewrite ( 12 ) in the following way P ( w 0 / n > q ) ≍ e − n δ q .   First we give a heuristic prove of this result which will be proved rigorously in section  4 . We assume the sequences { a n , n ∈ Z }   and { s n , n ∈ Z }   i.i.d. mutually independent with Λ A ( θ ) = log E e θ a 0 , Λ S = log E e θ s 0 ,   finite near the origin. Let x n = s n − a n   for all n ∈ Z   , and X k = ∑ i = 1 k x − i   for all k ∈ N   then w 0 = sup k ≥ 0 X k   , with X 0 = 0   . Using Cramér theorem (Theorem  2.5 ), the sequences { a n , n ∈ Z }   and { s n , n ∈ Z }   satisfy large deviations principles on R   with rate function I A   and I S   the Legendre transforms of Λ A   and Λ S   . Thus the sequence { x n , n ∈ Z }   satisfies a large deviations principle with rate function I X   , which is the Legendre transform of Λ X ( θ ) = Λ S ( θ ) + Λ A ( − θ )   , i.e. P ( X n n > x ) ≍ e − n I X ( x )   . Moreover,
P ( w 0 ≥ n q ) = P ( sup k ≥ 0 X k ≥ n q ) = P ( ∪ k ≥ 0 { X k ≥ q n } )
≤ ∑ k = 1 ∞ P ( X k ≥ q n ) .
Since P ( X k ≥ n q ) = P ( X k k ≥ n q k ) ≍ e − k I X ( n q / k )   , we check that
P ( w 0 ≥ n q ) ≍ ∑ k = 1 ∞ e − n q I X ( n q / k ) n q / k . (13)
We conclude using the principle of the largest term, i.e.
∑ k = 1 ∞ e − n q I X ( n q / k ) n q / k ≍ e − q n δ   where δ = inf x > 0 I X ( x ) x   and we get ( 12 ). The principle of the largest term translates the fact that rare events occurs in the most likely way. Indeed the dominant term in ( 13 ) which gives the explosion of the waiting times in the queueing system or the overflow of the stock in the storage model happen following the most probable scenario.

4 Large deviations for the workload process

First, we give the assumptions under which the approximation ( 12 ) is fulfilled. For more general assumptions we refer to the paper by Ganesh et al. [12] .

Assumptions:

  • ( i )   The sequences { a n , n ∈ Z }   and { s n , n ∈ Z }   are i.i.d., mutually independent. Their cumulant generating functions given by Λ A ( θ ) = log E e θ a 0 , Λ S ( θ ) = log E e θ s 0   differentiable near the origin.
  • ( i i )   The stability condition 1 / μ = Λ S ′ ( 0 ) = E s 0 < E a 0 = Λ A ′ ( 0 ) = 1 / λ   is satisfied.
Under ( i )   and ( i i )   , we have
Proposition 4.1. The sequence { w 0 / n , n ∈ N * }   satisfies a large deviations principle with good rate function I W ( q ) = δ q   , i.e. lim n → ∞ 1 n log P ( w 0 / n ≥ q ) = − δ q   , with
δ = inf 0 < a < s I A , S ( a , s ) s − a = sup { θ : Λ S ( θ ) + Λ A ( − θ ) ≤ 0 } . (14)
  • Proof. First we prove ( 14 ). Recall that x n = s n − a n   , X n = ∑ i = 1 n x − i   , and w 0 = sup k ≥ 0 X k .   By the independence assumption we have Λ X ( θ ) = Λ S ( θ ) + Λ A ( − θ ) .   Applying the contraction principle we check that I X ( x ) = inf y > x { I S ( y ) + I A ( y − x ) } .   Let θ ≤ inf x ≥ 0 I X ( x ) / x   then
    θ ≤ inf x ≥ 0 I X ( x ) / x ⇔ θ ≤ I X ( x ) / x , ∀ x ≥ 0
    ⇔ θ x − I X ( x ) ≤ 0 , ∀ x ≥ 0
    ⇔ sup x ≥ 0 { θ x − I X ( x ) } ≤ 0
    ⇔ Λ X ( θ ) ≤ 0 .
    The last equivalence is due to E x 0 < 0   (stability condition) et and the equation ( 2 ). We proved that inf 0 < a < s I A , S ( a , s ) s − a = inf x ≥ 0 I X ( x ) / x = sup { θ : Λ S ( θ ) + Λ A ( − θ ) ≤ 0 } .   ∙   Lower bound: For q > 0   , we have P ( w 0 ≥ q ) ≥ P ( X k ≥ q )   . Notice that for p > 0   , p ≥ q ⌈ q / p ⌉   , we have P ( w 0 ≥ q ) ≥ P ( 1 ⌈ q / p ⌉ X ⌈ q / p ⌉ ≥ p ) .   Since 1 q ≥ 1 p 1 ⌈ q / p ⌉   , we get
    liminf q → ∞ 1 q log P ( w 0 ≥ q ) ≥ 1 p liminf q → ∞ 1 ⌈ q / p ⌉ log P ( 1 ⌈ q / p ⌉ X ⌈ q / p ⌉ ≥ p )
    = 1 p liminf n → ∞ 1 n log P ( 1 n X n ≥ p ) ≥ − 1 p I X ( p ) ,
    for all p > 0   . Then we conclude that
    liminf q → ∞ 1 q log P ( w 0 ≥ q ) ≥ − inf x > 0 1 x I X ( x ) = − inf x > 0 1 x inf y > x { I S ( y ) + I A ( y − x ) }
    = − inf 0 < a < s I S ( s ) + I A ( a ) s − a .
    ∙   Upper bound: Recall that Λ X ( θ ) = Λ S ( θ ) + Λ A ( − θ )   . By the stability condition, we have Λ X ′ ( 0 ) = log E ( s 1 ) E ( a 1 ) < 0 .   Moreover, Λ X   is differentiable near 0   with Λ X ( 0 ) = 0   . Thus there is a constant Θ > 0   such that Λ X ( Θ ) < 0   and E e Θ X n < ∞   . Applying Chernoff 's bound, we n ∈ N   , we get P ( X n ≥ q ) ≤ e − Θ q E e Θ X n .   This leads to limsup q → ∞ 1 q log P ( X n ≥ q ) ≤ − Θ .   For N ∈ N   , we check that P ( max 0 ≤ n ≤ N X n ≥ q ) ≤ N max 0 ≤ n ≤ N P ( X n ≥ q ) .   Letting q   goes to infinity, limsup q → ∞ 1 q log P ( max 0 ≤ n ≤ N X n ≥ q ) ≤ max 0 ≤ n ≤ N limsup q → ∞ log 1 q P ( X n ≥ q ) ≤ − Θ .   Then P ( sup n > N X n ≥ q ) ≤ ∑ n > N P ( X n ≥ q ) ≤ e − Θ q ∑ n > N E e Θ X n .   Since 1 n log E e Θ X n = Λ X ( Θ ) < 0   , there is 0 < ε < − Λ X ( Θ )   et N Θ ∈ N   such that ∀ n > N Θ , . 1 n log E e Θ X n ≤ − ε .   Then P ( sup n > N Θ X n > q ) ≤ e − Θ q ∑ n > N Θ e − n ε < e − Θ q 1 − e − ε e − ( N Θ + 1 ) ε .   To summarize the above proof, we have limsup q → ∞ 1 q log P ( sup n > N Θ X n ≥ ) ≤ − Θ .   Therefore, for Θ > 0   such Λ X ( Θ ) < 0   , we have limsup q → ∞ 1 q log P ( sup n ≥ 0 X n ≥ q ) ≤ − Θ .   We conclude using ( 14 ).
This result can be interpreted naively in terms of the following approximation P ( sup n X n ≥ q ) ≈ sup n P ( X n ≥ q ) .   This is nothing more then a consequence of the fact that rare events occur in the most likely way. Moreover using this approximation one can predict the frequency at which the waiting time (or the level of stock) overflows a given threshold. Indeed if ( 12 ) is fulfilled, then we represent the graph (in logarithmic squale) of the frequency of exceeding a level q   . The above approximation (Proposition  4.1 ) inspired numerous applications (described by Courcoubetis et al. [3] ) of large deviations to the analysis of the statistics of networks of queues.

5 Effective bandwidth

The bandwidth of a traffic flow has become a classical feature in communication networks literature. We are interested in the notion of effective bandwidth introduced by Kelly in [15] , which gives an analytical way of describing the properties of a stochastic flow by means of rare events occurring in the network it passes through.
In practice the queues and stores we are interested in have finite capacities, i.e. the queue (respectively the store) rejects customers (respectively stock) each time the waiting time (respectively the amont of stock) overpasses a given threshold. In the queueing context, we assume { s n , n ∈ Z }   given and we seek the (deterministic) minimal value a p   of inter-arrival times such that the probability of the waiting times exceeding the threshold is less than p   fixed. For the storage model, we assume { a n , n ∈ Z }   given and we seek the maximal value s p   of product arriving at the store at each slot of time such that the store rejects it with a probability less then p   . More precisely, we want to identify the arrivals to both models such that
P ( w 0 ≥ q ) ≤ p , (15)
for q   and p   given.

Queue

Let a n = a , ∀ n ∈ Z   , i.e. Λ A ( θ ) = a θ   . If s   is i.i.d., then by Proposition  4.1 , P ( w 0 ≥ q ) ≤ e − δ ( a ) q   with δ ( a ) = sup { θ : θ ≥ 0 et Λ S ( θ ) ≤ a θ } .   The minimal inter-arrival time for the inequality ( 15 ) to be fulfilled is given by a p   such that a p = inf { a : a ≥ 0 et e − δ ( a ) q ≤ p } .   Let θ p = − log p q   . Then δ ( a p ) = θ p   and a p = Λ S ( θ p ) θ p .   We will call the effective bandwidth for the queue. For more details we refer to Kelly's review [14] .

Store

Let s n = s , ∀ n ∈ Z   . Then, Λ S ( θ ) = θ s   and δ ( s ) = − inf { θ < 0 : Λ A ( θ ) ≤ s θ } .   To have ( 15 ) satisfied, we should allow not more than s p   amount of stock to arrive to the store at each slot with s p = sup { s ≥ 0 : e − δ ( s ) q ≤ p } .   The quantity s p   is the effective bandwidth of the store, with s p = Λ A ( θ p ) θ p .   We generalize this notion to non deterministic arrivals by introducing the functions α A ( θ )   and α S ( θ )   given by α A ( θ ) = Λ S ( θ ) θ , α S ( θ ) = Λ A ( θ ) θ ,   representing the effective bandwidths of the queue and the store.

6 Principal of large deviations for the output variables

In section  4 , we prove a large deviations principle for the workload process using classical techniques to get large deviations principles. These techniques are hard to apply to prove large deviations principles for the output variables. Instead we are going to make use of the contraction principle. Following the outline of the proof of the existence of fixed points for discrete-time queues in [11] we use theoretical results on large deviations for continuous-time processes.
First we get back to the workload process to illustrate this method. For n ∈ N *   , we define A n = ∑ i = 1 n a − i , S n = ∑ i = 1 n s − i .   It is obvious that w 0 = sup k ≥ 0 ( S k − A k )   .
To apply the contraction principle it is crucial to define an adapted topology under which the workload process is obtained through a continuous mapping of the input variables. Therefore we define the polygonal approximation in n   of a given sequence { X k , k ∈ N * }   by X ~ n ( t ) = 1 n X ⌊ n t ⌋ + ( t − ⌊ n t ⌋ n ) ( X ⌊ n t ⌋ + 1 − X ⌊ n t ⌋ ) , t ≥ 0 .   Let A ~ n   and S ~ n   the polygonal approximations in n   of the sequences { A k , k ∈ N }   and { S k , k ∈ N }   .
Notice that for n ∈ N *   ,
w 0 n = 1 n sup k ∈ N ( S k − A k ) = 1 n sup t ≥ 0 ( S ⌊ n t ⌋ − A ⌊ n t ⌋ )
= sup t > 0 ( S ~ n ( t ) − A ~ n ( t ) ) .
A function x   is absolutely continuous on R   if ∀ ε > 0 , ∃ η > 0 such that ∀ u , v ∈ R , | u − v | ≤ η ⇒ | x ( u ) − x ( v ) | ≤ ε .   If x   is absolutely continuous, then its derivative x ′   exists almost everywhere and we can write x ( v ) − x ( u ) = ∫ u v x ′ ( t ) d t .   For μ > 0   , we define C μ   (respectively A μ   ) the set of continuous functions (respectively absolutely continuous) x : R + → R   with x ( 0 ) = 0   and lim t → + ∞ x ( t ) t + 1 = 1 / μ < ∞ ,   equipped with the norm
| | x | | = sup t ∈ R + | x ( t ) t + 1 | . (16)
We now focus on large deviations on processes in continuous time in C μ   .
Definition 6.1. A sequence of processes { X n , n ∈ N }   , where X n ∈ C μ   satisfies a functional large deviations principle with linear geodesy, with instantaneous rate function I   , if
  • ( i )   the function I   is a rate function, with I ( 1 / μ ) = 0   ,
  • ( i i )   the sequence { X n , n ∈ N }   satisfies a large deviations principle C μ   with rate function ℐ X ( φ ) = { ∫ 0 + ∞ I ( φ ′ ( t ) ) d t if φ ∈ A μ + ∞ otherwise.  
Dembo and Zajic explored extensions [4] of large deviations principles to processes in continuous time under the topology of uniform convergence. However, this topology is not appropriate in the context of queueing systems. We introduce a finer topology corresponding to the norm ( 16 ). The following large deviations principle is due to Ganesh and O'Connell [10] . Notice that if x = { x n , n ∈ N }   an i.i.d. sequence with mean 1 / μ   , that for n ∈ N *   , X ~ n ∈ C μ   , where X ~ n   is the polygonal approximation in n   of the sequence X = { X n , n ∈ N }   with X n = ∑ i = 1 n x i  
Theorem 6.2. [10] Let x = { x n , n ∈ N }   be a sequence of real-valued random variables and Λ X   its cumulant generating function, which we suppose differentiable near the origin. the sequence of polygonal approximations { X ~ n , n ∈ N * }   of X = { X n , n ∈ N }   , where X n = ∑ i = 1 n x i   , satisfies a functional large deviations principle with linear geodesics on C μ   with the norm ( 16 ), with mean 1 / μ = Λ X ′ ( 0 )   and instantaneous rate function I X   , i.e. ℐ X ( φ ) = { ∫ 0 + ∞ I X ( φ ′ ( t ) ) d t if φ ∈ A μ + ∞ otherwise.  
Under ( i )   , the processes A ~ n   and S ~ n   satisfy functional large deviations principles with linear geodesics and instantaneous rate functions ℐ A   and ℐ S   defined by ℐ A ( φ ) = { ∫ 0 + ∞ I A ( φ ′ ( t ) ) d t if φ ∈ A λ + ∞ otherwise ,   with I A ( x ) = sup θ ∈ R { θ x − Λ A ( θ ) }   , the Legendre transform of Λ A   . We define I S   and ℐ S   in the same way.
We check (see [12] ) that f : C μ × C λ → R +   defined by f ( φ , ψ ) = sup t > 0 ( ψ ( t ) − φ ( t ) ) ,   is continuous on C μ × C λ   for the topology induced by the norm ( 16 ). Indeed f   is not continuous under the toplogy of uniform convergence on compact sets (example 5.2 [12] ).
Applying the contraction principle, we check that { w 1 / n , n ∈ Z }   satisfies a large deviations principle on R +   with rate function
I W ( q ) = inf { ∫ 0 ∞ I A , S ( φ ′ ( s ) ) d s | ( φ 1 , φ 2 ) ∈ A λ × A μ , f ( φ 1 , φ 2 ) = q }
= inf { ∫ 0 ∞ I A , S ( φ ′ ( s ) ) d s | ( φ 1 , φ 2 ) ∈ A λ × A μ , sup t > 0 ( φ 2 ( t ) − φ 1 ( t ) ) = q } ,
where I A , S ( φ ′ ( s ) ) = I A ( φ 1 ′ ( s ) ) + I S ( φ 2 ′ ( s ) )   . Combining this with Proposition  4.1 , we have
Corollary 6.3. The solution of the following optimization problem { Minimizing ∫ 0 ∞ I A , S ( φ ′ ( s ) ) d s pour φ = ( φ 1 , φ 2 ) ∈ A λ × A μ subject to sup t > 0 ( φ 2 ( t ) − φ 1 ( t ) ) = q   is given by I W ( q ) = δ q   where δ   is defined in ( 14 ).
In the following paragraph we make use of the same techniques to give large deviations principles for the output variables
d n = a n + w n + 1 − w n + s n + 1 − s n , r n = s n − w n + 1 + w n . (17)
We define D = { D n , n ∈ N }   and R = { R n , n ∈ N }   by D n = ∑ i = 1 n d − i , R n = ∑ i = 1 n r − i .   Let D ~ n   and R ~ n   be their polygonal approximations in n   . Under ( i )   , ( i i )   and by Loynes scheme [16] , wee check that ( D ~ n , R ~ n ) ∈ C λ × C μ .  

6.1 Optimization problem

To make the proof as clear as possible, we introduce a new variable b n = a n + w n + 1 − w n ,   which stands, in a queueing context, for the time between instants of beginning of services of customers n   and n + 1   . Let B = { B n , n ∈ N }   defined by B n = ∑ i = 1 n b − i   and B ~ n   its polygonal approximation in n   then B ~ n ∈ C λ   . Under ( i )   , we have
Lemma 6.4. for 0 ≤ t ≤ 1   fixed, the sequences { D ~ n ( t ) , n ∈ N * }   and { B ~ n ( t ) , n ∈ N * }   are exponentially equivalent.
  • Proof. Let γ > 0   ,
    P ( sup 0 ≤ t ≤ 1 | D ~ n ( t ) − B ~ n ( t ) | > γ ) ≤ P ( sup 0 ≤ k ≤ n | s − k − s 0 | > n γ )
    ≤ ∑ k = 0 n P ( | s − k − s 0 | > n γ )
    ≤ e − γ ν n ∑ k = 0 n E e γ | s − k − s 0 | ≤ ( n + 1 ) e − γ ν n e 2 Λ S ( γ ) .
    Since lim n → ∞ log ( ( n + 1 ) e − γ ν n ) = − ∞   and thanks to assumption ( i )   ( Λ S ( γ ) < ∞   for γ   close to 0   ), we are done.
Thus if one of the sequences { D ~ n ( t ) , n ∈ N * }   and { B ~ n ( t ) , n ∈ N * }   satisfies a large deviation principle then the other too and and they have the same rate function. Since the expression of B ~ n   (in terms of the input variables) is easier than the one of D ~ n   , we concentrate on B ~ n   and R ~ n   . In fact,
Lemma 6.5. The sequences B ~ n ( t )   and R ~ n ( t )   satisfy
B ~ n ( t ) = A ~ n ( t ) + sup s > 0 { S ~ n ( s ) − A ~ n ( s ) } − sup s > t { ( S ~ n ( s ) − S ~ n ( t ) ) − ( A ~ n ( s ) − A ~ n ( t ) ) }
R ~ n ( t ) = S ~ n ( t ) − sup s > 0 { S ~ n ( s ) − A ~ n ( s ) } + sup s > t { ( S ~ n ( s ) − S ~ n ( t ) ) − ( A ~ n ( s ) − A ~ n ( t ) ) }
  • Proof. We check the result for B ~ n ( t )   , the proof goes along the same arguments for R ~ n ( t )   . Since B ~ n ( t )   is a linear interpolation of B ⌊ n t ⌋ / n   , we will prove the result for B ⌊ n t ⌋   . First, we check that B ⌊ n t ⌋ = A ⌊ n t ⌋ + w 0 − w − ⌊ n t ⌋ .   However, we have w 0 = sup s > 0 { S ~ n ( s ) − A ~ n ( s ) }   then w − ⌊ n t ⌋ = sup s > t { ( S ~ n ( s ) − S ~ n ( t ) ) − ( A ~ n ( s ) − A ~ n ( t ) ) } .  
Theorem 6.6. Under assumptions ( i )   and ( i i )   , the sequence { ( D n n , R n n , w 0 n ) , n ∈ N * }   satisfies a large deviations principle on R + 3   with rate function
J ( x 1 , x 2 , w ) = inf { δ ( w − x 1 + x 2 ) + I A , S ( x 2 , x 1 ) ; inf C g ( q , τ , v 1 , v 2 ) } , (18)
where g ( q , τ , v 1 , v 2 ) = τ I A , S ( x 2 − v 2 τ , x 2 − v 2 + w τ ) + ( 1 − τ ) I A , S ( v 1 1 − τ , v 2 − q 1 − τ ) + δ q ,   with δ = inf 0 < a < s I A ( a ) + I S ( s ) s − a   and C = { ( q , τ , v 1 , v 2 ) | q ≥ 0 , 0 ≤ τ ≤ 1 , x 2 − v 2 + w = x 1 − v 1 + q }   .
  • Proof. By Loynes [16] and lemma  6.5 , we check that ( B ~ n , R ~ n , w 0 n )   = Φ ( A ~ n , S ~ n )   with Φ : C λ × C μ → C λ × C μ × R + ,   where Φ = ( Φ 1 , Φ 2 , Φ 3 )   and φ = ( φ 1 , φ 2 ) ∈ C λ × C μ   , we have
    Φ 1 ( φ ) ( t ) = φ 1 ( t ) + sup s > 0 { φ 2 ( s ) − φ 1 ( s ) } − sup s > t { ( φ 2 ( s ) − φ 2 ( t ) ) − ( φ 1 ( s ) − φ 1 ( t ) ) }
    Φ 2 ( φ ) ( t ) = φ 2 ( t ) − sup s > 0 { φ 2 ( s ) − φ 1 ( s ) } + sup s > t { ( φ 2 ( s ) − φ 2 ( t ) ) − ( φ 1 ( s ) − φ 1 ( t ) ) }
    Φ 3 ( φ ) ( t ) = sup s > 0 { φ 2 ( s ) − φ 1 ( s ) } . (19)
    Applying the contraction principle, the sequence { ( B ~ n , R ~ n , w 0 / n ) , n ∈ N * }   satisfies a large deviations principle with rate function J ( ψ 1 , ψ 2 , w ) = inf { ∫ 0 ∞ I A , S ( φ 1 ′ ( s ) , φ 2 ′ ( s ) ) d s | Φ ( φ 1 , φ 2 ) = ( ψ 1 , ψ 2 , w ) } .   This variational is hard to solve in a general setting, we restrict ourselves to t = 1   . By the law of large numbers, { ( B ~ n ( 1 ) , R ~ n ( 1 ) ) , n ∈ N * } = { ( B n n , R n n ) , n ∈ N * }   converges to the mean values of the output variables, whereas large deviations principle give the fluctuations around these values. The sequence { ( B n n , R n n , w 0 / n ) , n ∈ N * }   satisfies principle with rate function
    J ( x 1 , x 2 , w ) = inf { ∫ 0 ∞ I A , S ( φ 1 ′ ( s ) , φ 2 ′ ( s ) ) d s | [ Φ ( φ 1 , φ 2 ) ] ( 1 ) = ( x 1 , x 2 , w ) } . (20)
    We introduce the variables q 0   and q 1   given by
    q 0 = sup s > 0 { φ 2 ( s ) − φ 1 ( s ) }
    q 1 = sup s > 1 { ( φ 2 ( s ) − φ 2 ( 1 ) ) − ( φ 1 ( s ) − φ 1 ( 1 ) ) } .
    We rewrite ( 19 ) as follows x 1 = φ 1 ( 1 ) + q 0 − q 1 , x 2 = φ 2 ( 1 ) − q 0 + q 1 , w = q 0 .   To solve this variational problem we condition on the value of q 1   to be equal to q   . By the stability condition λ < μ   , we check that q   is finite. Then J ( x 1 , x 2 , w )   is the solution of the following optimization problem
    Minimize ∫ 0 1 I A , S ( φ ′ ( s ) ) d s + ∫ 1 ∞ I A , S ( φ ′ ( s ) ) d s over φ ∈ A λ × A μ , q ≥ 0
    subject to q 1 = q , x 1 = φ 1 ( 1 ) + q 0 − q 1 , x 2 = φ 2 ( 1 ) − q 0 + q 1 , w = q 0 ,
    where φ = ( φ 1 ( s ) , φ 2 ( s ) )   and I A , S ( φ ′ ( s ) ) = I A ( φ 1 ′ ( s ) ) + I S ( φ 2 ′ ( s ) )   .
    Using the auxiliary variable q   allows the decomposition of the initial optimization problem into two minimization problems on s ∈ [ 0 , 1 ]   and s > 1   coupled through q   . More precisely, we suppose the variables x 1   , x 2   and w = q 0   given, if we fix q   equal q 1   , then φ 1 ( 1 )   and φ 2 ( 1 )   are fixed. For s > 1   , the only constraint on φ 1   and φ 2   is q 1 = q   . Consequently, the first minimization consists of Minimizing ∫ 1 ∞ I A , S ( φ 1 ′ ( s ) , φ 2 ′ ( s ) ) d s , subject to q 1 = q .   The second minimization consists of
    Minimizing ∫ 0 1 I A , S ( φ 1 ′ ( s ) , φ 2 ′ ( s ) ) d s
    subject to x 1 = φ 1 ( 1 ) + q 0 − q 1 , x 2 = φ 2 ( 1 ) − q 0 + q 1 , w = q 0 ,
    knowing q 1 = q   . In both cases the minimization is for φ ∈ A λ × A μ   .
    For the first problem, let ψ ∈ A λ × A μ   with ψ i ( s − 1 ) = φ i ( s ) − φ i ( 1 )   , s ≥ 1 , i = 1 , 2   . By lemma  6.3 , this optimization gives the rate function associated with w 0   given in  4.1 and the minimum is δ q   where δ = inf a < s I A , S ( a , s ) s − a   .
    Hence, to determine J ( x 1 , x 2 , w )   it remains to
    Minimize ∫ 0 1 I A ( φ 1 ′ ( s ) ) + I S ( φ 2 ′ ( s ) ) d s + δ q , (21)
    for ( φ 1 , φ 2 ) ∈ A λ × A μ   subject to { q ≥ 0 , w = sup s ≥ 0 { φ 2 ( s ) − φ 1 ( s ) } x 1 = φ 1 ( 1 ) + w − q x 2 = φ 2 ( 1 ) − w + q .  
    • ∙   Suppose sup s ≥ 0 { φ 2 ( s ) − φ 1 ( s ) } = sup s ≥ 1 { φ 2 ( s ) − φ 1 ( s ) }   , then w = q + φ 2 ( 1 ) − φ 2 ( 1 )   , i.e.
      x 1 = φ 2 ( 1 ) , x 2 = φ 1 ( 1 ) , q = w − x 1 + x 2 .   The optimisation problem ( 21 ) is fulfilled by linear functions φ 1   and φ 2   and we have δ ( w − x 1 + x 2 ) + I A ( x 2 ) + I S ( x 1 ) .  
    • ∙   If φ 2 ( s ) − φ 1 ( s )   reaches its maximum for τ ∈ [ 0 , 1 ]   then
      x 1 = − q + φ 1 ( 1 ) − φ 1 ( τ ) + φ 2 ( τ )
      x 2 = q + φ 2 ( 1 ) − φ 2 ( τ ) + φ 1 ( τ ) .
      We define y i = φ i ( τ ) τ   , z i = φ i ( 1 ) − φ i ( τ ) 1 − τ , i = 1 , 2   and χ ∈ A λ × A μ   , χ i ( t ) = { y i t if t ∈ ] 0 , τ ] y i τ + z i ( t − τ ) if t ∈ ] τ , 1 ] .   Using the convexity of I A   and I S   and Jensen's inequality, we have ∫ 0 1 I A , S ( χ 1 ′ ( s ) , χ 2 ′ ( s ) ) d s ≤ ∫ 0 1 I A , S ( φ 1 ′ ( s ) , φ 2 ′ ( s ) ) d s .   Since ∫ 0 1 I A , S ( χ 1 ′ ( s ) , χ 2 ′ ( s ) ) d s = τ I A , S ( y ) + ( 1 − τ ) I A , S ( z )   où y = ( y 1 , y 2 )   et z = ( z 1 , z 2 )   , it remains to minimize δ q + τ I A , S ( y ) + ( 1 − τ ) I A , S ( z ) ,   subject to { q ≥ 0 , y 1 ≥ y 2 x 1 = − q + ( 1 − τ ) z 1 + τ y 2 x 2 = q + ( 1 − τ ) z 2 ≤ ( 1 − τ ) z 1 q + ( 1 − τ ) z 2 ≤ ( 1 − τ ) z 1 .   Let v 1 = ( 1 − τ ) z 1   and v 2 = ( 1 − τ ) z 2 + q   , we check that y 1 = x 2 − v 2 τ   , y 2 = w + x 2 − v 2 τ   and J ( x 1 , x 2 , w ) = inf { δ ( w − x 1 + x 2 ) + I A , S ( x 2 , x 1 ) , inf C g ( q , τ , v 1 , v 2 ) } ,   g   et C   defined in Theorem  6.6 .
Let us give an interpretation of this result in a queueing context. Indeed the most likely ways to get departures with mean x 1   and an average time spent at the back of queue equals to w 2   , and an average waiting time w   is whether
  • ∙ all customers belong to the same busy period (the system is never empty). Thus the mean of the departures is equal to the mean of the services and the average time spent at the very back of the queue is equal to the mean of the arrivals,
  • ∙ or let ( q , τ , v 1 , v 2 ) ∈ C   the variables where g   reaches its minimum. Then the customer − n τ   finds the system empty, and the optimal path splits into two periods. Customer − n   waits n q   time before starting its service. During the first period the average of arrivals and services are x 2 − v 2 τ   and x 2 − v 2 + w τ   and it consists of n τ   customers. During the second period the mean of services is v 2 − q 1 − τ   and the arrivals occurs with mean v 1 1 − τ   .
The equation ( 18 ) determines the rate functions of the output variables in terms of those of the input variables. A natural question is when these functions are equal. More precisely, when do we have ( I D , I R ) = ( I A , I S )   ? We start with an example which translates the result stated in [7] in terms of large deviations.

Example: the M/M/1 queue

Suppose that { a n , n ∈ Z }   and { s n , n ∈ Z }   are i.i.d. mutually independent and for t ≥ 0   , P ( a 0 > t ) = e − λ t , P ( s 0 > t ) = e − μ t .   For θ < λ < μ   , Λ A ( θ ) = log ( λ λ − θ ) , Λ S ( θ ) = log ( μ μ − θ ) .   Since δ = sup { θ > 0 , Λ S ( θ ) + Λ A ( − θ ) < 0 }   , we check that δ = μ − λ   . Moreover we have I A ( a ) = λ a − log ( λ a ) − 1 , I S ( s ) = μ s − log ( μ s ) − 1 .   Resolving the above optimization problem, we have
J ( x 1 , x 2 , w ) = λ x 1 − log ( λ x 1 ) − 1 + μ x 2 − log ( μ x 2 ) − 1 + ( μ − λ ) w
= I A , S ( x 1 , x 2 ) + δ w .

6.2 Existence of fixed points

Suppose { a n , n ∈ Z }   and { s n , n ∈ Z }   i.i.d., mutually independent with mean 1 / λ   and 1 / μ   .
They satisfy large deviations principles with rate functions I A   and I S   differentiable on R +   . Let β > 0   such that
I S ′ ( x ) − I A ′ ( x ) = β , ∀ x ∈ R + . (22)
We can rewrite this relation in the following which will be useful for future analysis
I A ( x ) − I A ( y ) = I S ( x ) − I S ( y ) − β ( x − y ) , ∀ ( x , y ) ∈ ( R + ) 2 . (23)
Before stating the fixed point result for the Queue/Store operator for the rate functions, we give an interpretation of the relations ( 22 ) and ( 23 ) in terms of exponential tilting of measures.
Definition 6.7. Let β > 0   , we say that a measure ν ′   is the β   -exponentially-tilted measure of a given measure ν   if for all x ∈ R   ,
d ν ′ d ν ( x ) = e β x ∫ e β x d ν ( x ) , (24)
where ( d ν ′ / d ν ) ( x )   denotes the Radon-Nikodym derivative of ν ′   with respect to ν   .
Proposition 6.8. Suppose { a n , n ∈ Z }   and { s n , n ∈ Z }   satisfies relation ( 22 ) or ( 23 ), with marginals ν A   and ν S   . Then ν A   is the β   -exponentially-tilted function of ν S   .
  • Proof. Recall that I A ( 1 / λ ) = 0   . We check that
    Λ A ( θ ) = sup x ∈ R [ θ x − I A ( x ) ] = sup x ∈ R [ θ x − I S ( x ) + I S ( 1 / λ ) + β ( x − 1 / λ ) ]
    = sup x ∈ R [ ( θ + β ) x − I S ( x ) ] − [ β λ − I S ( 1 / λ ) ]
    = Λ S ( θ + β ) − Λ S ( β ) . (25)
    Taking exponentials in both sides, we have ∫ R + e θ x d ν A ( x ) = ∫ R + e ( θ + β ) x d ν S ( x ) ∫ R + e β x d ν S ( x ) .  
Lemma 6.9. Let { a n , n ∈ Z }   and { s n , n ∈ Z }   satisfying assumptions ( i )   and ( i i )   , then the tilt coefficient β   is given by β = sup { θ : Λ S ( θ ) + Λ A ( − θ ) ≤ 0 } .  
  • Proof. Let θ = − β   in ( 25 ), we have Λ A ( − β ) = Λ S ( 0 ) − Λ S ( β ) .   Since Λ S ( 0 ) = 0   , we obtain Λ A ( − β ) + Λ S ( β ) = 0   . Thanks to ( 14 ), we have β ≤ sup { θ ≥ 0 , Λ S ( θ ) + Λ A ( − θ ) ≤ 0 } = δ .   The function G ( θ ) = Λ S ( θ ) + Λ A ( − θ )   is convex with G ( 0 ) = 0   . Moreover, by assumption ( i i )   , G ′ ( 0 ) = Λ S ′ ( 0 ) − Λ A ′ ( 0 ) < 0 ,   i.e. G   is equal to zero twice on [ 0 , β ]   , at 0   and β   , than β = sup { θ ≥ 0 , Λ S ( θ ) + Λ A ( − θ ) ≤ 0 } = δ .  
Theorem 6.10. Let δ > 0   and the sequences { a n , n ∈ Z }   and { s n , n ∈ Z }   the input variables of the model with ν A   the δ   -tilted measure of ν S   (or ν S   the ( − δ )   -tilted measure of ν A   ). Then the sequence { ( D n n , R n n , w 0 / n ) , n ∈ N * }   satisfies a large deviations principle on R + 3   with rate function
J ( x 1 , x 2 , w ) = δ w + I A , S ( x 1 , x 2 ) . (26)
Moreover, we have I D = I A and I R = I S .  
  • Proof. By Theorem  6.6 , the sequence { ( D ~ n ( 1 ) , R ~ n ( 1 ) , w 1 / n ) , n ∈ N * }   satisfies a large deviations principle on R + 3   with rate function J ( x 1 , x 2 , w ) = inf { δ ( w − x 1 + x 2 ) + I A , S ( x 2 , x 1 ) ; inf C g ( q , τ , v 1 , v 2 ) } ,   We start by the first term of this optimization problem, i.e.
    x 1 = φ 2 ( 1 ) , x 2 = φ 2 ( 1 ) q = w − x 1 + x 2 .   We have w = x 1 − x 2 + q   , and thanks to ( 23 ),
    δ ( w − x 1 + x 2 ) + I A , S ( x 2 , x 1 ) = δ ( w − x 1 + x 2 ) + I A , S ( x 1 , x 2 ) + δ ( x 1 − x 2 )
    = δ w + I A , S ( x 1 , x 2 ) .
    For the second term, let ( q , τ , v 1 , v 2 ) ∈ C   ,
    • ∙   If v 1 = v 2   , from the convexity property, we have
      g ( q , τ , v 1 , v 2 ) = δ q + τ I A , S ( x 2 − v 2 τ , x 2 − v 2 + w τ ) + ( 1 − τ ) I A , S ( v 2 1 − τ , v 2 − q 1 − τ )
      ≥ δ q + I A , S ( x 2 , x 2 + w − q ) = δ w + I A , S ( x 1 , x 2 ) .
    • ∙   If v 1 > v 2   , then I A , S ( x 2 − v 2 τ , x 2 − v 2 + w τ ) = I A , S ( x 2 − v 2 + w τ , x 2 − v 2 τ ) + δ w τ   Notice that I S ( v 2 − q 1 − τ ) = I S ( v 2 1 − τ ) + I A ( v 2 − q 1 − τ ) − I A ( v 2 1 − τ ) − δ q 1 − τ .   Since I A   is convex and v 1 ≥ v 2   , we have I A ( v 2 − q 1 − τ ) − I A ( v 2 1 − τ ) ≥ I A ( v 1 − q 1 − τ ) − I A ( v 1 1 − τ ) .   Thus, I S ( v 2 − q 1 − τ ) + I A ( v 1 1 − τ ) ≥ I S ( v 2 1 − τ ) + I A ( v 1 − q 1 − τ ) − δ q 1 − τ .   Since I A   and I S   are convex and x 2 − v 2 + w + v 1 − q = x 1   , we have g ( q ) ≥ δ w + I A , S ( x 1 , x 2 ) .   We conclude that J ( x 1 , x 2 , w ) = δ w + I A , S ( x 1 , x 2 )   .
In words the above theorem states that if the input variables satisfy large deviations principles with rate functions I A   and I S   with ν A   the δ   -tilted measure of ν S   , then the output variables satisfy large deviations principles with the same rate functions. References

  1. P.J. Burke. The output of a queueing system. Operations Research, 4:699–704, 1956.
  2. C.S. Chang. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Transactions on Automatic Control, 39:913–931, 1994.
  3. C. Courcoubetis, G. Kesidis, A Ridder, J Walrand, and R. Weber. Admission control and routing in ATM networks using inference from measured buffer occupancy. IEEE Transations on Communications, 43:1778–1784, 1995.
  4. A. Dembo and T. Zajic. Large deviations : from empirical mean and measure to partial processes. Stochastic Processes and their Applications, 57:197–224, 1995.
  5. A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Jones and Barlett, Boston, 1993.
  6. M. Draief, J. Mairesse, and N. O'Connell. Joint Burke's theorem and RSK representation for a queue and a store. In C. Banderier and C. Krattenthaler, editors, Discrete Random Walks, DRW'03, volume AC, pages 69–82, Institut Henri Poincaré, Paris, 2003.
  7. M. Draief, J. Mairesse, and N. O'Connell. Queues, Stores, and Tableaux. submitted, 2004.
  8. N. Duffield and N. O'Connell. Large deviations and overflow probabilities for the general single server queue, with applications. Mathematical Proceedings of the Cambridge Philosophical Society, 118(1), 1995.
  9. R. Gallager and B. Prabhakar. Entropy and the timing capacity of discrete queues. IEEE Transactions on Information Theory, 49(2):357–370, 2003.
  10. A. Ganesh and N. O'Connell. A large deviation principle with queueing applications. Stochastics and Stochastic Reports, 73(1-2):25–35, 2002.
  11. A. Ganesh, N. O'Connell, and B. Prabhakar. Invariant rate functions for discrete-time queues. Annals of Applied Probability, 13(2):446–474, 2003.
  12. A. Ganesh, N. O'Connell, and D. Wischik. Big Queues. Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2004.
  13. P. Glynn and W. Whitt. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. Journal of Applied Probability, 31A:131–156, 1994.
  14. F Kelly. Notes on effective bandwidth. In F. Kelly and I Ziedens, editors, Stochastic Networks, pages 141–168. Oxford University Press, 1996.
  15. F.P. Kelly. Effective bandwidths at multi-class queues. Queueing Systems Theory and Application, 9:5–15, 1991.
  16. R. Loynes. The stability of a queue with non-independent interarrival and service times. Mathematical Proceedings of the Cambridge Philosophical Society, 58:497–520, 1962.