Namespaces
Variants
Actions

Difference between revisions of "Queue input stream of calls"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(latex details)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A random process given in some form or other and describing the appearance of calls in the queue. The input stream is usually defined by random sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768102.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768103.png" /> are the time intervals between the arrivals in the system of the batches of requests of sizes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768104.png" /> respectively. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768105.png" />, the stream is called single. Equivalently, the input stream can be given by a point process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768106.png" />, giving the number of calls arriving in the system up to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768107.png" />. It can be assumed, for the sake of being specific, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768108.png" />.
+
<!--
 +
q0768101.png
 +
$#A+1 = 80 n = 0
 +
$#C+1 = 80 : ~/encyclopedia/old_files/data/Q076/Q.0706810 Queue input stream of calls
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The most common requirement usually placed on the input stream is stationarity. This condition can be of two kinds: either stationarity in the narrow sense is required of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q0768109.png" /> (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681010.png" />), or it is required that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681011.png" /> be a process with increments that are stationary in the narrow sense (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681012.png" />). These requirements, in general, do not coincide (cf. [[Stationary stochastic process|Stationary stochastic process]]).
+
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
A random process given in some form or other and describing the appearance of calls in the queue. The input stream is usually defined by random sequences  $  \{ \tau _ {j}  ^ {e} , \nu _ {j}  ^ {e} \} $,
 +
where  $  \tau _ {j}  ^ {e} $,
 +
$  j = 1 , 2 \dots $
 +
are the time intervals between the arrivals in the system of the batches of requests of sizes  $  \nu _ {1}  ^ {e} \geq  1 , \nu _ {2}  ^ {e} \geq  1 \dots $
 +
respectively. If  $  \nu _ {j}  ^ {e} \equiv 1 $,
 +
the stream is called single. Equivalently, the input stream can be given by a point process  $  \{ {e ( t) } : {t \geq  0 } \} $,
 +
giving the number of calls arriving in the system up to time  $  t $.
 +
It can be assumed, for the sake of being specific, that  $  e ( t) = e ( t - 0 ) $.
 +
 
 +
The most common requirement usually placed on the input stream is stationarity. This condition can be of two kinds: either stationarity in the narrow sense is required of the sequence $  \{ \tau _ {j}  ^ {e} , \nu _ {j}  ^ {e} \} $(
 +
denoted by $  \{ \tau _ {j}  ^ {e} , \nu _ {j}  ^ {e} \} \in G _ {S} $),  
 +
or it is required that $  e ( t) $
 +
be a process with increments that are stationary in the narrow sense (denoted by $  \{ e ( t) \} \in G _ {IS} $).  
 +
These requirements, in general, do not coincide (cf. [[Stationary stochastic process|Stationary stochastic process]]).
  
 
The intensity of a stationary stream is the number
 
The intensity of a stationary stream is the number
  
<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/q076810/q07681013.png" /></td> </tr></table>
+
$$
 +
\mu  = \lim\limits _ {t \rightarrow \infty } \
 +
 
 +
\frac{ {\mathsf E} ( e ( t) - e ( 0) ) }{t}
 +
.
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681014.png" />, then
+
If $  \{ e ( t) \} \in G _ {IS} $,  
 +
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/q076810/q07681015.png" /></td> </tr></table>
+
$$
 +
\mu  = {\mathsf E} ( e ( t + 1 ) - e ( t) )  = \
 +
{\mathsf E} ( e ( 1) - e ( 0) ) ,
 +
$$
  
so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681016.png" /> is equal to the mean number of calls which arrive in the system in unit time. If the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681017.png" /> is stationary and ergodic and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681018.png" />, then
+
so that $  \mu $
 +
is equal to the mean number of calls which arrive in the system in unit time. If the sequence $  \{ \tau _ {j}  ^ {e} \} $
 +
is stationary and ergodic and if $  \{ \nu _ {j}  ^ {e} \} \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/q076810/q07681019.png" /></td> </tr></table>
+
$$
 +
