WIXLIB

Introduction toProbability ModelsNinth Edition

This page intentionally left blank

Introduction toProbability ModelsNinth EditionSheldon M. RossUniversity of CaliforniaBerkeley, CaliforniaAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PARIS SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOAcademic Press is an imprint of Elsevier

Acquisitions EditorProject ManagerMarketing ManagersCover DesignCompositionCover PrinterInterior PrinterTom SingerSarah M. HajdukLinda Beattie, Leah AckersonEric DeCiccoVTEXPhoenix ColorThe Maple-Vail Book Manufacturing GroupAcademic Press is an imprint of Elsevier30 Corporate Drive, Suite 400, Burlington, MA 01803, USA525 B Street, Suite 1900, San Diego, California 92101-4495, USA84 Theobald’s Road, London WC1X 8RR, UK This book is printed on acid-free paper. Copyright 2007, Elsevier Inc. All rights reserved.No 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 publisher.Permissions may be sought directly from Elsevier’s Science & Technology RightsDepartment in Oxford, UK: phone: ( 44) 1865 843830, fax: ( 44) 1865 853333,E-mail: permissions@elsevier.com. You may also complete your request on-linevia the Elsevier homepage (http://elsevier.com), by selecting “Support & Contact”then “Copyright and Permission” and then “Obtaining Permissions.”Library of Congress Cataloging-in-Publication DataApplication 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 publicationsvisit our Web site at www.books.elsevier.comPrinted in the United States of America06 07 08 09 109 8 7 654321

ContentsPreface xiii1. Introduction to Probability Theory 11.1.1.2.1.3.1.4.1.5.1.6.Introduction 1Sample Space and Events 1Probabilities Defined on Events 4Conditional Probabilities 7Independent Events 10Bayes’ Formula 12Exercises 15References 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.2.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 37v

viContents2.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 83Exercises 85References 963. Conditional Probability and ConditionalExpectation 973.1.3.2.3.3.3.4.Introduction 97The Discrete Case 97The Continuous Case 102Computing Expectations by Conditioning 1053.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, Polya’s 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 164Exercises 165

Contents4. Markov Chains ntroduction 185Chapman–Kolmogorov Equations 189Classification of States 193Limiting Probabilities 204Some 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 224Mean Time Spent in Transient States 230Branching Processes 233Time Reversible Markov Chains 236Markov Chain Monte Carlo Methods 247Markov Decision Processes 252Hidden 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 Poisson Process 3025.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 343vii

viiiContentsExercises 346References 3646. Continuous-Time Markov Chains 3656.1.6.2.6.3.6.4.6.5.6.6.6.7.6.8.Introduction 365Continuous-Time Markov Chains 366Birth and Death Processes 368The Transition Probability Function Pij (t) 375Limiting Probabilities 384Time Reversibility 392Uniformization 401Computing the Transition Probabilities 404Exercises 407References 4157. Renewal Theory and Its Applications uction 417Distribution of N (t) 419Limit Theorems and Their Applications 423Renewal Reward Processes 433Regenerative Processes 4427.5.1. Alternating Renewal Processes 445Semi-Markov Processes 452The Inspection Paradox 455Computing the Renewal Function 458Applications to Patterns 4617.9.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 471The 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 496

Contents8.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. Erlang’s 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 608ix

xContents9.7. Systems with Repair 6109.7.1. A Series Model with Suspended Animation 615Exercises 617References 62410. Brownian Motion and Stationary Processes 62510.1. Brownian Motion 62510.2. Hitting Times, Maximum Variable, and the Gambler’s RuinProblem 62910.3. Variations on Brownian Motion 63110.3.1. Brownian Motion with Drift 63110.3.2. Geometric Brownian Motion 63110.4. Pricing Stock Options 63210.4.1. An Example in Options Pricing 63210.4.2. The Arbitrage Theorem 63510.4.3. The Black-Scholes Option Pricing Formula 63810.5. White Noise 64410.6. Gaussian Processes 64610.7. Stationary and Weakly Stationary Processes 64910.8. Harmonic Analysis of Weakly Stationary Processes 654Exercises 657References 66211. Simulation 66311.1. Introduction 66311.2. General Techniques for Simulating Continuous RandomVariables 66811.2.1. The Inverse Transformation Method 66811.2.2. The Rejection Method 66911.2.3. The Hazard Rate Method 67311.3. Special Techniques for Simulating Continuous RandomVariables 67711.3.1. The Normal Distribution 67711.3.2. The Gamma Distribution 68011.3.3. The Chi-Squared Distribution 68111.3.4. The Beta (n, m) Distribution 68111.3.5. The Exponential Distribution—The Von NeumannAlgorithm 68211.4. Simulating from Discrete Distributions 68511.4.1. The Alias Method 688

Contents11.5. Stochastic Processes 69211.5.1. Simulating a Nonhomogeneous Poisson Process 69311.5.2. Simulating a Two-Dimensional Poisson Process 70011.6. Variance Reduction Techniques 70311.6.1. Use of Antithetic Variables 70411.6.2. Variance Reduction by Conditioning 70811.6.3. Control Variates 71211.6.4. Importance Sampling 71411.7. Determining the Number of Runs 72011.8. Coupling from the Past 720Exercises 723References 731Appendix: Solutions to Starred Exercises 733Index 775xi

This page intentionally left blank

PrefaceThis text is intended as an introduction to elementary probability theory and stochastic processes. It is particularly well suited for those wanting to see how probability theory can be applied to the study of phenomena in fields such as engineering, computer science, management science, the physical and social sciences, andoperations research.It is generally felt that there are two approaches to the study of probability theory. One approach is heuristic and nonrigorous and attempts to develop in thestudent an intuitive feel for the subject which enables him or her to “think probabilistically.” The other approach attempts a rigorous development of probabilityby using the tools of measure theory. It is the first approach that is employed inthis text. However, because it is extremely important in both understanding andapplying probability theory to be able to “think probabilistically,” this text shouldalso be useful to students interested primarily in the second approach.New to This EditionThe ninth edition contains the following new sections. Section 3.7 is concerned with compound random variables of the formSN Ni 1 Xi , where N is independent of the sequence of independent andidentically distributed random variables Xi , i 1. It starts by deriving a general identity concerning compound random variables, as well as a corollaryof that identity in the case where the Xi are positive and integer valued. Thecorollary is then used in subsequent subsections to obtain recursive formulasfor the probability mass function of SN , when N is a Poisson distribution(Subsection 3.7.1), a binomial distribution (Subsection 3.7.2), or a negativebinomial distribution (Subsection 3.7.3).xiii