Sample-Path Analysis of Stochastic Discrete-Event Systems

Muhammad El-Taha, Department of Mathematics and Statistics, University of Southern Maine

Shaler Stidham, Jr., Department of Operations Research, University of North Carolina

Abstract

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 = l 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 the ASTA (Arrivals See Time Averages), conditional ASTA, and reversed ASTA 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 a G / G / 1 queue.