\mu  = \
  
In other cases the relation between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681020.png" /> and the distribution of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681021.png" /> can be more complicated.
+
\frac{ {\mathsf E} \nu _ {j}  ^ {e} }{ {\mathsf E} \tau _ {j}  ^ {e} }
 +
.
 +
$$
  
Let there be given a process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681022.png" /> with intensity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681023.png" /> and initial value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681024.png" />. Closely associated with the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681025.png" /> is another parameter of the input stream, defined by
+
In other cases the relation between  $  \mu $
 +
and the distribution of the sequence  $  \{ \tau _ {j}  ^ {e} , \nu _ {j}  ^ {e} \} \in G _ {S} $
 +
can be more complicated.
  
<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/q076810/q07681026.png" /></td> </tr></table>
+
Let there be given a process  $  \{ e ( t) \} \in G _ {IS} $
 +
with intensity  $  \mu $
 +
and initial value  $  e ( 0) = 0 $.  
 +
Closely associated with the number  $  \mu $
 +
is another parameter of the input stream, defined by
  
This limit always exists and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681027.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681028.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681029.png" /> if and only if the input stream is single.
+
$$
 +
\alpha  =  \lim\limits _ {t \rightarrow 0 } \
 +
 
 +
\frac{ {\mathsf P} ( e ( t) \geq  1 ) }{t}
 +
.
 +
$$
 +
 
 +
This limit always exists and $  \alpha \leq  \mu $.  
 +
If $  \mu < \infty $,  
 +
then $  \alpha = \mu $
 +
if and only if the input stream is single.
  
 
In studying the properties of the input stream one often uses the so-called Palm functions
 
In studying the properties of the input stream one often uses the so-called Palm functions
  
<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/q076810/q07681030.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\phi _ {k} ( t)  = \
 +
\lim\limits _ {\tau \rightarrow 0 } \
 +
 
 +
\frac{ {\mathsf P} \{ e ( t + \tau ) - e ( \tau ) = k , e ( \tau ) \geq  1 \} }{ {\mathsf P} \{ e ( \tau ) \geq  1 \} }
 +
,
 +
$$
 +
 
 +
$$
 +
= 0 , 1 ,\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/q076810/q07681031.png" /></td> </tr></table>
+
(here  $  e ( 0) = 0 $),
 +
which have the meaning of the conditional probabilities that  $  k $
 +
calls arrive in the interval  $  ( 0 , t ) $
 +
under the condition that a call has arrived at time  $  0 $.
 +
The function  $  \phi _ {k} ( t) $
 +
is related to the distribution of  $  e ( t) $
 +
by:
  
(here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681032.png" />), which have the meaning of the conditional probabilities that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681033.png" /> calls arrive in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681034.png" /> under the condition that a call has arrived at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681035.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681036.png" /> is related to the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681037.png" /> by:
+
$$
 +
{\mathsf P} \{ e ( t) = 0 \}  = 1 - \lambda
 +
\int\limits _ { 0 } ^ { t }  \phi _ {0} ( u)  d 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/q076810/q07681038.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ e ( t) = k \}  = \lambda \int\limits _ { 0 } ^ { t }  [
 +
\phi _ {k-1} ( u) - \phi _ {k} ( u) ]  d 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/q076810/q07681039.png" /></td> </tr></table>
+
If  $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,
 +
then
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681040.png" />, then
+
$$
 +
\phi _ {0} ( t)  = {\mathsf P} \{ \tau _ {j}  ^ {e} \geq  t \} ,
 +
$$
  
<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/q076810/q07681041.png" /></td> </tr></table>
+
$$
 +
\sum_{j=0}^ { k }  \phi _ {j} ( t)  = {\mathsf P} \{ \tau _ {1}  ^ {e} + \dots + \tau _ {k+1}  ^ {e} \geq  t \} .
 +
