# Introduction to Probability Models, Thirteenth Edition PDF by Sheldon M. Ross

## 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.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.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.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

This book is US\$10
To get free sample pages OR Buy this book