Namespaces
Variants
Actions

Difference between revisions of "Queue with waiting and one service channel"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fix tex)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
q0768401.png
 +
$#A+1 = 293 n = 0
 +
$#C+1 = 293 : ~/encyclopedia/old_files/data/Q076/Q.0706840 Queue with waiting and one service channel,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''single-server queue''
 
''single-server queue''
  
 
A queue for which the algorithm provides for calls which are not served immediately (having found the system busy) to form a queue; in this connection the service of this call (or batch of calls) can begin only after the service of the previous call (or batch of calls, if the service is in batches) is complete. The basic definitions and notations are to be found in [[Queue|Queue]].
 
A queue for which the algorithm provides for calls which are not served immediately (having found the system busy) to form a queue; in this connection the service of this call (or batch of calls) can begin only after the service of the previous call (or batch of calls, if the service is in batches) is complete. The basic definitions and notations are to be found in [[Queue|Queue]].
  
The most natural characteristics of the state of a queueing system are the following: a) the waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768401.png" /> to the beginning of the service of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768402.png" />-th request, and the virtual waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768403.png" />, which is defined as the time necessary for the system to be free of the calls which arrived up to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768404.png" />; b) the queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768405.png" /> at the time of arrival of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768406.png" />-th call and the queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768407.png" /> at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768408.png" />.
+
The most natural characteristics of the state of a queueing system are the following: a) the waiting time $  w _ {n} $
 +
to the beginning of the service of the $  n $-th request, and the virtual waiting time $  w ( t) $,  
 +
which is defined as the time necessary for the system to be free of the calls which arrived up to time $  t $;  
 +
b) the queue length q _ {n} $
 +
at the time of arrival of the $  n $-th call and the queue length q ( t) $
 +
at time $  t $.
  
1) In the  "single"  case (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q0768409.png" />) the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684010.png" /> are connected by the recurrence relations
+
1) In the  "single"  case ( $  \nu _ {j}  ^ {e} \equiv 1 $)  
 +
the values $  w _ {n} $
 +
are connected by the recurrence relations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684011.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
w _ {n+1}  = \max ( 0 , w _ {n} + \xi _ {n} ) ,\ \
 +
\xi _ {n}  = \tau _ {n}  ^ {s} - \tau _ {n}  ^ {e} .
 +
$$
  
A queueing system in the  "multiple"  case, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684013.png" /> are different from one, may be described by the same type of equation (for the waiting time or queue length). For example, for the queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684014.png" /> one has the relation
+
A queueing system in the  "multiple"  case, when $  \nu _ {j}  ^ {e} $,  
 +
$  \nu _ {j}  ^ {s} $
 +
are different from one, may be described by the same type of equation (for the waiting time or queue length). For example, for the queue length q _ {n} $
 +
one has the relation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
q _ {n+1}  = \max ( 0 , q _ {n} + \nu _ {n}  ^ {e} - \beta _ {n} ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684016.png" /> is the number of calls which can be served during a time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684017.png" /> under continuous operation of the system. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684019.png" />, then the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684020.png" /> may be found from the relations
+
where $  \beta _ {n} $
 +
is the number of calls which can be served during a time $  \tau _ {n}  ^ {e} $
 +
under continuous operation of the system. If $  \{ \tau _ {j}  ^ {s} \} \in E $,  
 +
$  \{ \nu _ {j}  ^ {s} \} \in G _ {I} $,  
 +
then the distribution of $  \beta _ {n} $
 +
may be found from the relations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684021.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} _ {\tau _ {n}  ^ {e} } e ^ {i \lambda \beta _ {n} }  = \
 +
\mathop{\rm exp}
 +
\left [
 +
\tau _ {n}  ^ {e} \alpha
 +
\sum _ { k=1 } ^  \infty 
 +
( e ^ {i \lambda k } - 1 )
 +
{\mathsf P} \{ \nu _ {j}  ^ {s} = k \} \right ] ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684022.png" /> is the exponent of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684023.png" />.
+
where $  \alpha $
 +
is the exponent of the distribution of $  \tau _ {j}  ^ {s} $.
  
If one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684025.png" />, then the solution of (1) has the form
+
If one puts $  X _ {0} = 0 $,  
 +
$  X _ {n} = \xi _ {1} + \dots + \xi _ {n} $,  
 +
then the solution of (1) has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684026.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
w _ {n+1}  = X _ {n} -
 +
\min ( - w _ {1} , X _ {1} \dots X _ {n} ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684027.png" /></td> </tr></table>
+
$$
 +
= \
 +
\max ( X _ {n} + w _ {1} , X _ {n} - X _ {1} \dots X _ {n} - X _ {n-1} , 0 ) .
 +
$$
  
Hence it follows that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684029.png" /> for any fixed interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684030.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684031.png" />, then there is a limit distribution for the waiting time:
+
Hence it follows that if $  \{ \xi _ {n} \} \in G _ {S} $
 +
and $  {\mathsf P} \{ X _ {n} \in \Delta \} \rightarrow 0 $
 +
for any fixed interval $  \Delta $
 +
as $  n \rightarrow \infty $,  
 +
then there is a limit distribution for the waiting time:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684032.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ w _ {n} > x \}  = {\mathsf P} \{ Y > x \} ,
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684033.png" /></td> </tr></table>
+
$$
 +
= \sup _ {k \geq  0 }  Y _ {k} ,\ \
 +
Y _ {k}  = \xi _ {-k} + \dots + \xi _ {-1} ,\  Y _ {0}  = 0 .
 +
$$
  
Here the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684034.png" /> are the elements of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684035.png" /> which extends <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684036.png" /> to a sequence which is stationary on the whole line. In what follows it will be assumed that such an extension has been made for all control sequences.
+
Here the variables $  \xi _ {-k} $
 +
are the elements of the sequence $  \{ \xi _ {n} \} _ {n = - \infty }  ^  \infty  $
 +
which extends $  \{ \xi _ {n} \} _ {n=1}  ^  \infty  $
 +
to a sequence which is stationary on the whole line. In what follows it will be assumed that such an extension has been made for all control sequences.
  
 
The values
 
The values
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684037.png" /></td> </tr></table>
+
$$
 +
w  ^ {k}  = \sup
 +
( 0 , \xi _ {k} , \xi _ {k} + \xi _ {k-1} , \xi _ {k} +
 +
\xi _ {k-1} + \xi _ {k-2} ,\dots )
 +
$$
  
satisfy (1) and have a distribution coinciding with the limit distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684038.png" />. This is the stationary waiting time process.
+
satisfy (1) and have a distribution coinciding with the limit distribution of $  w _ {n} $.  
 +
This is the stationary waiting time process.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684039.png" /> be ergodic (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684040.png" /> with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684041.png" />). Then
+
Let $  \{ \xi _ {n} \} \in G _ {S} $
 +
be ergodic ( $  X _ {n} / n \rightarrow {\mathsf E} \xi _ {1} $
 +
with probability $  1 $).  
 +
Then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684042.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ Y < \infty \}  = \
 +
{\mathsf P} \{ w  ^ {k} < \infty \}  = 1
 +
$$
  
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684043.png" /> or if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684045.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684046.png" />. Otherwise
+
if $  {\mathsf E} \xi _ {k} < 0 $
 +
or if $  {\mathsf E} \xi _ {k} = 0 $
 +
and $  \xi _ {k} = \eta _ {k+1} - \eta _ {k} $,  
 +
where $  \{ \eta _ {k} \} \in G _ {S} $.  
 +
Otherwise
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684047.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ Y = \infty \}  = {\mathsf P} \{ w  ^ {k} = \infty \}  = 1 .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684048.png" />, then
+
If $  \{ \xi _ {n} \} \in G _ {I} $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684049.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ Y < \infty \}  = 1
 +
$$
  
if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684050.png" /> (the trivial case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684051.png" /> being excluded).
+
if and only if $  {\mathsf E} \xi _ {k} < 0 $(
 +
the trivial case $  \xi _ {k} = 0 $
 +
being excluded).
  
2) As already noted, another possible characteristic of the state of the system is the virtual waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684052.png" />. Roughly speaking, this is the time which the call arriving at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684053.png" /> would have to wait until the beginning of its service. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684054.png" /> be the sum of the service times of the calls which arrive in the system up to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684055.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684056.png" />. An analogue of (3) here is the relation
+
2) As already noted, another possible characteristic of the state of the system is the virtual waiting time $  w ( t) $.  
 +
Roughly speaking, this is the time which the call arriving at time $  t $
 +
would have to wait until the beginning of its service. Let $  S ( t) $
 +
be the sum of the service times of the calls which arrive in the system up to time $  t $,  
 +
and let $  X ( t) = S ( t) - t $.  
 +
An analogue of (3) here is the relation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684057.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
w ( t)  = X ( t) -
 +
\inf _ {0 \leq  u \leq  t } ( 0 , X ( u) ) .
 +