$$
  
<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/q076810/q07681042.png" /></td> </tr></table>
+
A significant role in queueing theory is played by the so-called simplest, or Poisson, input stream — a stationary input stream for which  $  \nu _ {j}  ^ {e} = 1 $,
 +
$  \{ \tau _ {j}  ^ {e} \} \in E $.
 +
In order to define the simplest stream in terms of  $  e ( t) $
 +
it is required that  $  \{ e ( t) \} $
 +
be Poisson (cf. [[Poisson process|Poisson process]]). The increments of this process in disjoint time intervals are independent and have Poisson distributions with parameters proportional to the length of the intervals.
  
A significant role in queueing theory is played by the so-called simplest, or Poisson, input stream — a stationary input stream for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681044.png" />. In order to define the simplest stream in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681045.png" /> it is required that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681046.png" /> be Poisson (cf. [[Poisson process|Poisson process]]). The increments of this process in disjoint time intervals are independent and have Poisson distributions with parameters proportional to the length of the intervals.
+
Non-homogeneous Poisson streams also find broad application (particularly in telephony); these are characterized as processes  $  e ( t) $
 +
with independent increments distributed by the Poisson law:
  
Non-homogeneous Poisson streams also find broad application (particularly in telephony); these are characterized as processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681047.png" /> with independent increments distributed by the Poisson law:
+
$$
 +
{\mathsf P} \{ e ( t + u ) - e ( t) = 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/q076810/q07681048.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/q076810/q07681049.png" /></td> </tr></table>
+
\frac{e ^ {- A ( t + u ) - A ( t) } }{k!}
 +
( A ( t + u ) - A ( t) )  ^ {k} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681050.png" /> is the drift function of the process (in the homogeneous case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681051.png" />).
+
where $  A ( t) $
 +
is the drift function of the process (in the homogeneous case $  A ( t) = \alpha t $).
  
 
The special role of Poisson processes in queueing theory is explained in many respects by the fundamental limit theorem for input streams, which asserts that under broad assumptions the sum of a large number of arbitrary independent stationary input streams of low intensity converges to a Poisson process. The frequent use of the assumption that the input flow is Poisson rests on the fact that in many applications real input streams are formed in precisely that way (for example, the stream of calls arriving at a telephone exchange is the sum of the weak streams originating from the individual subscribers).
 
The special role of Poisson processes in queueing theory is explained in many respects by the fundamental limit theorem for input streams, which asserts that under broad assumptions the sum of a large number of arbitrary independent stationary input streams of low intensity converges to a Poisson process. The frequent use of the assumption that the input flow is Poisson rests on the fact that in many applications real input streams are formed in precisely that way (for example, the stream of calls arriving at a telephone exchange is the sum of the weak streams originating from the individual subscribers).
Line 55: Line 147:
 
Below, the fundamental limit theorem is given in two forms. The first relates to the sum of arbitrary (non-stationary) input streams.
 
Below, the fundamental limit theorem is given in two forms. The first relates to the sum of arbitrary (non-stationary) input streams.
  
Suppose one is given increasing sets of independent process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681053.png" /> depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681054.png" /> (that is, a triangular array), and the following notation:
+
Suppose one is given increasing sets of independent process $  e _ {1n} ( t) \dots e _ {nn} ( t) $,
 +
$  n = 1 , 2 \dots $
 +
depending on $  n $(
 +
that is, a triangular array), and the following notation:
  
<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/q076810/q07681055.png" /></td> </tr></table>
+
$$
 +
A _ {n} ( t , u )  = \
 +
\sum_{r=1}^ { n }
 +
{\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( u) \geq  1 \} ,
 +
$$
  
<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/q076810/q07681056.png" /></td> </tr></table>
+
$$
 +
B _ {n} ( t , u )  = \sum_{r=1}^ { n }  {\mathsf P}
 +
\{ e _ {rn} ( t) - e _ {rn} ( u) \geq  2 \} .
 +
