STOCHASTIC PROCESSES Theory for Applications Draft R G Gallager February 8 2012 i ii Preface This text has evolved over some 20 years starting as lecture notes for two first year graduate subjects at M I T namely Discrete Stochastic Processes 6 262 and Random Processes Detection and Estimation 6 432 The two sets of notes are closely related and have been integrated into one text Instructors and students can pick and choose the topics that meet their needs and a table of prerequisite topics is included to help in this choice These subjects originally had an application emphasis the first on queueing and congestion in data networks and the second on modulation and detection of signals in the presence of noise As the notes have evolved it has become increasingly clear that the mathematical development with minor enhancements is applicable to a much broader set of applications in engineering operations research physics biology economics finance statistics etc The field of stochastic processes is essentially a branch of probability theory treating probabilistic models that evolve in time It is best viewed as a branch of mathematics starting with the axioms of probability and containing a rich and fascinating set of results following from those axioms Although the results are applicable to many applications they are best understood in terms of their mathematical structure and interrelationships Applying axiomatic probability results to a real world area requires creating a probabiity model for the given area Mathematically precise results can then be derived within the model and translated back to the real world If the model fits the area sufficiently well real problems can be solved by analysis within the model Models are almost always simplified approximations of reality however so precise results within the model become approximations in the real world Choosing an appropriate probability model is an essential part of this process Sometimes an application area will have customary choices of models or at least structured ways of selecting them For example there is a well developed taxonomy of queueing models A sound knowledge of the application area combined with a sound knowledge of the behavior of these queueing models often lets one choose a suitable model for a given issue within the application area In other cases one can start with a particularly simple model and use the behavior of that model to gain insight about the application issue and use this to iteratively guide the selection of more general models An important aspect of choosing a probability model for a real world area is that a prospective choice depends heavily on prior understanding at both an intuitive and mathematical level of results from the range of mathematical models that might be involved This partly explains the title of the text Theory for applications The aim is to guide the reader in both the mathematical and intuitive understanding necessary in developing and using stochastic process models in studying application areas Application oriented students often ask why it is important to understand axioms theorems and proofs in mathematical models when the applied results are approximate anyway One answer is that we cannot reason with approximations if we don t know how to reason with the quantities being approximated Given the need for precision in the theory however why is an axiomatic approach needed iii I tried to avoid axiomatics in these notes for many years simply stating and explaining the major results Engineering and science students learn to use calculus linear algebra and undergraduate probability e ectively without axioms or rigor Why doesn t this work for more advanced probability and stochastic processes Probability theory has more than its share of apparent paradoxes and these show up in very elementary arguments Undergraduates are content with this since they can postpone these questions to later study Graduate students however usually want a foundation that provides understanding without paradoxes and the axioms achieve this I have tried to avoid the concise and formal proofs of pure mathematics and instead use explanations that are longer but more intuitive while still being precise This is partly to help students with limited exposure to pure math and partly because intuition is vital when going back and forth between a mathematical model and a real world problem In doing research we grope toward results and successful groping requires both a strong intuition and precise reasoning The text neither uses nor develops measure theory Measure theory is undoubtedly important in understanding probability at a deep level but most of the topics useful in many applications can be understood without measure theory I believe that the level of precision here provides a good background for a later study of measure theory The text does require some background in probability at an undergraduate level Chapter 1 presents this background material as review but it is too concentrated and deep for most students without prior background Some exposure to linear algebra and analysis especially concrete topics like vectors matrices and limits is helpful but the text develops the necessary results The most important prerequisite is the mathematical maturity and patience to couple precise reasoning with intuition The organization of the text after the review in Chapter 1 is as follows Chapters 2 3 and 4 treat three of the simplest and most important classes of stochastic processes first Poisson processes next Gaussian processes and finally finite state Markov chains These are beautiful processes where almost everything is known and they contribute insights examples and initial approaches for almost all other processes Chapter 5 then treats renewal processes which generalize Poisson processes and provide the foundation for the rest of the text Chapters 6 and 7 use renewal theory to generalize Markov chains to countable state spaces and continuous time Chapters 8 and 10 then study decision making and estimation which in a sense gets us out of the world of theory and back to using the theory Finally Chapter 9 treats random walks large deviations and martingales and illustrates many of their applications Most results here are quite old and well established so I have not made any e ort to attribute results to investigators My treatment of the material is indebted to Bertsekas and Tsitsiklis s book Elementary