Introduction to probability modelsPDF电子书下载

1Introduction to Probability Theory 1

1.1Introduction 1

1.2Sample Space and Events 1

1.3Probabilities Defiined on Events 4

1.4Conditional Probabilities 6

1.5Independent Events 9

1.6Bayes’ Formula 11

Exercises 14

References 19

2Random Variables 21

2.1Random Variables 21

2.2Discrete Random Variables 25

2.2.1 The Bernoulli Random Variable 26

2.2.2 The Binomial Random Variable 26

2.2.3 The Geometric Random Variable 28

2.2.4 The Poisson Random Variable 29

2.3Continuous Random Variables 30

2.3.1 The Uniform Random Variable 31

2.3.2 Exponential Random Variables 32

2.3.3 Gamma Random Variables 33

2.3.4 Normal Random Variables 33

2.4Expectation of a Random Variable 34

2.4.1 The Discrete Case 34

2.4.2 The Continuous Case 37

2.4.3 Expectation of a Function of a Random Variable 38

2.5Jointly Distributed Random Variables 42

2.5.1 Joint Distribution Functions 42

2.5.2 Independent Random Variables 45

2.5.3 Covariance and Variance of Sums of Random Variables 46

2.5.4 Joint Probability Distribution of Functions of Random Variables 55

2.6Moment Generating Functions 58

2.6.1 The Joint Distribution of the Sample Mean and Sample Variance from a Normal Population 66

2.7 The Distribution of the Number of Events that Occur 69

2.8 Limit Theorems 71

2.9 Stochastic Processes 77

Exercises 79

References 91

3 Conditional Probability and Conditional Expectation 93

3.1 Introduction 93

3.2 The Discrete Case 93

3.3 The Continuous Case 97

3.4 Computing Expectations by Conditioning 100

3.4.1 Computing Variances by Conditioning 111

3.5 Computing Probabilities by Conditioning 115

3.6 Some Applications 133

3.6.1 A List Model 133

3.6.2 A Random Graph 135

3.6.3 Uniform Priors， Polya’s Urn Model， and Bose—Einstein Statistics 141

3.6.4 Mean Time for Patterns 146

3.6.5 The k-Record Values of Discrete Random Variables 149

3.6.6 Left Skip Free Random Walks 152

3.7 An Identity for Compound Random Variables 157

3.7.1 Poisson Compounding Distribution 160

3.7.2 Binomial Compounding Distribution 161

3.7.3 A Compounding Distribution Related to the Negative Binomial 162

Exercises 163

4 Markov Chains 183

4.1 Introduction 183

4.2 Chapman-Kolmogorov Equations 187

4.3 Classifiication of States 194

4.4 Long-Run Proportions and Limiting Probabilities 204

4.4.1 Limiting Probabilities 219

4.5 Some Applications 220

4.5.1 The Gambler’s Ruin Problem 220

4.5.2 A Model for Algorithmic Efficiency 223

4.5.3 Using a Random Walk to Analyze a Probabilistic Algorithm for the Satisfiiability Problem 226

4.6 Mean Time Spent in Transient States 231

4.7 Branching Processes 234

4.8 Time Reversible Markov Chains 237

4.9 Markov Chain Monte Carlo Methods 247

4.10 Markov Decision Processes 251

4.11 Hidden Markov Chains 254

4.11.1 Predicting the States 259

Exercises 261

References 275

5 The Exponential Distribution and the Poisson Process 277

5.1 Introduction 277

5.2 The Exponential Distribution 278

5.2.1 Defiinition 278

5.2.2 Properties of the Exponential Distribution 280

5.2.3 Further Properties of the Exponential Distribution 287

5.2.4 Convolutions of Exponential Random Variables 293

5.3 The Poisson Process 297

5.3.1 Counting Processes 297

5.3.2 Definition of the Poisson Process 298

5.3.3 Interarrival and Waiting Time Distributions 301

5.3.4 Further Properties of Poisson Processes 303

5.3.5 Conditional Distribution of the Arrival Times 309

5.3.6 Estimating Software Reliability 320

5.4 Generalizations of the Poisson Process 322

5.4.1 Nonhomogeneous Poisson Process 322

5.4.2 Compound Poisson Process 327

5.4.3 Conditional or Mixed Poisson Processes 332

5.5 Random Intensity Functions and Hawkes Processes 334

Exercises 338

References 356

6 Continuous-Time Markov Chains 357

6.1 Introduction 357

6.2 Continuous-Time Markov Chains 358

6.3 Birth and Death Processes 359

6.4 The Transition Probability Function Pij（t） 366

6.5 Limiting Probabilities 374

6.6 Time Reversibility 380

6.7 The Reversed Chain 387

6.8 Uniformization 393

6.9 Computing the Transition Probabilities 396

Exercises 398

References 407

7 Renewal Theory and Its Applications 409

7.1 Introduction 409

7.2 Distribution of N（t） 411

7.3 Limit Theorems and Their Applications 415