$$
  
In addition, for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681057.png" />, let
+
In addition, for any fixed $  t > 0 $,  
 +
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/q076810/q07681058.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( 0) \geq  1 \}  \rightarrow  0 ,
 +
$$
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681059.png" />, uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681060.png" /> (this is the condition of low intensity of the streams <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681061.png" />). Then in order that the finite-dimensional distributions of the process
+
as $  n \rightarrow \infty $,  
 +
uniformly in $  r $(
 +
this is the condition of low intensity of the streams $  e _ {rn} ( t) $).  
 +
Then in order that the finite-dimensional distributions 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/q076810/q07681062.png" /></td> </tr></table>
+
$$
 +
e _ {n} ( t)  = \sum_{r=1}^ { n }  e _ {rn} ( t)
 +
$$
  
converge to the distributions of a Poisson process with drift function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681063.png" />, it is necessary and sufficient that as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681064.png" />,
+
converge to the distributions of a Poisson process with drift function $  A ( t) $,  
 +
it is necessary and sufficient that as $  n \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/q076810/q07681065.png" /></td> </tr></table>
+
$$
 +
A _ {n} ( t , u )  \rightarrow  A ( t) - A ( u) ,\  B _ {n} ( t , u )  \rightarrow  0 .
 +
$$
  
If in the triangular array under discussion the processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681066.png" /> and are single, then the following result also holds. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681067.png" /> be the intensity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681068.png" /> and, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681069.png" />, let
+
If in the triangular array under discussion the processes $  e _ {rn} ( t) \in G _ {IS} $
 +
and are single, then the following result also holds. Let $  u _ {rn} $
 +
be the intensity of $  e _ {rn} ( t) $
 +
and, as $  n \rightarrow \infty $,  
 +
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/q076810/q07681070.png" /></td> </tr></table>
+
$$
 +
\sum_{r=1}^ { n }  \mu _ {rn}  \rightarrow  \alpha .
 +
$$
  
Then for the convergence of the finite-dimensional distributions of the processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681071.png" /> to a distribution of a Poisson process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681072.png" /> with parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681073.png" /> it is necessary and sufficient that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681074.png" />,
+
Then for the convergence of the finite-dimensional distributions of the processes $  e _ {n} ( t) $
 +
to a distribution of a Poisson process $  e ( t) $
 +
with parameter $  \alpha $
 +
it is necessary and sufficient that for each $  t $,
  
<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/q076810/q07681075.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
\sum_{r=1}^ { n }  \mu _ {rn} \int\limits _ { 0 } ^ { t }  \phi _ {0}  ^ {(r)} ( u) d u  \rightarrow  \alpha t ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681076.png" /> is the Palm function for the process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681077.png" />, defined by (1). If, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681078.png" />,
+
where $  \phi _ {0}  ^ {r} ( u) $
 +
is the Palm function for the process $  e _ {rn} ( t) $,  
 +
defined by (1). If, as $  n \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/q076810/q07681079.png" /></td> </tr></table>
+
$$
 +
( 1 - \phi _ {0}  ^ {(r)} ( t) )  \rightarrow  0 ,
 +
$$
  
uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681080.png" />, then (2) is obviously satisfied.
+
uniformly in $  r $,  
 +
then (2) is obviously satisfied.
  
 
For references see [[Queueing theory|Queueing theory]].
 
For references see [[Queueing theory|Queueing theory]].

Latest revision as of 19:56, 18 January 2024


A random process given in some form or other and describing the appearance of calls in the queue. The input stream is usually defined by random sequences $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} $, where $ \tau _ {j} ^ {e} $, $ j = 1 , 2 \dots $ are the time intervals between the arrivals in the system of the batches of requests of sizes $ \nu _ {1} ^ {e} \geq 1 , \nu _ {2} ^ {e} \geq 1 \dots $ respectively. If $ \nu _ {j} ^ {e} \equiv 1 $, the stream is called single. Equivalently, the input stream can be given by a point process $ \{ {e ( t) } : {t \geq 0 } \} $, giving the number of calls arriving in the system up to time $ t $. It can be assumed, for the sake of being specific, that $ e ( t) = e ( t - 0 ) $.

