Preface

Purpose. There has been considerable interest in sample-path analysis in recent years on the part of researchers and professionals working in stochastic processes and their applications. This book uses a deterministic (sample-path) approach to analyze stochastic systems, primarily queueing systems and more general input-output systems. It deals with establishing fundamental relations between asymptotic frequencies and averages, pathwise stability, and insensitivity, among other topics of interest. These results are utilized to establish useful performance measures. We believe that the intuitive deterministic approach of this book will be beneficial to researchers and practitioners, who will gain better insights into many questions in queueing theory, and to teachers and students, who will appreciate the simplicity and intuitive appeal of the arguments.

Features. A distinctive feature of this book is that it consistently takes the point of view of focusing on one sample path of a stochastic process. That is, it is devoted to providing {\em pure} sample-path arguments. With this approach it is possible to separate the issue of the validity of a relationship from issues of existence of limits and/or construction of stationary framework. In many cases of interest in queueing theory relations hold quite generally assuming limits exist, and the proofs are elementary and intuitive. On the other hand, proofs of the existence of limits (almost surely) require the heavy machinery of stochastic processes, such as the approach based on the theory of regenerative processes or stationary marked point processes. This book also covers recent topics such as pathwise stability.

Problems Studied. Sample-path analysis has been quite effective in proving establishing fundamental results such as relationships between time and point averages in a general setting. Examples include a pathwise version of the renewal-reward theorem, Little's formula ($L = \lambda W$) and its extension $H=\lambda G$, mean-value analysis, the covariance formula, the arrivals-see-time-average property ({\em ASTA}), sample-path versions of the rate-conservation principle, the global balance conditions, and various relations between time-average state frequencies and frequencies at the points of an imbedded point process. It has also been successful in providing complete and pure pathwise arguments in the case of rate stability and backward/forward recurrence times.

Proofs. Sample-path proofs are delicate and sometimes their simplicity is misleading. In a sample-path setting one works with fewer assumptions than in the corresponding stochastic framework. One therefore has limited resources to utilize in the proof. Moreover, because we focus one focuses on a particular sample path, we have one has to examine carefully all sorts of pathological and strange behaviors before insuring the validity of the argument. Once a sample-path proof is constructed, however, it tends to be for the most part simple, intuitive, and elegant: a good return on one's investment of time and effort.

Relation to Stochastic Approach. In many cases it is possible to provide pure pathwise results. In other cases one can provide a sample-path intermediate result, then invoke an appropriate ergodic theorem to complete the analysis. In such cases we advocate pushing sample-path arguments as far as possible before resorting to stochastic analysis. The advantages of this approach are clear: the sample-path arguments are simple and intuitive; thus they provide a clear insight into the issues at hand. Sample-path analysis helps pinpoint why and when stochastic arguments are needed. Typically stochastic analysis is required to construct stationary versions of the process in question and to ensure that the appropriate limits are well defined. At the sample-path level we focus on one realization of the underlying stochastic process, so the construction of a stationary stochastic version becomes irrelevant. Our approach is to assume the relevant limits are well defined on the sample path in question and then trace out the implications of this assumption. The fewer the assumptions one makes, the more general the results tend to be. General results have wider applicability, but they may not be useful in solving a particular problem. One should not expect sample-path analysis to be instructive in providing results where a stochastic condition is crucial to obtaining a result (such as the stationary distribution in an {\em M/M/1} queue). Making stochastic assumptions provides the analyst with more tools with which to construct a proof. In summary, we recommend use of sample-path analysis to provide general results that are independent of stochastic assumptions, complemented by use of probabilistic arguments to carry out a more detailed analysis. This book focuses on the first part of the picture. It does however, provide numerous examples that invoke stochastic assumptions. (These are typically presented at the end of a chapter.)

Organization. This book contains eight chapters and three appendices. Chapter 1 provides an introductory survey of some basic sample-path properties of queueing models at an elementary level. Topics include Little's formula, imbedded properties of input-output processes, busy period analysis, and conditional properties of queues. (These topics are revisited at a more advanced level in subsequent chapters. Readers familiar with queueing theory who wish to move directly to more general models and results may omit this chapter.) Chapter 2 contains a collection of fundamental results that are needed in the rest of the book. It discusses in detail the relation $Y=\lambda X$, which is a pathwise version or the renewal-reward theorem. It also covers cumulative processes and the rate conservation law, among other topics. Chapter 3 deals with a process with a general state space and an imbedded point process, with applications to the {\em G/G/1} queue and a martingale proof of {\em ASTA}. Chapter 4 specializes the topics of Chapter 3 to the case of a countable state space, with applications to networks of queues, one-dimensional processes, and numerous examples. The relationships discussed in Chapters 3 and 4 are applicable to a wide range of discrete-event dynamic systems. Chapter 5 deals with pathwise rate stability in the context of a general input-output system, with applications to single-server and multiple-server queues, among others. It also discuses several other notions of pathwise stability and the connections among them. Chapter 6 discuses Little's formula ($L = \lambda W$) and its generalization $H=\lambda G$. It also contains discussion of fluid versions of these relations under minimal conditions. Chapter 7 proves the insensitivity phenomenon (i.e., the property that the queue-length distribution is independent of the service-time distribution) for the infinite-server queue, the Erlang loss model, and a round-robin model in discrete time. Chapter 8 extends the basic relations in Chapters 3 and 4 to the multi-dimensional case by providing a sample-path approach to Palm calculus. Results include the Palm inversion formula and Neveu's exchange formulas. Appendix A contains a brief introduction to the strong law of large numbers and other ergodic theorems that are useful when it becomes necessary invoke stochastic assumptions in the context of stationary processes and random marked point processes. Appendix B reviews limit theorems from Markov and regenerative processes. Appendix C contains a survey of different concepts of stability in stochastic models.

Prerequisites. A basic course in probability and stochastic processes or queueing theory and some knowledge of calculus suffice for Chapters 1-7, with the exception of Section 3 in Chapter 3 on martingale {\em ASTA}, which requires knowledge of the basic elements of martingale theory. Chapter 8 requires more advanced background, perhaps familiarity with random marked point processes.