1 Introduction to Probability Theory 1
1.1 Introduction 1
1.2 Sample Space and Events 1
1.3 Probabilities Defined on Events 4
1.4 Conditional Probabilities 6
1.5 Independent Events 9
1.6 Bayes’ Formula 11
Exercises 14
References 19
2 Random Variables 21
2.1 Random Variables 21
2.2 Discrete 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.3 Continuous 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.4 Expectation 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.5 Jointly 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.6 Moment 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 Classification 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 Satisfiability 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 Definition 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 Patterns 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/1 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