Introduction to probability models

Title Page......Page 4
Copyright Page......Page 5
Contents\n......Page 6
Preface......Page 12
1.2 Sample Space and Events......Page 18
1.3 Probabilities Defined on Events......Page 21
1.4 Conditional Probabilities......Page 24
1.5 Independent Events......Page 27
1.6 Bayes’ Formula......Page 29
Exercises......Page 32
References......Page 37
2.1 Random Variables......Page 38
2.2 Discrete Random Variables......Page 42
2.2.1 The Bernoulli Random Variable......Page 43
2.2.2 The Binomial Random Variable......Page 44
2.2.3 The Geometric Random Variable......Page 46
2.2.4 The Poisson Random Variable......Page 47
2.3 Continuous Random Variables......Page 48
2.3.1 The Uniform Random Variable......Page 49
2.3.4 Normal Random Variables......Page 51
2.4.1 The Discrete Case......Page 53
2.4.2 The Continuous Case......Page 55
2.4.3 Expectation of a Function of a Random Variable......Page 57
2.5.1 Joint Distribution Functions......Page 61
2.5.2 Independent Random Variables......Page 65
2.5.3 Covariance and Variance of Sums of Random Variables......Page 67
2.5.4 Joint Probability Distribution of Functions of Random Variables......Page 76
2.6 Moment Generating Functions......Page 79
2.6.1 The Joint Distribution of the Sample Mean and Sample Variance from a Normal Population......Page 88
2.7 The Distribution of the Number of Events that Occur......Page 91
2.8 Limit Theorems......Page 94
2.9 Stochastic Processes......Page 101
Exercises......Page 103
References......Page 112
3.2 The Discrete Case......Page 114
3.3 The Continuous Case......Page 119
3.4 Computing Expectations by Conditioning......Page 123
3.4.1 Computing Variances by Conditioning......Page 134
3.5 Computing Probabilities by Conditioning......Page 139
3.6.1 A List Model......Page 157
3.6.2 A Random Graph......Page 158
3.6.3 Uniform Priors, Polya’s Urn Model, and Bose–Einstein Statistics......Page 166
3.6.4 Mean Time for Patterns......Page 170
3.6.5 The k-Record Values of Discrete Random Variables......Page 174
3.6.6 Left Skip Free Random Walks......Page 177
3.7 An Identity for Compound Random Variables......Page 183
3.7.1 Poisson Compounding Distribution......Page 186
3.7.2 Binomial Compounding Distribution......Page 188
3.7.3 A Compounding Distribution Related to the Negative Binomial......Page 189
Exercises......Page 190
4.1 Introduction......Page 208
4.2 Chapman–Kolmogorov Equations......Page 212
4.3 Classification of States......Page 221
4.4 Limiting Probabilities......Page 231
4.5.1 The Gambler’s Ruin Problem......Page 247
4.5.2 A Model for Algorithmic Efficiency......Page 251
4.5.3 Using a Random Walk to Analyze a Probabilistic Algorithm for the Satisfiability Problem......Page 254
4.6 Mean Time Spent in Transient States......Page 260
4.7 Branching Processes......Page 262
4.8 Time Reversible Markov Chains......Page 266
4.9 Markov Chain Monte Carlo Methods......Page 277
4.10 Markov Decision Processes......Page 282
4.11 Hidden Markov Chains......Page 286
4.11.1 Predicting the States......Page 290
Exercises......Page 292
References......Page 307
5.1 Introduction......Page 308
5.2.1 Definition......Page 309
5.2.2 Properties of the Exponential Distribution......Page 311
5.2.3 Further Properties of the Exponential Distribution......Page 318
5.2.4 Convolutions of Exponential Random Variables......Page 325
5.3.1 Counting Processes......Page 329
5.3.2 Definition of the Poisson Process......Page 330
5.3.3 Interarrival and Waiting Time Distributions......Page 333
5.3.4 Further Properties of Poisson Processes......Page 336
5.3.5 Conditional Distribution of the Arrival Times......Page 342
5.3.6 Estimating Software Reliability......Page 353
5.4.1 Nonhomogeneous Poisson Process......Page 356
5.4.2 Compound Poisson Process......Page 363
5.4.3 Conditional or Mixed Poisson Processes......Page 368
Exercises......Page 371
References......Page 387
6.1 Introduction......Page 388
6.2 Continuous-Time Markov Chains......Page 389
6.3 Birth and Death Processes......Page 391
6.4 The Transition Probability Function Pij(t)......Page 398
6.5 Limiting Probabilities......Page 407
6.6 Time Reversibility......Page 414
6.7 Uniformization......Page 423
6.8 Computing the Transition Probabilities......Page 426
Exercises......Page 429
References......Page 436
7.1 Introduction......Page 438
7.2 Distribution of N(t)......Page 440
7.3 Limit Theorems and Their Applications......Page 444
7.4 Renewal Reward Processes......Page 456
7.5 Regenerative Processes......Page 464
7.5.1 Alternating Renewal Processes......Page 467
7.6 Semi-Markov Processes......Page 474
7.7 The Inspection Paradox......Page 477
7.8 Computing the Renewal Function......Page 480
7.9 Applications to Patterns......Page 483
7.9.1 Patterns of Discrete Random Variables......Page 484
7.9.2 The Expected Time to a Maximal Run of Distinct Values......Page 491
7.9.3 Increasing Runs of Continuous Random Variables......Page 493
7.10 The Insurance Ruin Problem......Page 495
Exercises......Page 501
References......Page 512
8.1 Introduction......Page 514
8.2 Preliminaries......Page 515
8.2.1 Cost Equations......Page 516
8.2.2 Steady-State Probabilities......Page 517
8.3.1 A Single-Server Exponential Queueing System......Page 519
8.3.2 A Single-Server Exponential Queueing System Having Finite Capacity......Page 528
8.3.3 Birth and Death Queueing Models......Page 534
8.3.4 A Shoe Shine Shop......Page 539
8.3.5 A Queueing System with Bulk Service......Page 541
8.4.1 Open Systems......Page 544
8.4.2 Closed Systems......Page 549
8.5.1 Preliminaries: Work and Another Cost Identity......Page 555
8.5.2 Application of Work to M/G/1......Page 556
8.5.3 Busy Periods......Page 557
8.6.1 The M/G/1 with Random-Sized Batch Arrivals......Page 558
8.6.2 Priority Queues......Page 560
8.6.3 An M/G/1 Optimization Example......Page 563
8.6.4 The M/G/1 Queue with Server Breakdown......Page 567
8.7 The Model G/M/1......Page 570
8.7.1 The G/M/1 Busy and Idle Periods......Page 575
8.8 A Finite Source Model......Page 576
8.9 Multiserver Queues......Page 579
8.9.1 Erlang’s Loss System......Page 580
8.9.2 The M/M/k Queue......Page 581
8.9.3 The G/M/k Queue......Page 582
8.9.4 The M/G/k Queue......Page 584
Exercises......Page 585
References......Page 595
9.1 Introduction......Page 596
9.2 Structure Functions......Page 597
9.2.1 Minimal Path and Minimal Cut Sets......Page 599
9.3 Reliability of Systems of Independent Components......Page 603
9.4 Bounds on the Reliability Function......Page 607
9.4.1 Method of Inclusion and Exclusion......Page 608
9.4.2 Second Method for Obtaining Bounds on r(p)......Page 617
9.5 System Life as a Function of Component Lives......Page 619
9.6 Expected System Lifetime......Page 627
9.6.1 An Upper Bound on the Expected Life of a Parallel System......Page 631
9.7 Systems with Repair......Page 633
9.7.1 A Series Model with Suspended Animation......Page 637
Exercises......Page 640
References......Page 646
10.1 Brownian Motion......Page 648
10.2 Hitting Times, Maximum Variable, and the Gambler’s Ruin Problem......Page 652
10.3.2 Geometric Brownian Motion......Page 653
10.4.1 An Example in Options Pricing......Page 655
10.4.2 The Arbitrage Theorem......Page 657
10.4.3 The Black-Scholes Option Pricing Formula......Page 661
10.5 White Noise......Page 666
10.6 Gaussian Processes......Page 668
10.7 Stationary and Weakly Stationary Processes......Page 671
10.8 Harmonic Analysis of Weakly Stationary Processes......Page 676
Exercises......Page 678
References......Page 682
11.1 Introduction......Page 684
11.2.1 The Inverse Transformation Method......Page 689
11.2.2 The Rejection Method......Page 690
11.2.3 The Hazard Rate Method......Page 694
11.3.1 The Normal Distribution......Page 697
11.3.3 The Chi-Squared Distribution......Page 701
11.3.4 The Beta (n, m) Distribution......Page 702
11.3.5 The Exponential Distribution—The Von Neumann Algorithm......Page 703
11.4 Simulating from Discrete Distributions......Page 705
11.4.1 The Alias Method......Page 708
11.5 Stochastic Processes......Page 713
11.5.1 Simulating a Nonhomogeneous Poisson Process......Page 714
11.5.2 Simulating a Two-Dimensional Poisson Process......Page 720
11.6 Variance Reduction Techniques......Page 723
11.6.1 Use of Antithetic Variables......Page 724
11.6.2 Variance Reduction by Conditioning......Page 727
11.6.3 Control Variates......Page 732
11.6.4 Importance Sampling......Page 734
11.7 Determining the Number of Runs......Page 739
11.8.1 Coupling from the Past......Page 740
11.8.2 Another Approach......Page 742
Exercises......Page 743
References......Page 751
Appendix: Solutions to Starred Exercises......Page 752
Index......Page 792