Introduction to Probability Models

1 Introduction toProbability ModelsNinth EditionThis page intentionally left blankIntroduction toProbability ModelsNinth EditionSheldon M. RossUniversity of CaliforniaBerkeley, CaliforniaAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PA R I S SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOA cademic Press is an imprint of ElsevierAcquisitions EditorTom SingerProject ManagerSarah M. HajdukMarketing ManagersLinda Beattie, Leah AckersonCover DesignEric DeCiccoCompositionVTEXC over PrinterPhoenix ColorInterior PrinterThe 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, UKThis book is printed on acid-free paper.

2 Copyright 2007, Elsevier Inc. All rights 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 may be sought directly from Elsevier s Science & Technology RightsDepartment in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333,E-mail: You may also complete your request on-linevia the Elsevier homepage ( ), 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 : 978-0-12-598062-3 ISBN-10: 0-12-598062-0 For information on all Academic Press publicationsvisit our Web site at in the United States of America0607080910 987654321 ContentsPreface xiii1.

3 Introduction to Probability Theory Introduction Sample Space and Events Probabilities Defined on Events Conditional Probabilities Independent Events Bayes Formula 12 Exercises 15 References 212. random Variables random Variables Discrete random Variables The Bernoulli random variable The Binomial random variable The Geometric random variable The Poisson random variable Continuous random Variables The Uniform random variable Exponential random Variables Gamma random Variables Normal random Variables Expectation of a random variable The Discrete Case The Continuous Case Expectation of a Function of a random variable Jointly Distributed random Variables Joint Distribution Functions Independent random Variables Covariance and

4 Variance of Sums of random Variables Joint Probability Distribution of Functions of RandomVariables Moment Generating Functions The Joint Distribution of the Sample Mean and SampleVariance from a Normal Population Limit Theorems stochastic processes 83 Exercises 85 References 963. Conditional Probability and ConditionalExpectation Introduction The Discrete Case The Continuous Case Computing Expectations by Conditioning Computing Variances by Conditioning Computing Probabilities by Conditioning Some Applications A List Model A random Graph Uniform Priors, Polya s Urn Model.

5 AndBose Einstein Statistics Mean Time for Patterns Thek-Record Values of Discrete random Variables An Identity for Compound random Variables Poisson Compounding Distribution Binomial Compounding Distribution A Compounding Distribution Related to the NegativeBinomial 164 Exercises 165 Contentsvii4. Markov Chains Introduction Chapman Kolmogorov Equations Classification of States Limiting Probabilities Some Applications The Gambler s Ruin Problem A Model for Algorithmic Efficiency Using a random Walk to Analyze a Probabilistic Algorithmfor the Satisfiability Problem Mean Time Spent in Transient States Branching processes Time Reversible Markov Chains Markov Chain Monte Carlo Methods Markov Decision processes Hidden Markov Chains Predicting the States 261 Exercises 263 References 2805.

6 The Exponential Distribution and the PoissonProcess Introduction The Exponential Distribution Definition Properties of the Exponential Distribution Further Properties of the Exponential Distribution Convolutions of Exponential random Variables The Poisson Process Counting processes Definition of the Poisson Process Interarrival and Waiting Time Distributions Further Properties of Poisson processes Conditional Distribution of the Arrival Times Estimating Software Reliability Generalizations of the Poisson Process Nonhomogeneous Poisson Process Compound Poisson Process Conditional or Mixed Poisson processes 343viiiContentsExercises 346 References 3646.

7 Continuous-Time Markov Chains Introduction Continuous-Time Markov Chains Birth and Death processes The Transition Probability FunctionPij(t) Limiting Probabilities Time Reversibility Uniformization Computing the Transition Probabilities 404 Exercises 407 References 4157. Renewal Theory and Its Applications Introduction Distribution ofN(t) Limit Theorems and Their Applications Renewal Reward processes Regenerative processes Alternating Renewal processes Semi-Markov processes The Inspection Paradox Computing the Renewal Function Applications to Patterns Patterns of Discrete random Variables The Expected Time to a Maximal Run of Distinct Values Increasing Runs of Continuous random Variables The Insurance Ruin Problem 473 Exercises 479 References 4928.

8 Queueing Theory Introduction Preliminaries Cost Equations Steady-State Probabilities Exponential Models A Single-Server Exponential Queueing System A Single-Server Exponential Queueing SystemHaving Finite Capacity A Shoeshine Shop A Queueing System with Bulk Service Network of Queues Open Systems Closed Systems The SystemM/G/1 Preliminaries: Work and Another Cost Identity Application of Work toM/G/1 Busy Periods Variations on theM/G/1 TheM/G/1 with random -Sized Batch Arrivals Priority Queues AnM/G/1 Optimization Example TheM/G/1 Queue with Server Breakdown The ModelG/M/1 TheG/M/1 Busy and Idle Periods A Finite Source Model Multiserver Queues Erlang s Loss System TheM/M/kQueue TheG/M/ kQueue TheM/G/kQueue 556 Exercises 558 References 5709.

9 Reliability Theory Introduction Structure Functions Minimal Path and Minimal Cut Sets Reliability of Systems of Independent Components Bounds on the Reliability Function Method of Inclusion and Exclusion Second Method for Obtaining Bounds onr(p) System Life as a Function of Component Lives Expected System Lifetime An Upper Bound on the Expected Life of aParallel System Systems with Repair A Series Model with Suspended Animation 615 Exercises 617 References 62410. Brownian Motion and Stationary processes Brownian Motion Hitting Times, Maximum variable , and the Gambler s RuinProblem Variations on Brownian Motion Brownian Motion with Drift Geometric Brownian Motion Pricing Stock Options An Example in Options Pricing The Arbitrage Theorem The Black-Scholes Option Pricing Formula White Noise Gaussian processes Stationary and Weakly Stationary processes Harmonic Analysis of Weakly Stationary processes 654 Exercises 657 References 66211.

10 Simulation Introduction General Techniques for Simulating Continuous RandomVariables The Inverse Transformation Method The Rejection Method The Hazard Rate Method Special Techniques for Simulating Continuous RandomVariables The Normal Distribution The Gamma Distribution The Chi-Squared Distribution The Beta(n, m)Distribution The Exponential Distribution The Von NeumannAlgorithm Simulating from Discrete Distributions The Alias Method stochastic processes Simulating a Nonhomogeneous Poisson Process Simulating a Two-Dimensional Poisson Process Variance Reduction Techniques Use of Antithetic Variables Variance Reduction by Conditioning Control Variates Importance Sampling Determining the Number of Runs Coupling from the Past 720 Exercises 723 References 731 Appendix.