Queue with waiting and one service channel

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.