On a class of stochastic recursive sequences arising in queueing theory. (English) Zbl 0742.60095

Summary: This paper is concerned with a class of stochastic recursive sequences that arise in various branches of queueing theory. First, we make use of Kingman’s subadditive ergodic theorem to determine the stability region of this type of sequence, or equivalently, the condition under which they converge weakly to a finite limit. Under this stability condition, we also show that these sequences admit a unique finite stationary regime and that regardless of the initial condition, the transient sequence couples in finite time with this uniquely defined stationary regime. When this stability condition is not satisfied, we show that the sequence converges a.s. to \(\infty\) and that certain increments of the process form another type of stochastic recursive sequence that always admit at least one stationary regime. Finally, we give sufficient conditions for this increment sequence to couple with this stationary regime.


60K25 Queueing theory (aspects of probability theory)
05C20 Directed graphs (digraphs), tournaments
60F20 Zero-one laws
60G10 Stationary stochastic processes
60G17 Sample path properties
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68R10 Graph theory (including graph drawing) in computer science
93D05 Lyapunov and other classical stabilities (Lagrange, Poisson, \(L^p, l^p\), etc.) in control theory
93E03 Stochastic systems in control theory (general)
93E15 Stochastic stability in control theory
Full Text: DOI