Sample-path analysis of stochastic discrete-event systems

This paper presents a unified sample-path approach for deriving distribution-free relations between performance measures for stochastic discrete-event systems extending previous results for discrete-state processes to processes with a general state space. A unique feature of our approach is that all our results are shown to follow from a single fundamental theorem: the sample-path version of the renewal-reward theorem (Y=X). As an elementary consequence of this theorem, we derive a version of the rate-conservation law under conditions more general than previously given in the literature. We then focus on relations between continuous-time state frequencies and frequencies at the points of an imbedded point process, giving necessary and sufficient conditions for theASTA (Arrivals See Time Averages), conditionalASTA, and reversedASTA properties. In addition, we provide a unified approach for proving various relations involving forward and backward recurrence times. Finally, we give sufficient conditions for rate stability of an input-output system and apply these results to obtain an elementary proof of the relation between the workload and attained-waiting-time processes in aG/G/l queue.Research was partially supported by the National Science Foundation under Grant no. DDM-8719825. The government of the United States of America has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research of this author was also partially supported by a grant from Centre International des Étudiants et Stagiares (C.I.E.S.) while he was visiting INRIA, Sophia-Antipolis, Valbonne, France (1991–92).