Applied Probability and Stochastic Processes - …

1 Applied Probability and Stochastic ProcessesSecond EditionRichard M. Feldman Ciriaco Valdez-FloresApplied Probabilityand Stochastic ProcessesSecond Edition123 Richard M. FeldmanTexas A&M UniversityIndustrial and SystemsEngineering DepartmentCollege StationTexas Valdez-FloresSielken & AssociatesConsulting, Texas AvenueBryanTexas 978-3-642-05155-5e-ISBN 978-3-642-05158-6 DOI Heidelberg Dordrecht London New YorkLibrary of Congress Control Number: 2009940615 Originally published by PWS Publishing/Thomson Publishing, USA, 1995c Springer-Verlag Berlin Heidelberg 2010 This work is subject to copyright. All rights are reserved, whether the whole or part of the material isconcerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,reproduction on microfilm or in any other way, and storage in data banks.

2 Duplication of this publicationor parts thereof is permitted only under the provisions of the German Copyright Law of September 9,1965, in its current version, and permission for use must always be obtained from Springer. Violationsare liable to prosecution under the German Copyright use of general descriptive names, registered names, trademarks, etc. in this publication does notimply, even in the absence of a specific statement, that such names are exempt from the relevant protectivelaws and regulations and therefore free for general design:eStudio Calamar on acid-free paperSpringer is part of Springer Science+Business Media ( )This book is dedicated to our wives, AliceFeldman and Nancy Vivas-Valdez, whosepatience, love, and support keep us going andmake life book is a result of teaching Stochastic Processes to junior and senior undergrad-uates and beginning graduate students over many years.

3 In teaching such a course,we have realized a need to furnish students with material that gives a mathematicalpresentation while at the same time providing proper foundations to allow studentsto build an intuitive feel for probabilistic reasoning. We have tried to maintain a bal-ance in presenting advanced but understandable material that sparks an interest andchallenges students, without the discouragement that often comes as a consequenceof not understanding the material. Our intent in this text is to develop Stochastic pro-cesses in an elementary but mathematically precise style and to provide sufficientexamples and homework exercises that will permit students to understand the rangeof application areas for Stochastic also practice active learning in the classroom. In other words, we believe thatthe traditional practice of lecturing continuously for 50 to 75 minutes is not a veryeffective method for teaching.

4 Students should somehow engage in the subject mat-ter during the teaching session. One effective method for active learning is, after atmost 20 minutes of lecture, to assign a small example problem for the students towork and one important tool that the instructor can utilize is the computer. Some-times we are fortunate to lecture students in a classroom containing computers witha spreadsheet program, usually Microsoft s Excel. For a course dealing with randomvariables, Excel is an ideal tool that can be used both within the classroom and forhomework to demonstrate probabilistic concepts. In order to take full advantage ofthis, we have moved the chapter on simulation to the second chapter in the book. Itis not necessary to cover all the sections of the simulation chapter, but we suggestcovering at least Sects. and so that simulation can then be easily used withExcel throughout the course to demonstrate random Processes and used during thelecture to actively engage the students in the lecture only prerequisites for an undergraduate course using this textbook is a pre-vious course covering calculus-based Probability and statistics and familiarity withbasic matrix operations.

5 Included at the end of most chapters is an appendix cover-ing the use of Excel for the problems of the chapter; thus, a familiarity with ExcelviiviiiPrefacewould be helpful but not necessary. For students needing a review of matrices, someof the basic operations are given in Appendix A at the end of the book could also be used for an introductory course to Stochastic Processes atthe graduate level, in which case an additional prerequisite of linear programmingshould be required if the chapter on Markov decision theory is to be covered. Itwould also be helpful to expect graduate students to be competent programmers insome scientific programming language. There are two chapters covering advancedtopics that would be skipped in an undergraduate course: Chap. 12 Markov De-cision Theory and Chap. 13 Advanced Queueing Theory. Knowledge of lin-ear programming is necessary for Chap.

6 12, and a programming language or VBAwould be very helpful in implementing the concepts in Chap. book is organized as follows: The first three chapters are background mate-rial to be used throughout the book. The first chapter is a review of Probability . It isintended simply as a review; the material is too terse if students have not previouslybeen exposed to Probability . However, our experience is that most students do notlearn Probability until two or three exposures to it, so this chapter should serve asan excellent summary and review for most students. The second chapter is an in-troduction to simulation so that it can be used to demonstrate concepts covered infuture chapters. Included in this chapter is material covering random number gener-ation (Sect. ) which we sometimes skip when teaching our undergraduate coursein Stochastic Processes since Excel has its own generator.

7 The third chapter is a re-view of statistics which is only presented because some statistical concepts will becovered in later chapters, but this in not central to the text. We expect students tohave already been exposed to this material and we generally skip this chapter forour undergraduate course and refer to it as fourth chapter begins the introduction to random Processes and covers thebasic concepts of Poisson Processes . The fifth chapter covers Markov chains in somedetail. The approach in this chapter and in Chap. 6 is similar to the approach taken byC inlar (Introduction to Stochastic Processes , Prentice-Hall, 1975). The homeworkproblems cover a wide variety of modeling situations as an attempt is made to beginthe development of modelers . Chapter 6 is an introduction to continuous timeMarkov Processes . The major purpose of the chapter is to give the tools necessaryfor the development of queueing models; therefore, the emphasis in the chapter is onsteady-state analyses.

8 The final section of Chapter 6 is a brief treatment of the time-dependent probabilities for Markov Processes . This final section can be skipped formost undergraduate classes. Queueing theory is covered in Chaps. 7 and 8, whereChap. 7 deals with the basics of single queues and Chap. 8 introduces queueingnetworks. As in the Markov chain chapter, an attempt has been made to develop awide variety of modeling situations through the homework 9 has two sections: the first deals with the specifics of event-driven simu-lations while the second introduces some of the statistical issues for output the mechanical details of simulation (like future events lists) are not of interest tothe instructor, the first section of Chap. 9 can be skipped with no loss of 2 together with the second section of Chap. 9 should yield an excellent in-troduction to simulation.

9 No programming language is assumed since our purposePrefaceixis not to produce experts in simulation, but simply to introduce the concepts anddevelop student interest in simulation. If simulation is covered adequately by othercourses, Chap. 9 can be easily 10 and 11 introduce a change in tactics and present two chapters deal-ing with specific problem domains: the first is inventory and the second is replace-ment. Applied Probability can be taught as a collection of techniques useful for awide variety of applications, or it can be taught as various application areas forwhich randomness plays an important role. The first nine chapters focus on par-ticular techniques with some applications being emphasized through examples andthe homework problems. The next two chapters focus on two problem domains thathave been historically important in Applied Probability and Stochastic Processes .

10 Itwas difficult to decide on the proper location for these two chapters. There is someChapters 12 and 13 are only included for advanced students. Chapter 12 coversMarkov decision Processes , and Chap. 13 is a presentation of phase-type distribu-tions and the matrix geometric approach to queueing systems adopted from the workof Neuts (Matrix-Geometric Solutions in Stochastic Models, Johns Hopkins Univer-sity Press, 1981).We are indebted to many of our colleagues for their invaluable assistance andprofessional support. For this second edition, we especially thank Guy L. Curry andDon T. Phillips for their contributions and encouragement. We are also grateful toBrett Peters, the department head of Industrial and Systems Engineering at TexasA&M University, and to Robert L. Sielken of Sielken & Associates Consulting fortheir continuous support. Section and parts of Chap.