The most common requirement usually placed on the input stream is stationarity. This condition can be of two kinds: either stationarity in the narrow sense is required of the sequence $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} $( denoted by $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} \in G _ {S} $), or it is required that $ e ( t) $ be a process with increments that are stationary in the narrow sense (denoted by $ \{ e ( t) \} \in G _ {IS} $). These requirements, in general, do not coincide (cf. Stationary stochastic process).

The intensity of a stationary stream is the number

$$ \mu = \lim\limits _ {t \rightarrow \infty } \ \frac{ {\mathsf E} ( e ( t) - e ( 0) ) }{t} . $$

If $ \{ e ( t) \} \in G _ {IS} $, then

$$ \mu = {\mathsf E} ( e ( t + 1 ) - e ( t) ) = \ {\mathsf E} ( e ( 1) - e ( 0) ) , $$

so that $ \mu $ is equal to the mean number of calls which arrive in the system in unit time. If the sequence $ \{ \tau _ {j} ^ {e} \} $ is stationary and ergodic and if $ \{ \nu _ {j} ^ {e} \} \in G _ {I} $, then

$$ \mu = \ \frac{ {\mathsf E} \nu _ {j} ^ {e} }{ {\mathsf E} \tau _ {j} ^ {e} } . $$

In other cases the relation between $ \mu $ and the distribution of the sequence $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} \in G _ {S} $ can be more complicated.

Let there be given a process $ \{ e ( t) \} \in G _ {IS} $ with intensity $ \mu $ and initial value $ e ( 0) = 0 $. Closely associated with the number $ \mu $ is another parameter of the input stream, defined by

$$ \alpha = \lim\limits _ {t \rightarrow 0 } \ \frac{ {\mathsf P} ( e ( t) \geq 1 ) }{t} . $$

This limit always exists and $ \alpha \leq \mu $. If $ \mu < \infty $, then $ \alpha = \mu $ if and only if the input stream is single.

In studying the properties of the input stream one often uses the so-called Palm functions

$$ \tag{1 } \phi _ {k} ( t) = \ \lim\limits _ {\tau \rightarrow 0 } \ \frac{ {\mathsf P} \{ e ( t + \tau ) - e ( \tau ) = k , e ( \tau ) \geq 1 \} }{ {\mathsf P} \{ e ( \tau ) \geq 1 \} } , $$

$$ k = 0 , 1 ,\dots $$

(here $ e ( 0) = 0 $), which have the meaning of the conditional probabilities that $ k $ calls arrive in the interval $ ( 0 , t ) $ under the condition that a call has arrived at time $ 0 $. The function $ \phi _ {k} ( t) $ is related to the distribution of $ e ( t) $ by:

$$ {\mathsf P} \{ e ( t) = 0 \} = 1 - \lambda \int\limits _ { 0 } ^ { t } \phi _ {0} ( u) d u , $$

$$ {\mathsf P} \{ e ( t) = k \} = \lambda \int\limits _ { 0 } ^ { t } [ \phi _ {k-1} ( u) - \phi _ {k} ( u) ] d u . $$

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, then

$$ \phi _ {0} ( t) = {\mathsf P} \{ \tau _ {j} ^ {e} \geq t \} , $$

$$ \sum_{j=0}^ { k } \phi _ {j} ( t) = {\mathsf P} \{ \tau _ {1} ^ {e} + \dots + \tau _ {k+1} ^ {e} \geq t \} . $$

