Introduction to Probability ModelsIntroduction toProbability ModelsNinth editionSheldon m. rossity of CalifoBerkeley, californiaAMSTERDAM· BOSTON· HEIDELBERG· LONDONNEW YORK· OXFORD· PARIS· SAN DIEGOSAN FRANCISCO· SINGAPORE· SYDNEY· TOKYOELSEVIERAcademic Press is an imprint of elsevierAcquisitions editorTom SingerProject ManagerSarah M. hajdukMarketing managers Linda beattie, Leah AckersonCover designEric deciccoCompositionⅤTEXCover printerPhoenix colorInterior printerThe Maple-Vail Book Manufacturing GroupAcademic Press is an imprint of elsevier30 Corporate Drive, Suite 400, Burlington, MA O1803, USA525 B Street, Suite 1900, San Diego, California 92101-4495, USA84 Theobald,s road. London wciX 8RR. UKThis book is printed on acid-free paper.Copyright@ 2007, Elsevier Inc. All rights reservedNo part of this publication may be reproduced or transmitted in any form or by anymeans,electronic or mechanical, including photocopy, recording, or any informationstorage and retrieval system, without permission in writing from the publisherPermissions may be sought directly from Elsevier's Science Technology RightsDepartment in Oxford, UK: phone: (+44)1865 843830, fax: (+44 )1865 853333E-mail:permissions@elsevier.com.Youmayalsocompleteyourrequeston-lineviatheelsevierhomepage(http://elsevier.com),byselecting"support&Contactthen"Copyright and Permission,and then"Obtaining PermissionsLibrary of Congress Cataloging-in-Publication Datapplication SubmittedBritish library cataloguing-in-Publication DataA catalogue record for this book is available from the British Library.ISBN-13:978-0-12-598062-3ISBN-10:0-12-598062-0For information on all academic Press publicationsvisitourwebsiteatwww.books.elseviercomPrinted in the united States of america060708091098765432ContentsPreface xiii1. Introduction to Probability Theory 11. Introduction 12. Sample space and events 11. 3. Probabilities defined on events 41. 4. Conditional probabilities 71. 5. Inddent events 101.6. Bayes Formula 12ErReferences 212. Random variables 232. 1. Random variables 232. 2. Discrete random Variables 272.2.1. The bernoulli random variable 282.2.2. The Binomial Random Variable 292.2.3. The Geometric Random variable 312. 4. The poisson random variable 322.3. Continuous random Variables 342.3.1. The Uniform random variable 352.3.2. Exponential Random variables 362. 3.3. Gamma Random Variables 372. 3. 4. Normal random variables 37Contents2.4. Expectation of a random variable 382.4.1. The Discrete Case 382. 4.2. The Continuous case 412.4.3. Expectation of a Function of a Random Variable 432.5. Jointly Distributed Random Variables 472.5.1. Joint distribution Functions 472.5.2. Independent Random Variables 512.5.3. Covariance and variance of Sums of random variables 532.5.4. Joint Probability Distribution of Functions of RandomVariables 612.6. Moment Generating Functions 642.6. 1. The Joint Distribution of the sample mean and sampleVariance from a Normal Population 742.7. Limit Theorems 772. 8. Stochastic Processes 83Exerc85References 963. Conditional Probability and ConditionalExpectation 973.1. Introduction 973.2. The Discrete Case 973. 3. The Continuous case 1023.4. Computing Expectations by Conditioning 10.53.4.1. Computing Variances by Conditioning 1173.5. Computing Probabilities by Conditioning 1203.6. Some Applications 1373.6.1. A List model 1373.6.2. A Random graph 1393.6.3. Uniform Priors, Polyas Urn Model, andBose-Einstein statistics 1473. 6. 4. Mean Time for Patterns 1513.6.5. The k-Record Values of Discrete Random variables 1553.7. An Identity for Compound random variables 1583.7.1. Poisson Compounding Distribution 1613.7.2. Binomial Compounding distribution 1633.7.3. A Compounding distribution related to the NegativeBinomial 16 4Exercises 1654. Markov Chains 1854.1. Introduction 1854.2. Chapman-Kolmogorov Equations 1894.3. Classification of States 1934. 4. Limiting probabilities 2044.5. Some Applications 2174.5.1. The gambler,s ruin problem 2174.5.2. A Model for Algorithmic Efficiency 2214.5.3. USing a Random Walk to Analyze a Probabilistic algorithmfor the satisfiability Problem 2244.6. Mean Time Spent in Transient States 2304.7. Branching Processes 2334. 8. Time Reversible markov Chains 2364.9. Markov Chain Monte Carlo methods 2474.10. Markov decision processes 252411. Hidden markov chains 2564.11.1. Predicting the States 261Exercises 263References 2805. The Exponential Distribution and the poissonProcess 2815.1. Introduction 2815.2. The Exponential Distribution 2825.2.1. Definition 2825.2.2. Properties of the Exponential Distribution 2845.2.3. Further Properties of the exponential Distribution 2915.2.4. Convolutions of Exponential Random Variables 2985.3. The poi305.3. 1. Counting Processes 3025.3.2. Definition of the poisson process 3045.3.3. Interarrival and Waiting Time distributions 3075.3. 4. Further Properties of Poisson Processes 3105.3.5. Conditional Distribution of the arrival Times 3165.3.6. Estimating Software Reliability 3285.4. Generalizations of the poisson process 3305.4.1. Nonhomogeneous poisson process 3305.4.2. Compound poisson Process 3375.4.3. Conditional or Mixed Poisson Processes 3431l ContentsExercises 346References 3646. Continuous-Time markov Chains 3656.1. Introduction 3656.2. Continuous-Time markov Chains 3666.3. Birth and Death Processes 3686. 4. The Transition Probability Function Pii (t)3756.5. Limiting Probabilities 3846. 6. Time Reversibility 3926.7. Uniformization 4016. 8. Computing the Transition Probabilities 404Exercises 407References 4157. Renewal Theory and Its Applications 4177. 1. Introduction 4177. 2. Distribution of N(t)4197.3. Limit Theorems and Their Applications 4237. 4. Renewal reward Processes 4337.5. Regenerative Processes 4427.5.I. Alternating renewal Processes 4457. 6. Semi-Markoy Processes 4527.7. The Inspection Paradox 4557.8. Computing the renewal Function 4587.9. Applications to patterns 4617. 1. Patterns of Discrete Random Variables 4627.9.2. The Expected Time to a Maximal Run of Distinct Values 4697.9.3. Increasing Runs of Continuous random Variables 4717.10. The Insurance ruin Problem 473Exercises 479References 4928. Queueing Theory 4938.1. Introduction 4938. 2. Preliminaries 4948.2. 1. Cost Equations 4958.2.2. Steady-State Probabilities 4968.3. Exponential Models 4998.3.1. A Single-Server Exponential Queueing System 4998.3.2. A Single-Server Exponential Queueing systemHaving Finite Capacity 5088.3.3. A Shoeshine Shop 5118.3. 4. A Queueing System with Bulk Service 5148.4. Network of Queues 5178.4.1. Open Systems 5178.4.2. Closed Systems 5228.5. The System M/G/1 5288.5.1. Preliminaries: Work and another Cost identity 5288.5.2. Application of Work to M/G/1 5298.5.3. Busy Periods 5308.6. Variations on the M/G/1 5318.6.1. The M/G/1 with Random-Sized Batch Arrivals 5318.6.2. Priority Queues 5338.6.3. An M/G/1 Optimization Example 5368.6.4. The M/G/1 Queue with Server Breakdown 5408.7. The Model G/M/1 5438.7.1. The G/M/1 Busy and Idle Periods 5488.8. A Finite Source Model 5498.9. Multiserver Queues 5528.9.1. Erlangs Loss system 5538.9.2. The M/M/k Queue 5548.9.3. The G/M/ k Queue 5548.9.4. The M/G/k Queue 556Exercises 558References 5709. Reliability Theory 5719.1. Introduction 5719.2. Structure Functions 5719.2.1. Minimal Path and minimal Cut Sets 5749.3. Reliability of Systems of Independent Components 5789. 4. Bounds on the reliability Function 5839.4.1. Method of Inclusion and Exclusion 5849.4.2. Second Method for Obtaining Bounds on r(p) 5939. 5. System Life as a Function of Component Lives 5959.6. Expected System Lifetime 6049.6. 1. An Upper Bound on the Expected Life of aParallel System 608