Introduction to Probability Models, Thirteenth Edition
Sheldon M. Ross
Contents
Preface xiii
1 Introduction to Probability Theory 1
1.1 Introduction 1
1.2 Sample Space and Events 1
1.3 Probabilities Defined on Events 3
1.4 Conditional Probabilities 6
1.5 Independent Events 9
1.6 Bayes’ Formula 11
1.7 Probability Is a Continuous Event Function 14
Exercises 15
References 21
2 Random Variables 23
2.1 Random Variables 23
2.2 Discrete Random Variables 26
2.2.1 The Bernoulli Random Variable 28
2.2.2 The Binomial Random Variable 28
2.2.3 The Geometric Random Variable 30
2.2.4 The Poisson Random Variable 31
2.3 Continuous Random Variables 32
2.3.1 The Uniform Random Variable 33
2.3.2 Exponential Random Variables 35
2.3.3 Gamma Random Variables 35
2.3.4 Normal Random Variables 35
2.4 Expectation of a Random Variable 37
2.4.1 The Discrete Case 37
2.4.2 The Continuous Case 39
2.4.3 Expectation of a Function of a Random Variable 41
2.5 Jointly Distributed Random Variables 44
2.5.1 Joint Distribution Functions 44
2.5.2 Independent Random Variables 52
2.5.3 Covariance and Variance of Sums of Random Variables 53
Properties of Covariance 55
2.5.4 Joint Probability Distribution of Functions of Random
Variables 62
2.6 Moment Generating Functions 64
2.6.1 The Joint Distribution of the Sample Mean and Sample
Variance from a Normal Population 73
2.7 Limit Theorems 76
2.8 Proof of the Strong Law of Large Numbers 82
2.9 Stochastic Processes 86
Exercises 88
References 101
3 Conditional Probability and Conditional Expectation 103
3.1 Introduction 103
3.2 The Discrete Case 103
3.3 The Continuous Case 106
3.4 Computing Expectations by Conditioning 111
3.4.1 Computing Variances by Conditioning 122
3.5 Computing Probabilities by Conditioning 126
3.6 Some Applications 150
3.6.1 A List Model 150
3.6.2 A Random Graph 152
3.6.3 Uniform Priors, Polya’s Urn Model, and Bose–Einstein Statistics 159
3.6.4 Mean Time for Patterns 163
3.6.5 The k-Record Values of Discrete Random Variables 168
3.6.6 Left Skip Free Random Walks 171
3.7 An Identity for Compound Random Variables 177
3.7.1 Poisson Compounding Distribution 179
3.7.2 Binomial Compounding Distribution 180
3.7.3 A Compounding Distribution Related to the Negative
Binomial 181
Exercises 182
4 Markov Chains 201
4.1 Introduction 201
4.2 Chapman–Kolmogorov Equations 205
4.3 Classification of States 213
4.4 Long-Run Proportions and Limiting Probabilities 223
4.4.1 Limiting Probabilities 240
4.5 Some Applications 241
4.5.1 The Gambler’s Ruin Problem 241
4.5.2 A Model for Algorithmic Efficiency 245
4.5.3 Using a Random Walk to Analyze a Probabilistic Algorithm
for the Satisfiability Problem 247
4.6 Mean Time Spent in Transient States 253
4.7 Branching Processes 255
4.8 Time Reversible Markov Chains 258
4.9 Markov Chain Monte Carlo Methods 269
4.10 Markov Decision Processes 273
4.11 Hidden Markov Chains 277
4.11.1Predicting the States 281
Exercises 283
References 299
5 The Exponential Distribution and the Poisson Process 301
5.1 Introduction 301
5.2 The Exponential Distribution 301
5.2.1 Definition 301
5.2.2 Properties of the Exponential Distribution 303
5.2.3 Further Properties of the Exponential Distribution 310
5.2.4 Convolutions of Exponential Random Variables 317
5.2.5 The Dirichlet Distribution 321
5.3 The Poisson Process 322
5.3.1 Counting Processes 322
5.3.2 Definition of the Poisson Process 323
5.3.3 Further Properties of Poisson Processes 328
5.3.4 Conditional Distribution of the Arrival Times 334
5.3.5 Estimating Software Reliability 344
5.4 Generalizations of the Poisson Process 347
5.4.1 Nonhomogeneous Poisson Process 347
5.4.2 Compound Poisson Process 353
Examples of Compound Poisson Processes 353
5.4.3 Conditional or Mixed Poisson Processes 358
5.5 Random Intensity Functions and Hawkes Processes 361
Exercises 364
References 381
6 Continuous-Time Markov Chains 383
6.1 Introduction 383
6.2 Continuous-Time Markov Chains 383
6.3 Birth and Death Processes 385
6.4 The Transition Probability Function Pij (t) 392
6.5 Limiting Probabilities 402
6.6 Time Reversibility 409
6.7 The Reversed Chain 417
6.8 Uniformization 422
6.9 Computing the Transition Probabilities 425
Exercises 428
References 437
7 Renewal Theory and Its Applications 439
7.1 Introduction 439
7.2 Distribution of N(t) 440
7.3 Limit Theorems and Their Applications 444
7.4 Renewal Reward Processes 459
7.4.1 Renewal Reward Process Applications to Markov Chains 468
7.4.2 Renewal Reward Process Applications to Patterns of Markov
Chain Generated Data 471
7.5 Regenerative Processes 473
7.5.1 Alternating Renewal Processes 476
7.6 Semi-Markov Processes 482
7.7 The Inspection Paradox 485
7.8 Computing the Renewal Function 488
7.9 Applications to Patterns 490
7.9.1 Patterns of Discrete Random Variables 491
7.9.2 The Expected Time to a Maximal Run of Distinct Values 498
7.9.3 Increasing Runs of Continuous Random Variables 499
7.10 The Insurance Ruin Problem 501
Exercises 507
References 518
8 Queueing Theory 519
8.1 Introduction 519
8.2 Preliminaries 520
8.2.1 Cost Equations 520
8.2.2 Steady-State Probabilities 521
8.3 Exponential Models 524
8.3.1 A Single-Server Exponential Queueing System 524
8.3.2 A Single-Server Exponential Queueing System Having
Finite Capacity 534
8.3.3 Birth and Death Queueing Models 539
8.3.4 A Shoe Shine Shop 546
8.3.5 Queueing Systems with Bulk Service 548
8.4 Network of Queues 552
8.4.1 Open Systems 552
8.4.2 Closed Systems 556
8.5 The System M/G/1 562
8.5.1 Preliminaries: Work and Another Cost Identity 562
8.5.2 Application of Work to M/G/1 563
8.5.3 Busy Periods 565
8.6 Variations on the M/G/1 566
8.6.1 The M/G/1 with Random-Sized Batch Arrivals 566
8.6.2 Priority Queues 568
8.6.3 An M/G/1 Optimization Example 571
8.6.4 The M/G/1 Queue with Server Breakdown 575
8.7 The Model G/M/1 577
8.7.1 The G/M/1 Busy and Idle Periods 581
8.8 A Finite Source Model 582
8.9 Multiserver Queues 586
8.9.1 Erlang’s Loss System 586
8.9.2 The M/M/k Queue 587
8.9.3 The G/M/k Queue 588
8.9.4 The M/G/k Queue 590
Exercises 591
9 Reliability Theory 603
9.1 Introduction 603
9.2 Structure Functions 603
9.2.1 Minimal Path and Minimal Cut Sets 606
9.3 Reliability of Systems of Independent Components 609
9.4 Bounds on the Reliability Function 613
9.4.1 Method of Inclusion and Exclusion 614
9.4.2 Second Method for Obtaining Bounds on r (p) 622
9.5 System Life as a Function of Component Lives 624
9.6 Expected System Lifetime 632
9.6.1 An Upper Bound on the Expected Life of a Parallel System 636
9.7 Systems with Repair 638
9.7.1 A Series Model with Suspended Animation 642
Exercises 644
References 651
10 Brownian Motion and Stationary Processes 653
10.1 Brownian Motion 653
10.2 Hitting Times, Maximum Variable, and the Gambler’s Ruin
Problem 657
10.3 Variations on Brownian Motion 658
10.3.1 Brownian Motion with Drift 658
10.3.2 Geometric Brownian Motion 658
10.4 Pricing Stock Options 659
10.4.1 An Example in Options Pricing 659
10.4.2 The Arbitrage Theorem 662
10.4.3 The Black–Scholes Option Pricing Formula 665
10.5 The Maximum of Brownian Motion with Drift 670
10.6 White Noise 675
10.7 Gaussian Processes 677
10.8 Stationary and Weakly Stationary Processes 679
10.9 Harmonic Analysis of Weakly Stationary Processes 684
Exercises 686
References 691
11 Simulation 693
11.1 Introduction 693
11.2 General Techniques for Simulating Continuous Random Variables 697
11.2.1 The Inverse Transformation Method 697
11.2.2 The Rejection Method 698
11.2.3 The Hazard Rate Method 702
11.3 Special Techniques for Simulating Continuous Random Variables 705
11.3.1 The Normal Distribution 705
11.3.2 The Gamma Distribution 708
11.3.3 The Chi-Squared Distribution 709
11.3.4 The Beta (n, m) Distribution 709
11.3.5 The Exponential Distribution—The Von Neumann
Algorithm 710
11.4 Simulating from Discrete Distributions 712
11.4.1 The Alias Method 715
11.5 Stochastic Processes 719
11.5.1 Simulating a Nonhomogeneous Poisson Process 720
11.5.2 Simulating a Two-Dimensional Poisson Process 726
11.6 Variance Reduction Techniques 728
11.6.1 Use of Antithetic Variables 729
11.6.2 Variance Reduction by Conditioning 733
11.6.3 Control Variates 737
11.6.4 Importance Sampling 739
11.7 Determining the Number of Runs 744
11.8 Generating from the Stationary Distribution of a Markov Chain 744
11.8.1 Coupling from the Past 744
11.8.2 Another Approach 746
Exercises 747
References 755
12 Coupling 757
12.1 A Brief Introduction 757
12.2 Coupling and Stochastic Order Relations 757
12.3 Stochastic Ordering of Stochastic Processes 760
12.4 Maximum Couplings, Total Variation Distance, and the Coupling
Identity 763
12.5 Applications of the Coupling Identity 766
12.5.1 Applications to Markov Chains 766
12.6 Coupling and Stochastic Optimization 772
12.7 Chen–Stein Poisson Approximation Bounds 776
Exercises 783
13 Martingales 787
13.1 Introduction 787
13.2 The Martingale Stopping Theorem 789
13.3 Applications of the Martingale Stopping Theorem 791
13.3.1 Wald’s Equation 791
13.3.2 Means and Variances of Pattern Occurrence Times 791
13.3.3 Random Walks 793
13.4 Submartingales 795
Exercises 796
Solutions to Starred Exercises 799
Index 843