$$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684058.png" /> be the class of processes with stationary increments in the narrow sense and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684059.png" /> be the class of processes with independent increments (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684060.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684061.png" /> could here be narrower: for example, it can be supposed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684062.png" /> is the class of generalized Poisson processes with positive jumps and drift <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684063.png" />). If the process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684064.png" />, then it can be extended to a process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684065.png" /> given on the whole line and also in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684066.png" />. In this case
+
Let $  G _ {IS} $
 +
be the class of processes with stationary increments in the narrow sense and let $  G _ {II} $
 +
be the class of processes with independent increments ( $  G _ {II} $
 +
and $  G _ {IS} $
 +
could here be narrower: for example, it can be supposed that $  G _ {II} $
 +
is the class of generalized Poisson processes with positive jumps and drift $  - 1 $).  
 +
If the process $  \{ {X ( t) } : {t \geq  0 } \} \in G _ {IS} $,  
 +
then it can be extended to a process $  \{ {X ( t) } : {- \infty < t < \infty } \} $
 +
given on the whole line and also in $  G _ {IS} $.  
 +
In this case
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684067.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {t \rightarrow \infty }  {\mathsf P} \{ w ( t) > x \}  = \
 +
{\mathsf P} \{ \overline{Y}\; > x \}
 +
$$
  
 
exists, where
 
exists, where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684068.png" /></td> </tr></table>
+
$$
 +
\overline{Y}\; = \sup _ {u \geq  0 }  Y ( t) ,\ \
 +
Y ( t)  = X ( 0) - X (- t) .
 +
$$
  
 
If, in addition,
 
If, in addition,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684069.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} ( X ( 1) - X ( 0) )  = {\mathsf E} ( Y ( 1) - Y ( 0) )  = < 0 ,
 +
$$
  
 
then the distribution of the process
 
then the distribution of the process
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684070.png" /></td> </tr></table>
+
$$
 +
w _ {t} ( u)  = \{ {w ( t - u ) } : {u \geq  0 } \}
 +
$$
  
converges as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684071.png" /> to the distribution of the process
+
converges as $  t \rightarrow \infty $
 +
to the distribution of the process
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684072.png" /></td> </tr></table>
+
$$
 +
w  ^ {s} ( u)  = \sup _ {v \leq  u } ( X ( u) - X ( v) ) ,
 +
$$
  
 
which is the strictly stationary virtual waiting time process. Here convergence holds in the strong form:
 
which is the strictly stationary virtual waiting time process. Here convergence holds in the strong form:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684073.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ w _ {t} \in B \}  \rightarrow  {\mathsf P} \{ w  ^ {s} \in B \}
 +
$$
  
for any measurable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684074.png" />.
+
for any measurable $  B $.
  
Further, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684075.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684076.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684077.png" /> has a conditional renewal function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684078.png" />:
+
Further, if $  \{ X ( t) \} \in G _ {IS} $
 +
and $  a < 0 $,  
 +
then $  X ( t) $
 +
has a conditional renewal function $  H _ {0} ( x) $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684079.png" /></td> </tr></table>
+
$$
 +
H _ {0} ( x) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684080.png" /></td> </tr></table>
+
$$
 +
= \
 +
\int\limits _ { 0 } ^  \infty  {\mathsf P} \left \{ 0 \leq  X ( u) - X ( 0) < x : X
 +
( 0) = \inf _ {v \leq  0 }  X ( v) \right \}  d u  < \infty ;
 +
$$
  
 
here
 
here
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684081.png" /></td> </tr></table>
+
$$
 +
\left . \begin{array}{c}
 +
 
 +
{\mathsf P} \{ w  ^ {s} ( u) \geq  x \}  = - a
 +
 
 +
\frac{d H _ {0} ( x) }{dx}
 +
,
 +
\\
 +
 
 +
{\mathsf P} \{ w  ^ {s} ( t)  = 0 \}  = - a .
 +
\end{array}
 +
 
 +
\right \}
 +
$$
 +
 
 +
These formulas still hold when  $  \nu _ {j}  ^ {e} \neq 1 $.
 +
 
 +
For systems in which  $  \{ \tau _ {j}  ^ {s} - \tau _ {j}  ^ {e} \} \in G _ {I} $
 +
there are simple relations between the distributions of  $  w  ^ {k} $
 +
and  $  w  ^ {s} ( t) $.
 +
 
 +
3) Ergodic theorems for the queue length can be obtained with the help of the corresponding theorems for the waiting time. For example, let the sequence  $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {e} \} \in G _ {S} $
 +
be ergodic (metrically transitive). If, in addition,  $  {\mathsf E} ( \tau _ {j}  ^ {s} - \tau _ {j}  ^ {e} ) < 0 $,
 +
then there is a (stationary) limit distribution for  $  q _ {n} $
 +
such that
 +
 
 +
$$
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} > k \} \
 +
=  {\mathsf P} \{ w  ^ {0} > \tau _ {1}  ^ {e} + \dots +
 +
\tau _ {k}  ^ {e} \} .
 +
$$
 +
 
 +
If  $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,
 +
$  \{ \tau _ {j}  ^ {s} \} \in G _ {I} $
 +
and  $  \tau _ {j}  ^ {e} $
 +
has a non-lattice distribution, then
 +
 
 +
$$
 +
\lim\limits _ {\tau \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) > k + 1 \} \
 +
=  {\mathsf P} \{ w  ^ {0} > \tau _ {1}  ^ {e} + \dots + \tau _ {k}  ^ {e} + \gamma \} ,\  k \geq  0 ,
 +
$$
  
These formulas still hold when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684082.png" />.
+
$$
 +
\lim\limits _ {\tau \rightarrow 0 }  {\mathsf P} \{ q ( t) =
 +
0 \}  = -
 +
\frac{a}{ {\mathsf E} \tau  ^ {e} }
 +
,
 +
$$
  
For systems in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684083.png" /> there are simple relations between the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684085.png" />.
+
where all the components under the probability sign on the right-hand side are independent, and $  \gamma $
 +
has a density
  
3) Ergodic theorems for the queue length can be obtained with the help of the corresponding theorems for the waiting time. For example, let the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684086.png" /> be ergodic (metrically transitive). If, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684087.png" />, then there is a (stationary) limit distribution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684088.png" /> such that
+
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684089.png" /></td> </tr></table>
+
\frac{ {\mathsf P} \{ \tau _ {j}  ^ {e} > x \} }{ {\mathsf E} \tau  ^ {e} }
 +
,
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684090.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684091.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684092.png" /> has a non-lattice distribution, then
+
$$
 +
w  ^ {0}  = \sup ( 0 , \xi _ {0} , \xi _ {0} + \xi _ {-1}
 +
,\dots ) ,\  \xi _ {j}  = \tau _ {j}  ^ {s} - \tau _ {j}  ^ {e} .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684093.png" /></td> </tr></table>
+
If  $  \{ \tau _ {j}  ^ {e} \} \in E $,
 +
then the limit distributions of  $  q _ {n} $
 +
and  $  q ( t) $
 +
coincide.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684094.png" /></td> </tr></table>
+
4) If  $  \{ \tau _ {j}  ^ {e} \} \in E $,
 +
$  \{ \tau _ {j}  ^ {s} \} \in G _ {I} $(
 +
it is also supposed that  $  \nu _ {j}  ^ {e} \neq 1 $,
 +
$  \{ \nu _ {j}  ^ {e} \} \in G _ {I} $),
 +
then it is possible to obtain an exact formula for the limit distribution of  $  w ( t) $:
  
where all the components under the probability sign on the right-hand side are independent, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684095.png" /> has a density
+
$$
 +
{\mathsf P} \{ w ( t) < x \} \
 +
= {\mathsf P} \{ Y ( t) < x \} +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684096.png" /></td> </tr></table>
+
$$
 +
+
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684097.png" /></td> </tr></table>
+
\frac \partial {\partial  x }
 +
\int\limits _ { 0 } ^ { t }  {\mathsf E} \left (
 +
\frac{Y ( u) }{u}
 +
: \
 +
Y ( u) < 0 \right ) {\mathsf P} \{ Y ( t - u ) < x \}  d u ,
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684098.png" />, then the limit distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q07684099.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840100.png" /> coincide.
+
$$
 +
{\mathsf P} \{ w ( t) = 0 \}  = - {\mathsf E} \left (
 +
\frac{
 +
Y ( t) }{t}
 +
: Y ( t) < 0 \right ) .
 +
$$
  
4) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840101.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840102.png" /> (it is also supposed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840104.png" />), then it is possible to obtain an exact formula for the limit distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840105.png" />:
+
For  $  a < 0 $
 +
and  $  t \rightarrow \infty $
 +
there is the Khinchin–Pollaczek formula for the stationary distribution:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840106.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} e ^ {i \lambda w  ^ {s} ( u) } \
 +
=
 +
\frac{1 - \alpha {\mathsf E} \theta }{1 - \alpha
 +
\frac{\phi ( \lambda ) - 1 }{i \lambda }
 +
}
 +
,\ \
 +
\phi ( \lambda )  = {\mathsf E} e ^ {i \lambda \theta } ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840107.png" /></td> </tr></table>
+
where  $  \theta $
 +
is the jump of the process  $  X ( t) $(
 +
$  \theta = \tau _ {j}  ^ {s} $
 +
if  $  \nu _ {j}  ^ {e} \equiv 1 $)
 +
and  $  \alpha $
 +
is the exponent of the distribution of  $  \tau _ {j}  ^ {e} $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840108.png" /></td> </tr></table>
+
Let  $  T _ {j} $,
 +
$  j = 1 , 2 \dots $
 +
be the busy periods of the system (that is, the lengths of the time intervals during which  $  w ( t) > 0 $).  
 +
Then, for the systems considered,
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840110.png" /> there is the Khinchin–Pollaczek formula for the stationary distribution:
+
$$
 +
{\mathsf P} \{ T _ {j} \in ( u , u + d u ) \} \
 +
=
 +
\frac{1}{\alpha u }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840111.png" /></td> </tr></table>
+
{\mathsf P} \{ X ( u) \in ( 0 , d u ) \} .
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840112.png" /> is the jump of the process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840113.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840114.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840115.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840116.png" /> is the exponent of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840117.png" />.
+
5) For systems in which  $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} \in G _ {I} $(
 +
it is also assumed that  $  \nu _ {j}  ^ {e} \neq 1 $,
 +
$  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} , \nu _ {j}  ^ {e} \} \in G _ {I} $),
 +
the distribution of $  w  ^ {k} $
 +
