DISCRETE STOCHASTIC PROCESSESDraft of 2nd EditionR. G. GallagerJune 20, 2011iiiPrefaceThese notes are a draft of a major rewrite of a text [9] of the same name. The notes and thetext are outgrowths of lecture notes developed over some 20 years for the M.I.T. graduatesubject 6.262, entitled ‘Discrete Stochastic Processes.’ The original motivation for 6.262was to provide some of the necessary background for Electrical Engineering, ComputerScience, and Operations Research students working in the burgeoning field of computer-communication networks. Many of the most important and challenging problems in thisarea involve queueing and congestion, but the literature on queueing and congestion wasrapidly becoming so di↵use that a more cohesive approach was needed. Queuing problemsare examples of stochastic processes, and more particularly, discrete stochastic processes.Discrete stochastic processes form a cohesive body of study, allowing queueing and conges-tion problems to be discussed where they naturally arise.In the intervening years, it has become increasingly apparent that many problems involvinguncertainty in almost all branches of technology and human a↵airs provide interesting andimportant examples of discrete stochastic processes. Discussing these problems as they ariseboth increases the application domain of this subject and also enhances our intuition andunderstanding about the general principles.The purpose of this text is both to help students understand the general principles ofdiscrete stochastic processes, and to develop the understanding and intuition necessaryto apply stochastic process models to problems in engineering, science, and operationsresearch. Although the ultimate objective is applications, there is relatively little detaileddescription of real applications. Rather, there are many simple examples designed both tobuild insight about particular principles in stochastic processes and to illustrate the generice↵ect of these phenomena in real systems. I am convinced that the ”case study” method, inwhich many applications are studied in the absence of general principles, is inappropriatefor understanding stochastic processes (and similarly inappropriate for any field that has arich and highly cohesive mathematical structure).When we try to either design new kinds of systems or understand physical phenomena, weusually employ a variety of stochastic process models to gain understanding about di↵erenttradeo↵s and aspects of the problem. Creating these models requires deep understandingboth of the application area and of the structure of stochastic processes. The applicationareas are too broad, and the structure too deep, to do all this in one text. My experienceindicates that engineers rarely have difficulty applying well-understood theories and toolsto well-understood application areas. The difficulty comes when the theoretical structureis not understood on both an intuitive and mathematical level. The ”back of the envelopecalculations” that we so prize as engineers are the result of this deep understanding of bothapplication areas and conceptual structure.I try to present the structural aspects of stochastic processes in the simplest possible lighthere, thus helping readers develop insight. This requires somewhat more abstraction thanengineers are used to, but much less than often appears in mathematics texts. It alsorequires students to spend less time doing complex calculations and more time drawingillustrative diagrams and thinking. The proofs and explanations here are meant to be read,iiinot because students might doubt the result, but to enhance understanding. In order to usethese results in modeling real situations, the robustness of the results must be understoodat an intuitive level, and this is gained only by understanding why the results are true, andwhy they fail when the required conditions are unsatisfied.Students learn about new concepts in many ways, partly by learning facts, partly by doingexercises, and partly by successively refining an internal structural picture of what thesubject is about. The combination of all of these leads to understanding and the ability tocreate models for real problems. This ability to model, however, requires much more thanthe “plug and chug” of matching exercises to formulas and theorems. The ability to modelis based on understanding at an intuitive level, backed by mathematics.Stochastic processes is the branch of probability dealing with probabilistic systems thatevolve in time. By discrete stochastic processes, I mean processes in which changes occuronly at discrete times separated by either deterministic or random intervals. In particu-lar, we do not treat noise processes such as Gaussian processes. This distinction betweendiscrete and non-discrete processes is somewhat artificial, but is dictated by two practicalconsiderations. The first is that many engineering graduate students take a course involvingnoise, second moment theory, and inference (including detection and estimation) (the ma-terial in such subjects is more standard than the title). Such a course has much cohesion,fits nicely into one academic term, but has relatively little conceptual overlap with the ma-terial here. The second consideration is that extensions of the material here to continuousprocesses often obscure the probabilistic ideas with mathematical technicalities.The mathematical concepts here are presented without measure theory, but a little math-ematical analysis is required and developed as used. The material requires more patienceand more mathematical abstraction than many engineering students are used to, but thatis balanced by a minimum of ‘plug and chug’ exercises. If you find yourself writing manyequations in an exercise, stop and think, because there is usually an easier way. In the the-orems, proofs, and explanations, I have tried to favor simplicity over generality and clarityover conciseness (although this will often not be apparent on a first reading). I have pro-vided references rather than pro ofs for a number of important results where the techniquesin the proof will not be reused and provide little intuition. Numerous examples are givenshowing how results fail to hold when all the conditions are not satisfied. Understanding isoften as dependent on a collection of good counterexamples as on knowledge of theorems.In engineering, there is considerable latitude in generating mathematical mo dels