7.4 Renewal Reward Processes 427

7.5 Regenerative Processes 436

7.5.1 Alternating Renewal Processes 439

7.6 Semi-Markov Processes 444

7.7 The Inspection Paradox 447

7.8 Computing the Renewal Function 449

7.9 Applications to Patterns 452

7.9.1 Patternes of Discrete Random Variables 453

7.9.2 The Expected Time to a Maximal Run of Distinct Values 459

7.9.3 Increasing Runs of Continuous Random Variables 461

7.10 The Insurance Ruin Problem 462

Exercises 468

References 479

8 Queueing Theory 481

8.1 Introduction 481

8.2 Preliminaries 482

8.2.1 Cost Equations 482

8.2.2 Steady-State Probabilities 484

8.3 Exponential Models 486

8.3.1 A Single-Server Exponential Queueing System 486

8.3.2 A Single-Server Exponential Queueing System Having Finite Capacity 495

8.3.3 Birth and Death Queueing Models 499

8.3.4 A Shoe Shine Shop 505

8.3.5 A Queueing System with Bulk Service 507

8.4 Network of Queues 510

8.4.1 Open Systems 510

8.4.2 Closed Systems 514

8.5 The System M/G/ 1 520

8.5.1 Preliminaries： Work and Another Cost Identity 520

8.5.2 Application of Work to M/G/1 520

8.5.3 Busy Periods 522

8.6 Variations on the M/G/ 1 523

8.6.1 The M/G/1 with Random-Sized Batch Arrivals 523

8.6.2 Priority Queues 524

8.6.3 An M/G/1 Optimization Example 527

8.6.4 The M/G/l Queue with Server Breakdown 531

8.7 The Model G/M/ 1 534

8.7.1 The G/M/ 1 Busy and Idle Periods 538

8.8 A Finite Source Model 538

8.9 Multiserver Queues 542

8.9.1 Erlang’s Loss System 542

8.9.2 The M/M/k Queue 544

8.9.3 The G/M/k Queue 544

8.9.4 The M/G/k Queue 546

Exercises 547

References 558

9 Reliability Theory 559

9.1 Introduction 559

9.2 Structure Functions 560

9.2.1 Minimal Path and Minimal Cut Sets 562

9.3 Reliability of Systems of Independent Components 565

9.4 Bounds on the Reliability Function 570

9.4.1 Method of Inclusion and Exclusion 570

9.4.2 Second Method for Obtaining Bounds on r（p） 578

9.5 System Life as a Function of Component Lives 580

9.6 Expected System Lifetime 587

9.6.1 An Upper Bound on the Expected Life of a Parallel System 591

9.7 Systems with Repair 593

9.7.1 A Series Model with Suspended Animation 597

Exercises 599

References 606

10 Brownian Motion and Stationary Processes 607

10.1 Brownian Motion 607

10.2 Hitting Times， Maximum Variable， and the Gambler’s Ruin Problem 611

10.3 Variations on Brownian Motion 612

10.3.1 Brownian Motion with Drift 612

10.3.2 Geometric Brownian Motion 612

10.4 Pricing Stock Options 614

10.4.1 An Example in Options Pricing 614

10.4.2 The Arbitrage Theorem 616

10.4.3 The Black-Scholes Option Pricing Formula 619

10.5 The Maximum of Brownian Motion with Drift 624

10.6 White Noise 628

10.7 Gaussian Processes 630

10.8 Stationary and Weakly Stationary Processes 633

10.9 Harmonic Analysis of Weakly Stationary Processes 637

Exercises 639

References 644

11 Simulation 645

11.1 Introduction 645

11.2 General Techniques for Simulating Continuous Random Variables 649

11.2.1 The Inverse Transformation Method 649

11.2.2 The Rejection Method 650

11.2.3 The Hazard Rate Method 654

11.3 Special Techniques for Simulating Continuous Random Variables 657

11.3.1 The Normal Distribution 657

11.3.2 The Gamma Distribution 660

11.3.3 The Chi-Squared Distribution 660

11.3.4 The Beta （n， m） Distribution 661

11.3.5 The Exponential Distribution—The Von Neumann Algorithm 662

11.4 Simulating from Discrete Distributions 664

11.4.1 The Alias Method 667

11.5 Stochastic Processes 671

11.5.1 Simulating a Nonhomogeneous Poisson Process 672

11.5.2 Simulating a Two-Dimensional Poisson Process 677

11.6 Variance Reduction Techniques 680

11.6.1 Use of Antithetic Variables 681

11.6.2 Variance Reduction by Conditioning 684

11.6.3 Control Variates 688

11.6.4 Importance Sampling 690

11.7 Determining the Number of Runs 694

11.8 Generating from the Stationary Distribution of a Markov Chain 695

11.8.1 Coupling from the Past 695

11.8.2 Another Approach 697

Exercises 698

References 705

Appendix： Solutions to Starred Exercises 707

Index 759