coincides with the distribution of the variable
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840118.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840119.png" /> be the busy periods of the system (that is, the lengths of the time intervals during which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840120.png" />). Then, for the systems considered,
+
$$
 +
= \sup
 +
( 0 , \xi _ {1} , \xi _ {1} + \xi _ {2} ,\dots ) .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840121.png" /></td> </tr></table>
+
If the distribution of  $  \xi _ {j} $
 +
is known, then the distribution of  $  Y $
 +
can be found as follows. If  $  {\mathsf P} \{ Y < \infty \} = 1 $(
 +
this is always true if  $  {\mathsf E} \xi _ {j} < 0 $),
 +
then the factorization identity
  
5) For systems in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840122.png" /> (it is also assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840123.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840124.png" />), the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840125.png" /> coincides with the distribution of the variable
+
$$
 +
1 - {\mathsf E} e ^ {i \lambda \xi }  = ( 1 - p )
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840126.png" /></td> </tr></table>
+
\frac{1 - {\mathsf E} e ^ {i \lambda \chi } }{ {\mathsf E} e ^ {i \lambda Y } }
 +
,\ \
 +
\mathop{\rm Im}  \lambda = 0 ,
 +
$$
  
If the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840127.png" /> is known, then the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840128.png" /> can be found as follows. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840129.png" /> (this is always true if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840130.png" />), then the factorization identity
+
holds, where  $  p = {\mathsf P} \{ Y < 0 \} $
 +
and  $  \chi \leq  0 $
 +
is the size of the first non-positive sum among  $  \xi _ {1} , \xi _ {1} + \xi _ {2} ,\dots $.  
 +
This relation permits one to relate  $  {\mathsf E} e ^ {i \lambda Y } $
 +
to the ratio  $  w _ {+} ( \lambda ) / w _ {+} ( 0) $
 +
in any identity
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840131.png" /></td> </tr></table>
+
$$ \tag{5 }
 +
1 - {\mathsf E} e ^ {i \lambda \xi }  =
 +
\frac{w _ {-} ( \lambda ) }{w _ {+} ( \lambda ) }
 +
,\ \
 +
\mathop{\rm Im}  \lambda = 0 ,
 +
$$
  
holds, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840132.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840133.png" /> is the size of the first non-positive sum among <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840134.png" />. This relation permits one to relate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840135.png" /> to the ratio <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840136.png" /> in any identity
+
in which the functions  $  w _  \pm  ( \lambda ) $
 +
admit a representation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840137.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$
 +
w _  \pm  ( \lambda )  = \
 +
\int\limits _ { 0 } ^ {  \pm  \infty }
 +
e ^ {i \lambda t }  d V _  \pm  ( t)
 +
$$
  
in which the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840138.png" /> admit a representation
+
( $  V _  \pm  $
 +
are functions of bounded variation). Equality (5) provides the so-called  $  V $-
 +
factorization of the function  $  1 - {\mathsf E} e ^ {i \lambda \xi } $.  
 +
It explains the following cases, when it is possible to search for  $  {\mathsf E} e ^ {i \lambda Y } $
 +
explicitly.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840139.png" /></td> </tr></table>
+
Assume that  $  - \infty < {\mathsf E} \xi < 0 $
 +
and put
  
(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840140.png" /> are functions of bounded variation). Equality (5) provides the so-called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840142.png" />-factorization of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840143.png" />. It explains the following cases, when it is possible to search for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840144.png" /> explicitly.
+
$$
 +
f ( \lambda )  = {\mathsf E} e ^ {i \lambda \xi } ,\ \
 +
f _ {+} ( \lambda )  = e ^ {i \lambda \tau  ^ {s} } ,\ \
 +
f _ {-} ( \lambda ) = e ^ {- i \lambda \tau  ^ {e} } ,
 +
$$
  
Assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840145.png" /> and put
+
so that $  f ( \lambda ) = f _ {+} ( \lambda ) f _ {-} ( \lambda ) $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840146.png" /></td> </tr></table>
+
A) If  $  f _ {+} $
 +
is a rational function,  $  f _ {+} = P _ {m} / Q _ {n} $,
 +
where  $  P _ {m} $
 +
and  $  Q _ {n} $
 +
are polynomials of degree  $  m $
 +
and  $  n $,
 +
respectively, then in the domain  $  \mathop{\rm Im}  \lambda < 0 $
 +
the function  $  ( 1 - f  ) Q _ {n} $
 +
has exactly  $  n $
 +
zeros  $  \lambda _ {1} \dots \lambda _ {n} $,
 +
and
  
so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840147.png" />.
+
$$
 +
w _ {+} ( \lambda )  = \
  
A) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840148.png" /> is a rational function, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840149.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840150.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840151.png" /> are polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840152.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840153.png" />, respectively, then in the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840154.png" /> the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840155.png" /> has exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840156.png" /> zeros <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840157.png" />, and
+
\frac{Q _ {n} ( \lambda ) }{\prod _ { k=1} ^ { n }  ( \lambda - \lambda _ {k} ) }
 +
,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840158.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} e ^ {i \lambda Y }  =
 +
\frac{w _ {+} ( \lambda ) }{w _ {+} ( 0) }
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840159.png" /></td> </tr></table>
+
This means that if the distribution of  $  \tau  ^ {s} $
 +
can be represented as
  
This means that if the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840160.png" /> can be represented as
+
$$
 +
{\mathsf P} \{ \tau  ^ {s} > x \}  = \
 +
\sum _ { k }
 +
P _ {k} ( x) e ^ {- \alpha _ {k} x } ,\ \
 +
\mathop{\rm Re}  \alpha _ {k} > 0 ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840161.png" /></td> </tr></table>
+
where  $  P _ {k} ( x) $
 +
is a polynomial, then the same type of representation (for other  $  \alpha _ {k} $
 +
and  $  P _ {k} $,
 +
determined by  $  \lambda _ {1} \dots \lambda _ {n} $)
 +
also holds for  $  {\mathsf P} \{ Y < x \} $.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840162.png" /> is a polynomial, then the same type of representation (for other <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840163.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840164.png" />, determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840165.png" />) also holds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840166.png" />.
+
B) If  $  f _ {-} = P _ {m} / Q _ {n} $
 +
is a rational function, then in the domain  $  \mathop{\rm Im}  \lambda > 0 $
 +
the function  $  ( 1 - f  ) Q _ {n} $
 +
has  $  n- 1 $
 +
zeros  $  \lambda _ {1} \dots \lambda _ {n-1} $,  
 +
and
  
B) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840167.png" /> is a rational function, then in the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840168.png" /> the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840169.png" /> has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840170.png" /> zeros <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840171.png" />, and
+
$$
 +
w _ {+} ( \lambda ) = \
 +
i \lambda
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840172.png" /></td> </tr></table>
+
\frac{\prod _ { k=1 } ^ { n- 1} 
 +
( \lambda - \lambda _ {k} ) }{Q _ {n} ( \lambda ) ( 1 - f ( \lambda ) ) }
 +
.
 +
$$
  
In addition to these formulas, giving explicit expressions for the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840173.png" />, it is also possible, in a broad class of cases, to describe the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840174.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840175.png" />. Namely, if
+
In addition to these formulas, giving explicit expressions for the distribution of $  Y $,  
 +
it is also possible, in a broad class of cases, to describe the asymptotic behaviour of $  {\mathsf P} \{ Y > x \} $
 +
as $  x \rightarrow \infty $.  
 +
Namely, if
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840176.png" /></td> </tr></table>
+
$$
 +
\gamma  = \
 +
\sup
 +
( \mu : {\mathsf E} e ^ {\mu \xi } \langle  \infty )  \rangle  0
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840177.png" />, then there is a unique root of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840178.png" />. In this case, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840179.png" />,
+
and $  {\mathsf E} e ^ {\gamma \xi } > 1 $,  
 +
then there is a unique root of the equation $  {\mathsf E} e ^ {q \xi } = 1 $.  
 +
In this case, as $  x \rightarrow \infty $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840180.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ Y > x \}  = \
 +
c _ {1} e  ^ {-qx} ( 1+ o ( 1) ) .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840181.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840182.png" />, then
+
If $  \gamma = 0 $,  
 +
$  - \infty < {\mathsf E} \xi < 0 $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840183.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ Y > x \}  = \
 +
c _ {2} \int\limits _ { x } ^  \infty 
 +
{\mathsf P} \{ \xi > t \}  dt  ( 1 + o ( 1) ) .
 +
$$
  
The constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840184.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840185.png" /> have been found explicitly.
+
The constants $  c _ {1} $
 +
and $  c _ {2} $
 +
have been found explicitly.
  
Results similar to those discussed in parts 2)–5) are true even for discrete-time systems, when the time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840186.png" /> and the random variables of the control sequences take only integer values.
+
Results similar to those discussed in parts 2)–5) are true even for discrete-time systems, when the time $  t $
 +
and the random variables of the control sequences take only integer values.
  
6) Stability theorems investigate conditions under which a small change in the finite-dimensional distributions of the control sequences leads to a small change in the stationary distribution of the waiting time or queue length. The importance of stability for queues is explained by the fact that in real problems various assumptions are usually made on the nature of the control sequences (for example, it is assumed that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840187.png" /> are independent or that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840188.png" /> are exponentially distributed), whereas, in reality, these assumptions are only approximately satisfied. The question is whether the solution of such  "idealized"  problems is close to the solution of the actual problem.
+
6) Stability theorems investigate conditions under which a small change in the finite-dimensional distributions of the control sequences leads to a small change in the stationary distribution of the waiting time or queue length. The importance of stability for queues is explained by the fact that in real problems various assumptions are usually made on the nature of the control sequences (for example, it is assumed that the $  \xi _ {j} $
 +
are independent or that the $  \tau _ {j}  ^ {e} $
 +
are exponentially distributed), whereas, in reality, these assumptions are only approximately satisfied. The question is whether the solution of such  "idealized"  problems is close to the solution of the actual problem.
  