A significant role in queueing theory is played by the so-called simplest, or Poisson, input stream — a stationary input stream for which $ \nu _ {j} ^ {e} = 1 $, $ \{ \tau _ {j} ^ {e} \} \in E $. In order to define the simplest stream in terms of $ e ( t) $ it is required that $ \{ e ( t) \} $ be Poisson (cf. Poisson process). The increments of this process in disjoint time intervals are independent and have Poisson distributions with parameters proportional to the length of the intervals.

Non-homogeneous Poisson streams also find broad application (particularly in telephony); these are characterized as processes $ e ( t) $ with independent increments distributed by the Poisson law:

$$ {\mathsf P} \{ e ( t + u ) - e ( t) = k \} = $$

$$ = \ \frac{e ^ {- A ( t + u ) - A ( t) } }{k!} ( A ( t + u ) - A ( t) ) ^ {k} , $$

where $ A ( t) $ is the drift function of the process (in the homogeneous case $ A ( t) = \alpha t $).

The special role of Poisson processes in queueing theory is explained in many respects by the fundamental limit theorem for input streams, which asserts that under broad assumptions the sum of a large number of arbitrary independent stationary input streams of low intensity converges to a Poisson process. The frequent use of the assumption that the input flow is Poisson rests on the fact that in many applications real input streams are formed in precisely that way (for example, the stream of calls arriving at a telephone exchange is the sum of the weak streams originating from the individual subscribers).

Below, the fundamental limit theorem is given in two forms. The first relates to the sum of arbitrary (non-stationary) input streams.

Suppose one is given increasing sets of independent process $ e _ {1n} ( t) \dots e _ {nn} ( t) $, $ n = 1 , 2 \dots $ depending on $ n $( that is, a triangular array), and the following notation:

$$ A _ {n} ( t , u ) = \ \sum_{r=1}^ { n } {\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( u) \geq 1 \} , $$

$$ B _ {n} ( t , u ) = \sum_{r=1}^ { n } {\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( u) \geq 2 \} . $$

In addition, for any fixed $ t > 0 $, let

$$ {\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( 0) \geq 1 \} \rightarrow 0 , $$

as $ n \rightarrow \infty $, uniformly in $ r $( this is the condition of low intensity of the streams $ e _ {rn} ( t) $). Then in order that the finite-dimensional distributions of the process

$$ e _ {n} ( t) = \sum_{r=1}^ { n } e _ {rn} ( t) $$

converge to the distributions of a Poisson process with drift function $ A ( t) $, it is necessary and sufficient that as $ n \rightarrow \infty $,

$$ A _ {n} ( t , u ) \rightarrow A ( t) - A ( u) ,\ B _ {n} ( t , u ) \rightarrow 0 . $$

If in the triangular array under discussion the processes $ e _ {rn} ( t) \in G _ {IS} $ and are single, then the following result also holds. Let $ u _ {rn} $ be the intensity of $ e _ {rn} ( t) $ and, as $ n \rightarrow \infty $, let

$$ \sum_{r=1}^ { n } \mu _ {rn} \rightarrow \alpha . $$

Then for the convergence of the finite-dimensional distributions of the processes $ e _ {n} ( t) $ to a distribution of a Poisson process $ e ( t) $ with parameter $ \alpha $ it is necessary and sufficient that for each $ t $,

$$ \tag{2 } \sum_{r=1}^ { n } \mu _ {rn} \int\limits _ { 0 } ^ { t } \phi _ {0} ^ {(r)} ( u) d u \rightarrow \alpha t , $$

where $ \phi _ {0} ^ {r} ( u) $ is the Palm function for the process $ e _ {rn} ( t) $, defined by (1). If, as $ n \rightarrow \infty $,

$$ ( 1 - \phi _ {0} ^ {(r)} ( t) ) \rightarrow 0 , $$

uniformly in $ r $, then (2) is obviously satisfied.

For references see Queueing theory.

How to Cite This Entry:
Queue input stream of calls. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Queue_input_stream_of_calls&oldid=12417
This article was adapted from an original article by A.A. Borovkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article