View source for Queue input stream of calls

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" />.

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]]).

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>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681014.png" />, 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>

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

<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>

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.

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

<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>

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.

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>

<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 <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:

<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>

<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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681040.png" />, 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/q07681041.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/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 <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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681047.png" /> with independent increments distributed by the Poisson law:

<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>

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" />).

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 <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:

<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>

<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>

In addition, for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681057.png" />, 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>

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

<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>

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" />,

<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>

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

<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>

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" />,

<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>

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" />,

<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>

uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076810/q07681080.png" />, then (2) is obviously satisfied.

For references see [[Queueing theory|Queueing theory]].