To obtain a precise statement of the problem, triangular arrays are used, where equation (1) is controlled by stationary sequences (triangular arrays) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840189.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840190.png" />. In addition, one considers a stationary sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840191.png" /> and puts
+
To obtain a precise statement of the problem, triangular arrays are used, where equation (1) is controlled by stationary sequences (triangular arrays) $  \xi  ^ {( n)} = \{ {\xi _ {j}  ^ {( n)} } : {- \infty < j < \infty } \} $,  
 +
$  n = 1 , 2 ,\dots $.  
 +
In addition, one considers a stationary sequence $  \xi = \{ {\xi _ {j} } : {- \infty < j < \infty } \} $
 +
and puts
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840192.png" /></td> </tr></table>
+
$$
 +
Y  ^ {( n)}  = \
 +
\sup _ {k \geq  0 }  Y _ {k}  ^ {( n)} ,\ \
 +
Y _ {k}  ^ {( n)}  = \sum _ { j=1 } ^ { n }  \xi _ {-j}  ^ {( n)} .
 +
$$
  
 
The answer to the question posed above is given by the following result.
 
The answer to the question posed above is given by the following result.
  
Let the finite-dimensional distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840193.png" /> converge weakly to the corresponding distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840194.png" />, which is assumed to be ergodic, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840195.png" />. Then for the weak convergence
+
Let the finite-dimensional distributions of $  \xi  ^ {( n)} $
 +
converge weakly to the corresponding distributions of $  \xi $,  
 +
which is assumed to be ergodic, and let $  {\mathsf E} \xi _ {j} < 0 $.  
 +
Then for the weak convergence
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840196.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
$$ \tag{6 }
 +
{\mathsf P} \{ Y  ^ {( n)} < t \}  \Rightarrow  {\mathsf P} \{ Y < t \}
 +
$$
  
 
(that is, for the convergence of the distributions of the stationary waiting times) it is sufficient that
 
(that is, for the convergence of the distributions of the stationary waiting times) it is sufficient that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840197.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} ( \xi _ {j}  ^ {( n)} : \xi _ {j}  ^ {( n)} \geq  0 )  \rightarrow \
 +
{\mathsf E} ( \xi _ {j} : \xi _ {j} \geq  0 ) .
 +
$$
  
 
The stated condition for convergence is almost necessary.
 
The stated condition for convergence is almost necessary.
  
If the control sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840198.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840199.png" /> are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840200.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840201.png" /> are independent and the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840202.png" /> converge weakly to the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840203.png" />, then for (6) it is sufficient that
+
If the control sequences $  \{ \tau _ {j} ^ {( n) e } , \tau _ {j} ^ {( n) s } \} $
 +
and $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} $
 +
are such that $  \tau _ {j} ^ {( n) e } $
 +
and $  \tau _ {j} ^ {( n) s } $
 +
are independent and the distributions of $  \{ \tau _ {j} ^ {( n) e } , \tau _ {j} ^ {( n) s } \} $
 +
converge weakly to the distributions of $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} $,  
 +
then for (6) it is sufficient that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840204.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} \tau _ {j} ^ {( n) s }  \rightarrow \
 +
{\mathsf E} \tau _ {j}  ^ {s} .
 +
$$
  
The situation is similar for the stationary distribution of the virtual waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840205.png" />. If the finite-dimensional distributions of the processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840206.png" /> converge to the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840207.png" /> and if the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840208.png" /> is ergodic, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840209.png" />, then for the convergence of the distributions of
+
The situation is similar for the stationary distribution of the virtual waiting time $  w  ^ {s} ( t) $.  
 +
If the finite-dimensional distributions of the processes $  Y  ^ {( n)} ( t) \in G _ {IS} $
 +
converge to the distributions of $  Y ( t) \in G _ {IS} $
 +
and if the sequence $  \{ \eta _ {k} = Y ( k+ 1) - Y ( k) \} $
 +
is ergodic, $  {\mathsf E} \eta _ {k} = a < 0 $,  
 +
then for the convergence of the distributions of
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840210.png" /></td> </tr></table>
+
$$
 +
\sup _ {t \geq  0 }  Y  ^ {(n)} ( t) \ \
 +
\textrm{ and } \ \
 +
\sup _ {t \geq  0 }  Y ( t)
 +
$$
  
 
it is sufficient that
 
it is sufficient that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840211.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} \{ {\eta _ {k}  ^ {(n)} } : {\eta _ {k}  ^ {( n)} \geq  0 } \}
 +
\rightarrow \
 +
{\mathsf E} \{ {\eta _ {k} } : {\eta _ {k} \geq  0 } \}
 +
.
 +
$$
 +
 
 +
7) Asymptotic methods for studying single-server systems (which include stability theorems) give approximate formulas for the case of heavy and light traffic. Let  $  \{ Y ( t) \} \in G _ {IS} $.  
 +
Then the system is said to be in heavy traffic conditions if
 +
 
 +
$$
 +
a  =  {\mathsf E} ( Y ( t+ 1) - Y ( t) )  < 0
 +
$$
 +
 
 +
is close to 0 and in light traffic conditions if  $  a $
 +
is close to  $  - 1 $.
  
7) Asymptotic methods for studying single-server systems (which include stability theorems) give approximate formulas for the case of heavy and light traffic. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840212.png" />. Then the system is said to be in heavy traffic conditions if
+
A precise statement, as in part (6), is again related to the introduction of triangular arrays. Specifically, for heavy traffic one considers processes  $  X  ^ {a} ( t) $,
 +
depending on a parameter  $  a \rightarrow 0 $.  
 +
Let $  X  ^ {a} ( t) $
 +
satisfy the conditions of weak dependence, which guarantee that, as  $  t \rightarrow \infty $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840213.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} \left (
  
is close to 0 and in light traffic conditions if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840214.png" /> is close to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840215.png" />.
+
\frac{| X  ^ {a} ( t) - X  ^ {a} ( 0) - at | ^ {2+ \gamma } }{A}
 +
\right )
 +
< c t ^ {1 + \gamma / 2 } ,
 +
$$
  
A precise statement, as in part (6), is again related to the introduction of triangular arrays. Specifically, for heavy traffic one considers processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840216.png" />, depending on a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840217.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840218.png" /> satisfy the conditions of weak dependence, which guarantee that, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840219.png" />,
+
$$
 +
\lim\limits _ {t \rightarrow \infty }  {\mathsf P} \left \{
 +
\frac{
 +
X  ^ {a} ( t) - X  ^ {a} ( 0) - at }{\sigma \sqrt t
 +
}
 +
< x \mid  A \right \}  = \int\limits _ {- \infty } ^ { x }  e ^ {- u  ^ {2} / 2 }  du ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840220.png" /></td> </tr></table>
+
uniformly in  $  a $,
 +
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840221.png" /></td> </tr></table>
+
$$
 +
\gamma , c , \sigma  > 0 ,\ \
 +
= \
 +
\left \{
 +
X  ^ {a} ( 0) = \inf _ {v \leq  0 }  X  ^ {a} ( v)
 +
\right \} .
 +
$$
  
uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840222.png" />, where
+
Then for the stationary virtual waiting time  $  w  ^ {s} ( t) $,
 +
as  $  a \rightarrow 0 $
 +
one has
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840223.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \left \{ w  ^ {s} ( t) >  
 +
\frac{x}{| a | }
 +
\right \}
 +
\rightarrow  e ^ {- 2 x / \sigma  ^ {2} } .
 +
$$
  
Then for the stationary virtual waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840224.png" />, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840225.png" /> one has
+
A similar result holds for the stationary distribution of  $  w  ^ {k} $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840226.png" /></td> </tr></table>
+
If the condition of heavy traffic is imposed on the sequence  $  \{ \xi  ^ {(n)} = \tau _ {j} ^ {( n) e } - \tau _ {j} ^ {( n) e } \} \in G _ {I} $(
 +
also in a triangular array relative to the parameter  $  n $),
 +
and it is required that
  
A similar result holds for the stationary distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840227.png" />.
+
$$ \tag{7 }
 +
0  >  \alpha _ {n}  = {\mathsf E} \xi _ {j}  ^ {( n)}  \rightarrow  0 ,\ \
 +
{\mathsf D} \xi _ {j}  ^ {( n)}  \rightarrow  \sigma  ^ {2}  > 0 ,
 +
$$
  
If the condition of heavy traffic is imposed on the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840228.png" /> (also in a triangular array relative to the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840229.png" />), and it is required that
+
then it is also possible to give a fairly complete description of the distribution of the limit waiting time  $  w _ {n} $,
 +
including the so-called transition phenomena. Specifically, in addition to (7), let
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840230.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>
+
$$
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf E} [ ( \xi _ {j}  ^ {( n)} )  ^ {2} :\
 +
| \xi _ {j}  ^ {( n)} | > \epsilon \sqrt n ]  = 0
 +
$$
  
then it is also possible to give a fairly complete description of the distribution of the limit waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840231.png" />, including the so-called transition phenomena. Specifically, in addition to (7), let
+
for any  $  \epsilon > 0 $.
 +
Then, if  $  \alpha = \alpha _ {n} \rightarrow 0 $
 +
as  $  n \rightarrow \infty $
 +
without changing sign, so that  $  n \alpha  ^ {2} \rightarrow v  ^ {2} $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840232.png" /></td> </tr></table>
+
$$ \tag{8 }
 +
{\mathsf P} \left \{ w _ {n} <  
 +
\frac{x}{| \alpha | }
 +
\right \} \rightarrow
 +
$$
  
for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840233.png" />. Then, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840234.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840235.png" /> without changing sign, so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840236.png" />, then
+
$$
 +
\rightarrow \
 +
{\mathsf P} \left \{ w ( u) <  
 +
\frac{( x - u  \mathop{\rm sign}  n \alpha
 +
) } \sigma
 +
: 0 \leq  u \leq  v  ^ {2} \right \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840237.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>
+
where  $  w ( u) $
 +
is a standard [[Wiener process|Wiener process]]. The value of the right-hand side of (8) can be explicitly calculated. If  $  n \alpha  ^ {2} \rightarrow 0 $,
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840238.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ w _ {n} < x \sqrt n \}  \rightarrow \
 +
\sqrt {
 +
\frac{2} \pi
 +
}
 +
\int\limits _ { 0 } ^ { {x }  / \sigma }
 +
e ^ {- u  ^ {2} / 2 }  du .
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840239.png" /> is a standard [[Wiener process|Wiener process]]. The value of the right-hand side of (8) can be explicitly calculated. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840240.png" />, then
+
If  $  n \alpha  ^ {2} \rightarrow \infty $,
 +
$  \alpha > 0 $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840241.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ w _ {n} < \alpha n + x \sqrt n \}  = \
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840242.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840243.png" />, then
+
\frac{1}{\sqrt {2 \pi } }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840244.png" /></td> </tr></table>
+
\int\limits _ {- \infty } ^ { {x }  / \sigma }
 +
e ^ {- u  ^ {2} / 2 }  du .
 +
$$
  
8) Systems with finite waiting room are characterized as follows: Calls which arrive in the system and find a queue of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840245.png" /> are refused and removed from the system. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840246.png" />, and the probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840247.png" /> will be the same as the probability that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840248.png" />-th call is refused.
+
8) Systems with finite waiting room are characterized as follows: Calls which arrive in the system and find a queue of size $  n \geq  N $
 +
are refused and removed from the system. In this case q _ {n} \leq  N $,  
 +
and the probability $  {\mathsf P} \{ q _ {n} = N \} $
 +
will be the same as the probability that the $  n $-
 +
th call is refused.
  
 
Equation (2) must here be changed to an equation of the form
 
Equation (2) must here be changed to an equation of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840249.png" /></td> </tr></table>
+
$$
 +
q _ {n+1}  = \min
 +
( N , \max ( 0 , q _ {n} + \eta _ {n} ) ) ,\ \
 +
n \geq  0.
 +
$$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840250.png" /> be metrically transitive. In addition, let the following condition be satisfied: Either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840251.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840252.png" /> and, in the second case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840253.png" /> cannot be represented in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840254.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840255.png" />. Under these conditions there exists a limit distribution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840256.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840257.png" />.
+
Let $  \{ \eta _ {n} \} \in G _ {S} $
 +
be metrically transitive. In addition, let the following condition be satisfied: Either $  {\mathsf E} \eta _ {1} \neq 0 $
 +
or $  {\mathsf E} \eta _ {1} = 0 $
 +
and, in the second case, $  \eta _ {n} $
 +
cannot be represented in the form $  \eta _ {n} = \gamma _ {n} - \gamma _ {n-1}$
 +
with $  \{ \gamma _ {n} \} \in G _ {S} $.  
 +
Under these conditions there exists a limit distribution for q _ {n} $
 +
as $  n \rightarrow \infty $.
  
If, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840258.png" /> (this holds, for example, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840259.png" /> and if the remaining control sequences belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840260.png" />), then it is possible to find an explicit form for the stationary distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840261.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840262.png" />, since in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840263.png" /> is related to a simple homogeneous [[Markov chain|Markov chain]] with a finite state space.
+
If, in addition, $  \{ \eta _ {n} \} \in G _ {I} $(
 +
this holds, for example, when $  \{ \tau _ {j}  ^ {s} \} \in E $
 +
and if the remaining control sequences belong to $  G $),  
 +
then it is possible to find an explicit form for the stationary distribution of q _ {n} $
 +
as $  n \rightarrow \infty $,  
 +
since in this case q _ {n} $
 +
is related to a simple homogeneous [[Markov chain|Markov chain]] with a finite state space.
  
 
There is also a representation for the stationary distribution:
 
There is also a representation for the stationary distribution:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840264.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>
+
$$ \tag{9 }
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} = k \} =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840265.png" /></td> </tr></table>
+
$$
 +
= \
 +
{\mathsf P} \{ \chi ( k - N , k ) = k
 +
\} {\mathsf P} \{ \chi ( - N , 1 ) \leq  - N \} +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840266.png" /></td> </tr></table>
+
$$
 +
+
 +
{\mathsf P} \{ \chi ( k- N , k ) = k- N \}
 +
{\mathsf P} \{ \chi ( - 1 , N ) \geq  N \} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840267.png" /> is the position of a particle leaving 0 and wandering with jumps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840268.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840269.png" /> to the first exit time from the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840270.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840271.png" /> (that is, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840272.png" />), then the probability (9) can be expressed explicitly in terms of the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840273.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840274.png" />.
+
where $  \chi ( - l , m ) $
 +
is the position of a particle leaving 0 and wandering with jumps $  \eta _ {k} $,
 +
$  k = 1 , 2 \dots $
 +
to the first exit time from the interval $  ( - l , m ) $.  
 +
If $  \nu _ {j}  ^ {e} \equiv 1 $(
 +
that is, if $  {\mathsf P} \{ \eta _ {n} \leq  1 \} = 1 $),  
 +
then the probability (9) can be expressed explicitly in terms of the distributions of $  \tau _ {j}  ^ {e} $
 +
and $  \nu _ {j}  ^ {s} $.
  
9) In systems with autonomous service, in contrast to the usual queueing system, the service of calls may begin only at the times <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840275.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840276.png" /> are the elements of a control sequence. Thus, calls which find the system free must wait until the next stage of service.
+
9) In systems with autonomous service, in contrast to the usual queueing system, the service of calls may begin only at the times 0 , \tau _ {1}  ^ {s} , \tau _ {1}  ^ {s} + \tau _ {2}  ^ {s} \dots $
 +
where $  \tau _ {j}  ^ {s} $
 +
are the elements of a control sequence. Thus, calls which find the system free must wait until the next stage of service.
  
Side by side with the process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840277.png" />, describing the input stream, one considers the process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840278.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840279.png" /> is defined as the number of calls which would be accepted into service up to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840280.png" /> if the queue could be infinite. Denoting by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840281.png" /> the length of the queue at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840282.png" />, not counting calls in service, and putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840283.png" />, one obtains
+
Side by side with the process $  \{ e ( t) \} $,  
 +
describing the input stream, one considers the process $  \{ s ( t) \} $,  
 +
where $  s ( t) $
 +
is defined as the number of calls which would be accepted into service up to time $  t $
 +
if the queue could be infinite. Denoting by q ( t) $
 +
the length of the queue at time $  t $,  
 +
not counting calls in service, and putting $  X ( t) = e ( t) - s ( t) $,  
 +
one obtains
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840284.png" /></td> </tr></table>
+
$$
 +
q ( t)  = \
 +
q ( 0) + X ( t) - \inf _ {0 \leq  u < t } ( 0 , X ( u) + q ( 0) ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840285.png" /></td> </tr></table>
+
$$
 +
= \
 +
\sup _ {0 \leq  u < t } ( q ( 0) + X ( t ) , X ( t) - X ( u) ) .
 +
$$
  
This equality is similar to (4) and leads to the following result. If the process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840286.png" /> is ergodic and
+
This equality is similar to (4) and leads to the following result. If the process $  \{ X ( t) \} \in G _ {IS} $
 +
is ergodic and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840287.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} ( X ( 1) - X ( 0) )  < 0 ,
 +
$$
  
then the distributions of the processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840288.png" /> converge as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840289.png" /> to the distribution of the stationary process
+
then the distributions of the processes $  \{ {X _ {t} ( u) = X ( t+ u ) } : {u \geq  0 } \} $
 +
converge as $  t \rightarrow \infty $
 +
to the distribution of the stationary process
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840290.png" /></td> </tr></table>
+
$$
 +
\overline{X}\; ( u)  = \
 +
\sup _ {v \leq  u } ( X ( u) - X ( v) ) .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840291.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840292.png" /> and the remaining control sequences belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840293.png" />, it is possible to give explicit formulas for the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076840/q076840294.png" />.
+
If $  \{ \tau _ {j}  ^ {s} \} \in E $
 +
or $  \{ \tau _ {j}  ^ {e} \} \in E $
 +
and the remaining control sequences belong to $  G _ {I} $,  
 +
it is possible to give explicit formulas for the distribution of $  \overline{X}\; ( u) $.
  
 
For references see [[Queueing theory|Queueing theory]].
 
For references see [[Queueing theory|Queueing theory]].

Latest revision as of 16:42, 30 December 2020


single-server queue

A queue for which the algorithm provides for calls which are not served immediately (having found the system busy) to form a queue; in this connection the service of this call (or batch of calls) can begin only after the service of the previous call (or batch of calls, if the service is in batches) is complete. The basic definitions and notations are to be found in Queue.

The most natural characteristics of the state of a queueing system are the following: a) the waiting time $ w _ {n} $ to the beginning of the service of the $ n $-th request, and the virtual waiting time $ w ( t) $, which is defined as the time necessary for the system to be free of the calls which arrived up to time $ t $; b) the queue length $ q _ {n} $ at the time of arrival of the $ n $-th call and the queue length $ q ( t) $ at time $ t $.

1) In the "single" case ( $ \nu _ {j} ^ {e} \equiv 1 $) the values $ w _ {n} $ are connected by the recurrence relations

$$ \tag{1 } w _ {n+1} = \max ( 0 , w _ {n} + \xi _ {n} ) ,\ \ \xi _ {n} = \tau _ {n} ^ {s} - \tau _ {n} ^ {e} . $$

A queueing system in the "multiple" case, when $ \nu _ {j} ^ {e} $, $ \nu _ {j} ^ {s} $ are different from one, may be described by the same type of equation (for the waiting time or queue length). For example, for the queue length $ q _ {n} $ one has the relation

$$ \tag{2 } q _ {n+1} = \max ( 0 , q _ {n} + \nu _ {n} ^ {e} - \beta _ {n} ) , $$

where $ \beta _ {n} $ is the number of calls which can be served during a time $ \tau _ {n} ^ {e} $ under continuous operation of the system. If $ \{ \tau _ {j} ^ {s} \} \in E $, $ \{ \nu _ {j} ^ {s} \} \in G _ {I} $, then the distribution of $ \beta _ {n} $ may be found from the relations

$$ {\mathsf E} _ {\tau _ {n} ^ {e} } e ^ {i \lambda \beta _ {n} } = \ \mathop{\rm exp} \left [ \tau _ {n} ^ {e} \alpha \sum _ { k=1 } ^ \infty ( e ^ {i \lambda k } - 1 ) {\mathsf P} \{ \nu _ {j} ^ {s} = k \} \right ] , $$

where $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {s} $.

If one puts $ X _ {0} = 0 $, $ X _ {n} = \xi _ {1} + \dots + \xi _ {n} $, then the solution of (1) has the form

$$ \tag{3 } w _ {n+1} = X _ {n} - \min ( - w _ {1} , X _ {1} \dots X _ {n} ) = $$

$$ = \ \max ( X _ {n} + w _ {1} , X _ {n} - X _ {1} \dots X _ {n} - X _ {n-1} , 0 ) . $$

Hence it follows that if $ \{ \xi _ {n} \} \in G _ {S} $ and $ {\mathsf P} \{ X _ {n} \in \Delta \} \rightarrow 0 $ for any fixed interval $ \Delta $ as $ n \rightarrow \infty $, then there is a limit distribution for the waiting time:

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ w _ {n} > x \} = {\mathsf P} \{ Y > x \} , $$

where

$$ Y = \sup _ {k \geq 0 } Y _ {k} ,\ \ Y _ {k} = \xi _ {-k} + \dots + \xi _ {-1} ,\ Y _ {0} = 0 . $$

Here the variables $ \xi _ {-k} $ are the elements of the sequence $ \{ \xi _ {n} \} _ {n = - \infty } ^ \infty $ which extends $ \{ \xi _ {n} \} _ {n=1} ^ \infty $ to a sequence which is stationary on the whole line. In what follows it will be assumed that such an extension has been made for all control sequences.

The values

$$ w ^ {k} = \sup ( 0 , \xi _ {k} , \xi _ {k} + \xi _ {k-1} , \xi _ {k} + \xi _ {k-1} + \xi _ {k-2} ,\dots ) $$

satisfy (1) and have a distribution coinciding with the limit distribution of $ w _ {n} $. This is the stationary waiting time process.

Let $ \{ \xi _ {n} \} \in G _ {S} $ be ergodic ( $ X _ {n} / n \rightarrow {\mathsf E} \xi _ {1} $ with probability $ 1 $). Then

$$ {\mathsf P} \{ Y < \infty \} = \ {\mathsf P} \{ w ^ {k} < \infty \} = 1 $$

if $ {\mathsf E} \xi _ {k} < 0 $ or if $ {\mathsf E} \xi _ {k} = 0 $ and $ \xi _ {k} = \eta _ {k+1} - \eta _ {k} $, where $ \{ \eta _ {k} \} \in G _ {S} $. Otherwise

$$ {\mathsf P} \{ Y = \infty \} = {\mathsf P} \{ w ^ {k} = \infty \} = 1 . $$

If $ \{ \xi _ {n} \} \in G _ {I} $, then

$$ {\mathsf P} \{ Y < \infty \} = 1 $$

if and only if $ {\mathsf E} \xi _ {k} < 0 $( the trivial case $ \xi _ {k} = 0 $ being excluded).

2) As already noted, another possible characteristic of the state of the system is the virtual waiting time $ w ( t) $. Roughly speaking, this is the time which the call arriving at time $ t $ would have to wait until the beginning of its service. Let $ S ( t) $ be the sum of the service times of the calls which arrive in the system up to time $ t $, and let $ X ( t) = S ( t) - t $. An analogue of (3) here is the relation

$$ \tag{4 } w ( t) = X ( t) - \inf _ {0 \leq u \leq t } ( 0 , X ( u) ) . $$

Let $ G _ {IS} $ be the class of processes with stationary increments in the narrow sense and let $ G _ {II} $ be the class of processes with independent increments ( $ G _ {II} $ and $ G _ {IS} $ could here be narrower: for example, it can be supposed that $ G _ {II} $ is the class of generalized Poisson processes with positive jumps and drift $ - 1 $). If the process $ \{ {X ( t) } : {t \geq 0 } \} \in G _ {IS} $, then it can be extended to a process $ \{ {X ( t) } : {- \infty < t < \infty } \} $ given on the whole line and also in $ G _ {IS} $. In this case

$$ \lim\limits _ {t \rightarrow \infty } {\mathsf P} \{ w ( t) > x \} = \ {\mathsf P} \{ \overline{Y}\; > x \} $$

exists, where

$$ \overline{Y}\; = \sup _ {u \geq 0 } Y ( t) ,\ \ Y ( t) = X ( 0) - X (- t) . $$

If, in addition,

$$ {\mathsf E} ( X ( 1) - X ( 0) ) = {\mathsf E} ( Y ( 1) - Y ( 0) ) = a < 0 , $$

then the distribution of the process

$$ w _ {t} ( u) = \{ {w ( t - u ) } : {u \geq 0 } \} $$

converges as $ t \rightarrow \infty $ to the distribution of the process

$$ w ^ {s} ( u) = \sup _ {v \leq u } ( X ( u) - X ( v) ) , $$

which is the strictly stationary virtual waiting time process. Here convergence holds in the strong form:

$$ {\mathsf P} \{ w _ {t} \in B \} \rightarrow {\mathsf P} \{ w ^ {s} \in B \} $$

for any measurable $ B $.

Further, if $ \{ X ( t) \} \in G _ {IS} $ and $ a < 0 $, then $ X ( t) $ has a conditional renewal function $ H _ {0} ( x) $:

$$ H _ {0} ( x) = $$

$$ = \ \int\limits _ { 0 } ^ \infty {\mathsf P} \left \{ 0 \leq X ( u) - X ( 0) < x : X ( 0) = \inf _ {v \leq 0 } X ( v) \right \} d u < \infty ; $$

here

$$ \left . \begin{array}{c} {\mathsf P} \{ w ^ {s} ( u) \geq x \} = - a \frac{d H _ {0} ( x) }{dx} , \\ {\mathsf P} \{ w ^ {s} ( t) = 0 \} = - a . \end{array} \right \} $$

These formulas still hold when $ \nu _ {j} ^ {e} \neq 1 $.

For systems in which $ \{ \tau _ {j} ^ {s} - \tau _ {j} ^ {e} \} \in G _ {I} $ there are simple relations between the distributions of $ w ^ {k} $ and $ w ^ {s} ( t) $.

3) Ergodic theorems for the queue length can be obtained with the help of the corresponding theorems for the waiting time. For example, let the sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {e} \} \in G _ {S} $ be ergodic (metrically transitive). If, in addition, $ {\mathsf E} ( \tau _ {j} ^ {s} - \tau _ {j} ^ {e} ) < 0 $, then there is a (stationary) limit distribution for $ q _ {n} $ such that

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ q _ {n} > k \} \ = {\mathsf P} \{ w ^ {0} > \tau _ {1} ^ {e} + \dots + \tau _ {k} ^ {e} \} . $$

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $ and $ \tau _ {j} ^ {e} $ has a non-lattice distribution, then

$$ \lim\limits _ {\tau \rightarrow \infty } \ {\mathsf P} \{ q ( t) > k + 1 \} \ = {\mathsf P} \{ w ^ {0} > \tau _ {1} ^ {e} + \dots + \tau _ {k} ^ {e} + \gamma \} ,\ k \geq 0 , $$

$$ \lim\limits _ {\tau \rightarrow 0 } {\mathsf P} \{ q ( t) = 0 \} = - \frac{a}{ {\mathsf E} \tau ^ {e} } , $$

where all the components under the probability sign on the right-hand side are independent, and $ \gamma $ has a density

$$ \frac{ {\mathsf P} \{ \tau _ {j} ^ {e} > x \} }{ {\mathsf E} \tau ^ {e} } , $$

$$ w ^ {0} = \sup ( 0 , \xi _ {0} , \xi _ {0} + \xi _ {-1} ,\dots ) ,\ \xi _ {j} = \tau _ {j} ^ {s} - \tau _ {j} ^ {e} . $$

If $ \{ \tau _ {j} ^ {e} \} \in E $, then the limit distributions of $ q _ {n} $ and $ q ( t) $ coincide.

4) If $ \{ \tau _ {j} ^ {e} \} \in E $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $( it is also supposed that $ \nu _ {j} ^ {e} \neq 1 $, $ \{ \nu _ {j} ^ {e} \} \in G _ {I} $), then it is possible to obtain an exact formula for the limit distribution of $ w ( t) $:

$$ {\mathsf P} \{ w ( t) < x \} \ = {\mathsf P} \{ Y ( t) < x \} + $$

$$ + \frac \partial {\partial x } \int\limits _ { 0 } ^ { t } {\mathsf E} \left ( \frac{Y ( u) }{u} : \ Y ( u) < 0 \right ) {\mathsf P} \{ Y ( t - u ) < x \} d u , $$

$$ {\mathsf P} \{ w ( t) = 0 \} = - {\mathsf E} \left ( \frac{ Y ( t) }{t} : Y ( t) < 0 \right ) . $$

For $ a < 0 $ and $ t \rightarrow \infty $ there is the Khinchin–Pollaczek formula for the stationary distribution:

$$ {\mathsf E} e ^ {i \lambda w ^ {s} ( u) } \ = \frac{1 - \alpha {\mathsf E} \theta }{1 - \alpha \frac{\phi ( \lambda ) - 1 }{i \lambda } } ,\ \ \phi ( \lambda ) = {\mathsf E} e ^ {i \lambda \theta } , $$

where $ \theta $ is the jump of the process $ X ( t) $( $ \theta = \tau _ {j} ^ {s} $ if $ \nu _ {j} ^ {e} \equiv 1 $) and $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {e} $.

Let $ T _ {j} $, $ j = 1 , 2 \dots $ be the busy periods of the system (that is, the lengths of the time intervals during which $ w ( t) > 0 $). Then, for the systems considered,

$$ {\mathsf P} \{ T _ {j} \in ( u , u + d u ) \} \ = \frac{1}{\alpha u } {\mathsf P} \{ X ( u) \in ( 0 , d u ) \} . $$

5) For systems in which $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {I} $( it is also assumed that $ \nu _ {j} ^ {e} \neq 1 $, $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} , \nu _ {j} ^ {e} \} \in G _ {I} $), the distribution of $ w ^ {k} $ coincides with the distribution of the variable

$$ Y = \sup ( 0 , \xi _ {1} , \xi _ {1} + \xi _ {2} ,\dots ) . $$

If the distribution of $ \xi _ {j} $ is known, then the distribution of $ Y $ can be found as follows. If $ {\mathsf P} \{ Y < \infty \} = 1 $( this is always true if $ {\mathsf E} \xi _ {j} < 0 $), then the factorization identity

$$ 1 - {\mathsf E} e ^ {i \lambda \xi } = ( 1 - p ) \frac{1 - {\mathsf E} e ^ {i \lambda \chi } }{ {\mathsf E} e ^ {i \lambda Y } } ,\ \ \mathop{\rm Im} \lambda = 0 , $$

holds, where $ p = {\mathsf P} \{ Y < 0 \} $ and $ \chi \leq 0 $ is the size of the first non-positive sum among $ \xi _ {1} , \xi _ {1} + \xi _ {2} ,\dots $. This relation permits one to relate $ {\mathsf E} e ^ {i \lambda Y } $ to the ratio $ w _ {+} ( \lambda ) / w _ {+} ( 0) $ in any identity

$$ \tag{5 } 1 - {\mathsf E} e ^ {i \lambda \xi } = \frac{w _ {-} ( \lambda ) }{w _ {+} ( \lambda ) } ,\ \ \mathop{\rm Im} \lambda = 0 , $$

in which the functions $ w _ \pm ( \lambda ) $ admit a representation

$$ w _ \pm ( \lambda ) = \ \int\limits _ { 0 } ^ { \pm \infty } e ^ {i \lambda t } d V _ \pm ( t) $$

( $ V _ \pm $ are functions of bounded variation). Equality (5) provides the so-called $ V $- factorization of the function $ 1 - {\mathsf E} e ^ {i \lambda \xi } $. It explains the following cases, when it is possible to search for $ {\mathsf E} e ^ {i \lambda Y } $ explicitly.

Assume that $ - \infty < {\mathsf E} \xi < 0 $ and put

$$ f ( \lambda ) = {\mathsf E} e ^ {i \lambda \xi } ,\ \ f _ {+} ( \lambda ) = e ^ {i \lambda \tau ^ {s} } ,\ \ f _ {-} ( \lambda ) = e ^ {- i \lambda \tau ^ {e} } , $$

so that $ f ( \lambda ) = f _ {+} ( \lambda ) f _ {-} ( \lambda ) $.

A) If $ f _ {+} $ is a rational function, $ f _ {+} = P _ {m} / Q _ {n} $, where $ P _ {m} $ and $ Q _ {n} $ are polynomials of degree $ m $ and $ n $, respectively, then in the domain $ \mathop{\rm Im} \lambda < 0 $ the function $ ( 1 - f ) Q _ {n} $ has exactly $ n $ zeros $ \lambda _ {1} \dots \lambda _ {n} $, and

$$ w _ {+} ( \lambda ) = \ \frac{Q _ {n} ( \lambda ) }{\prod _ { k=1} ^ { n } ( \lambda - \lambda _ {k} ) } , $$

$$ {\mathsf E} e ^ {i \lambda Y } = \frac{w _ {+} ( \lambda ) }{w _ {+} ( 0) } . $$

This means that if the distribution of $ \tau ^ {s} $ can be represented as

$$ {\mathsf P} \{ \tau ^ {s} > x \} = \ \sum _ { k } P _ {k} ( x) e ^ {- \alpha _ {k} x } ,\ \ \mathop{\rm Re} \alpha _ {k} > 0 , $$

where $ P _ {k} ( x) $ is a polynomial, then the same type of representation (for other $ \alpha _ {k} $ and $ P _ {k} $, determined by $ \lambda _ {1} \dots \lambda _ {n} $) also holds for $ {\mathsf P} \{ Y < x \} $.

B) If $ f _ {-} = P _ {m} / Q _ {n} $ is a rational function, then in the domain $ \mathop{\rm Im} \lambda > 0 $ the function $ ( 1 - f ) Q _ {n} $ has $ n- 1 $ zeros $ \lambda _ {1} \dots \lambda _ {n-1} $, and

$$ w _ {+} ( \lambda ) = \ i \lambda \frac{\prod _ { k=1 } ^ { n- 1} ( \lambda - \lambda _ {k} ) }{Q _ {n} ( \lambda ) ( 1 - f ( \lambda ) ) } . $$

In addition to these formulas, giving explicit expressions for the distribution of $ Y $, it is also possible, in a broad class of cases, to describe the asymptotic behaviour of $ {\mathsf P} \{ Y > x \} $ as $ x \rightarrow \infty $. Namely, if

$$ \gamma = \ \sup ( \mu : {\mathsf E} e ^ {\mu \xi } \langle \infty ) \rangle 0 $$

and $ {\mathsf E} e ^ {\gamma \xi } > 1 $, then there is a unique root of the equation $ {\mathsf E} e ^ {q \xi } = 1 $. In this case, as $ x \rightarrow \infty $,

$$ {\mathsf P} \{ Y > x \} = \ c _ {1} e ^ {-qx} ( 1+ o ( 1) ) . $$

If $ \gamma = 0 $, $ - \infty < {\mathsf E} \xi < 0 $, then

$$ {\mathsf P} \{ Y > x \} = \ c _ {2} \int\limits _ { x } ^ \infty {\mathsf P} \{ \xi > t \} dt ( 1 + o ( 1) ) . $$

The constants $ c _ {1} $ and $ c _ {2} $ have been found explicitly.

Results similar to those discussed in parts 2)–5) are true even for discrete-time systems, when the time $ t $ and the random variables of the control sequences take only integer values.

6) Stability theorems investigate conditions under which a small change in the finite-dimensional distributions of the control sequences leads to a small change in the stationary distribution of the waiting time or queue length. The importance of stability for queues is explained by the fact that in real problems various assumptions are usually made on the nature of the control sequences (for example, it is assumed that the $ \xi _ {j} $ are independent or that the $ \tau _ {j} ^ {e} $ are exponentially distributed), whereas, in reality, these assumptions are only approximately satisfied. The question is whether the solution of such "idealized" problems is close to the solution of the actual problem.

To obtain a precise statement of the problem, triangular arrays are used, where equation (1) is controlled by stationary sequences (triangular arrays) $ \xi ^ {( n)} = \{ {\xi _ {j} ^ {( n)} } : {- \infty < j < \infty } \} $, $ n = 1 , 2 ,\dots $. In addition, one considers a stationary sequence $ \xi = \{ {\xi _ {j} } : {- \infty < j < \infty } \} $ and puts

$$ Y ^ {( n)} = \ \sup _ {k \geq 0 } Y _ {k} ^ {( n)} ,\ \ Y _ {k} ^ {( n)} = \sum _ { j=1 } ^ { n } \xi _ {-j} ^ {( n)} . $$

The answer to the question posed above is given by the following result.

Let the finite-dimensional distributions of $ \xi ^ {( n)} $ converge weakly to the corresponding distributions of $ \xi $, which is assumed to be ergodic, and let $ {\mathsf E} \xi _ {j} < 0 $. Then for the weak convergence

$$ \tag{6 } {\mathsf P} \{ Y ^ {( n)} < t \} \Rightarrow {\mathsf P} \{ Y < t \} $$

(that is, for the convergence of the distributions of the stationary waiting times) it is sufficient that

$$ {\mathsf E} ( \xi _ {j} ^ {( n)} : \xi _ {j} ^ {( n)} \geq 0 ) \rightarrow \ {\mathsf E} ( \xi _ {j} : \xi _ {j} \geq 0 ) . $$

The stated condition for convergence is almost necessary.

If the control sequences $ \{ \tau _ {j} ^ {( n) e } , \tau _ {j} ^ {( n) s } \} $ and $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $ are such that $ \tau _ {j} ^ {( n) e } $ and $ \tau _ {j} ^ {( n) s } $ are independent and the distributions of $ \{ \tau _ {j} ^ {( n) e } , \tau _ {j} ^ {( n) s } \} $ converge weakly to the distributions of $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $, then for (6) it is sufficient that

$$ {\mathsf E} \tau _ {j} ^ {( n) s } \rightarrow \ {\mathsf E} \tau _ {j} ^ {s} . $$

The situation is similar for the stationary distribution of the virtual waiting time $ w ^ {s} ( t) $. If the finite-dimensional distributions of the processes $ Y ^ {( n)} ( t) \in G _ {IS} $ converge to the distributions of $ Y ( t) \in G _ {IS} $ and if the sequence $ \{ \eta _ {k} = Y ( k+ 1) - Y ( k) \} $ is ergodic, $ {\mathsf E} \eta _ {k} = a < 0 $, then for the convergence of the distributions of

$$ \sup _ {t \geq 0 } Y ^ {(n)} ( t) \ \ \textrm{ and } \ \ \sup _ {t \geq 0 } Y ( t) $$

it is sufficient that

$$ {\mathsf E} \{ {\eta _ {k} ^ {(n)} } : {\eta _ {k} ^ {( n)} \geq 0 } \} \rightarrow \ {\mathsf E} \{ {\eta _ {k} } : {\eta _ {k} \geq 0 } \} . $$

7) Asymptotic methods for studying single-server systems (which include stability theorems) give approximate formulas for the case of heavy and light traffic. Let $ \{ Y ( t) \} \in G _ {IS} $. Then the system is said to be in heavy traffic conditions if

$$ a = {\mathsf E} ( Y ( t+ 1) - Y ( t) ) < 0 $$

is close to 0 and in light traffic conditions if $ a $ is close to $ - 1 $.

A precise statement, as in part (6), is again related to the introduction of triangular arrays. Specifically, for heavy traffic one considers processes $ X ^ {a} ( t) $, depending on a parameter $ a \rightarrow 0 $. Let $ X ^ {a} ( t) $ satisfy the conditions of weak dependence, which guarantee that, as $ t \rightarrow \infty $,

$$ {\mathsf E} \left ( \frac{| X ^ {a} ( t) - X ^ {a} ( 0) - at | ^ {2+ \gamma } }{A} \right ) < c t ^ {1 + \gamma / 2 } , $$

$$ \lim\limits _ {t \rightarrow \infty } {\mathsf P} \left \{ \frac{ X ^ {a} ( t) - X ^ {a} ( 0) - at }{\sigma \sqrt t } < x \mid A \right \} = \int\limits _ {- \infty } ^ { x } e ^ {- u ^ {2} / 2 } du , $$

uniformly in $ a $, where

$$ \gamma , c , \sigma > 0 ,\ \ A = \ \left \{ X ^ {a} ( 0) = \inf _ {v \leq 0 } X ^ {a} ( v) \right \} . $$

Then for the stationary virtual waiting time $ w ^ {s} ( t) $, as $ a \rightarrow 0 $ one has

$$ {\mathsf P} \left \{ w ^ {s} ( t) > \frac{x}{| a | } \right \} \rightarrow e ^ {- 2 x / \sigma ^ {2} } . $$

A similar result holds for the stationary distribution of $ w ^ {k} $.

If the condition of heavy traffic is imposed on the sequence $ \{ \xi ^ {(n)} = \tau _ {j} ^ {( n) e } - \tau _ {j} ^ {( n) e } \} \in G _ {I} $( also in a triangular array relative to the parameter $ n $), and it is required that

$$ \tag{7 } 0 > \alpha _ {n} = {\mathsf E} \xi _ {j} ^ {( n)} \rightarrow 0 ,\ \ {\mathsf D} \xi _ {j} ^ {( n)} \rightarrow \sigma ^ {2} > 0 , $$

then it is also possible to give a fairly complete description of the distribution of the limit waiting time $ w _ {n} $, including the so-called transition phenomena. Specifically, in addition to (7), let

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf E} [ ( \xi _ {j} ^ {( n)} ) ^ {2} :\ | \xi _ {j} ^ {( n)} | > \epsilon \sqrt n ] = 0 $$

for any $ \epsilon > 0 $. Then, if $ \alpha = \alpha _ {n} \rightarrow 0 $ as $ n \rightarrow \infty $ without changing sign, so that $ n \alpha ^ {2} \rightarrow v ^ {2} $, then

$$ \tag{8 } {\mathsf P} \left \{ w _ {n} < \frac{x}{| \alpha | } \right \} \rightarrow $$

$$ \rightarrow \ {\mathsf P} \left \{ w ( u) < \frac{( x - u \mathop{\rm sign} n \alpha ) } \sigma : 0 \leq u \leq v ^ {2} \right \} , $$

where $ w ( u) $ is a standard Wiener process. The value of the right-hand side of (8) can be explicitly calculated. If $ n \alpha ^ {2} \rightarrow 0 $, then

$$ {\mathsf P} \{ w _ {n} < x \sqrt n \} \rightarrow \ \sqrt { \frac{2} \pi } \int\limits _ { 0 } ^ { {x } / \sigma } e ^ {- u ^ {2} / 2 } du . $$

If $ n \alpha ^ {2} \rightarrow \infty $, $ \alpha > 0 $, then

$$ {\mathsf P} \{ w _ {n} < \alpha n + x \sqrt n \} = \ \frac{1}{\sqrt {2 \pi } } \int\limits _ {- \infty } ^ { {x } / \sigma } e ^ {- u ^ {2} / 2 } du . $$

8) Systems with finite waiting room are characterized as follows: Calls which arrive in the system and find a queue of size $ n \geq N $ are refused and removed from the system. In this case $ q _ {n} \leq N $, and the probability $ {\mathsf P} \{ q _ {n} = N \} $ will be the same as the probability that the $ n $- th call is refused.

Equation (2) must here be changed to an equation of the form

$$ q _ {n+1} = \min ( N , \max ( 0 , q _ {n} + \eta _ {n} ) ) ,\ \ n \geq 0. $$

Let $ \{ \eta _ {n} \} \in G _ {S} $ be metrically transitive. In addition, let the following condition be satisfied: Either $ {\mathsf E} \eta _ {1} \neq 0 $ or $ {\mathsf E} \eta _ {1} = 0 $ and, in the second case, $ \eta _ {n} $ cannot be represented in the form $ \eta _ {n} = \gamma _ {n} - \gamma _ {n-1}$ with $ \{ \gamma _ {n} \} \in G _ {S} $. Under these conditions there exists a limit distribution for $ q _ {n} $ as $ n \rightarrow \infty $.

If, in addition, $ \{ \eta _ {n} \} \in G _ {I} $( this holds, for example, when $ \{ \tau _ {j} ^ {s} \} \in E $ and if the remaining control sequences belong to $ G $), then it is possible to find an explicit form for the stationary distribution of $ q _ {n} $ as $ n \rightarrow \infty $, since in this case $ q _ {n} $ is related to a simple homogeneous Markov chain with a finite state space.

There is also a representation for the stationary distribution:

$$ \tag{9 } \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ q _ {n} = k \} = $$

$$ = \ {\mathsf P} \{ \chi ( k - N , k ) = k \} {\mathsf P} \{ \chi ( - N , 1 ) \leq - N \} + $$

$$ + {\mathsf P} \{ \chi ( k- N , k ) = k- N \} {\mathsf P} \{ \chi ( - 1 , N ) \geq N \} , $$

where $ \chi ( - l , m ) $ is the position of a particle leaving 0 and wandering with jumps $ \eta _ {k} $, $ k = 1 , 2 \dots $ to the first exit time from the interval $ ( - l , m ) $. If $ \nu _ {j} ^ {e} \equiv 1 $( that is, if $ {\mathsf P} \{ \eta _ {n} \leq 1 \} = 1 $), then the probability (9) can be expressed explicitly in terms of the distributions of $ \tau _ {j} ^ {e} $ and $ \nu _ {j} ^ {s} $.

9) In systems with autonomous service, in contrast to the usual queueing system, the service of calls may begin only at the times $ 0 , \tau _ {1} ^ {s} , \tau _ {1} ^ {s} + \tau _ {2} ^ {s} \dots $ where $ \tau _ {j} ^ {s} $ are the elements of a control sequence. Thus, calls which find the system free must wait until the next stage of service.

Side by side with the process $ \{ e ( t) \} $, describing the input stream, one considers the process $ \{ s ( t) \} $, where $ s ( t) $ is defined as the number of calls which would be accepted into service up to time $ t $ if the queue could be infinite. Denoting by $ q ( t) $ the length of the queue at time $ t $, not counting calls in service, and putting $ X ( t) = e ( t) - s ( t) $, one obtains

$$ q ( t) = \ q ( 0) + X ( t) - \inf _ {0 \leq u < t } ( 0 , X ( u) + q ( 0) ) = $$

$$ = \ \sup _ {0 \leq u < t } ( q ( 0) + X ( t ) , X ( t) - X ( u) ) . $$

This equality is similar to (4) and leads to the following result. If the process $ \{ X ( t) \} \in G _ {IS} $ is ergodic and

$$ {\mathsf E} ( X ( 1) - X ( 0) ) < 0 , $$

then the distributions of the processes $ \{ {X _ {t} ( u) = X ( t+ u ) } : {u \geq 0 } \} $ converge as $ t \rightarrow \infty $ to the distribution of the stationary process

$$ \overline{X}\; ( u) = \ \sup _ {v \leq u } ( X ( u) - X ( v) ) . $$

If $ \{ \tau _ {j} ^ {s} \} \in E $ or $ \{ \tau _ {j} ^ {e} \} \in E $ and the remaining control sequences belong to $ G _ {I} $, it is possible to give explicit formulas for the distribution of $ \overline{X}\; ( u) $.

For references see Queueing theory.

How to Cite This Entry:
Queue with waiting and one service channel. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Queue_with_waiting_and_one_service_channel&oldid=12210
This article was adapted from an original article by A.A. Borovkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article