Introduction to Probability Models

Cover......Page 1
Introduction toProbability Models......Page 4
Copyright......Page 5
  Course......Page 6
  Organization......Page 7
  Acknowledgments......Page 9
 1.2 Sample Space and Events......Page 11
 1.3 Probabilities Defined on Events......Page 13
 1.4 Conditional Probabilities......Page 16
 1.5 Independent Events......Page 19
 1.6 Bayes\' Formula......Page 21
 1.7 Probability Is a Continuous Event Function......Page 24
  Exercises......Page 25
  References......Page 31
 2.1 Random Variables......Page 32
 2.2 Discrete Random Variables......Page 36
  2.2.2 The Binomial Random Variable......Page 37
  2.2.3 The Geometric Random Variable......Page 39
  2.2.4 The Poisson Random Variable......Page 40
 2.3 Continuous Random Variables......Page 41
  2.3.1 The Uniform Random Variable......Page 42
  2.3.4 Normal Random Variables......Page 44
  2.4.1 The Discrete Case......Page 46
  2.4.2 The Continuous Case......Page 48
  2.4.3 Expectation of a Function of a Random Variable......Page 50
  2.5.1 Joint Distribution Functions......Page 53
  2.5.2 Independent Random Variables......Page 58
  2.5.3 Covariance and Variance of Sums of Random Variables......Page 59
   Properties of Covariance......Page 61
  2.5.4 Joint Probability Distribution of Functions of Random Variables......Page 68
 2.6 Moment Generating Functions......Page 71
  2.6.1 The Joint Distribution of the Sample Mean and Sample Variance from a Normal Population......Page 79
 2.7 Limit Theorems......Page 82
 2.8 Proof of the Strong Law of Large Numbers......Page 88
 2.9 Stochastic Processes......Page 93
  Exercises......Page 95
  References......Page 108
 3.2 The Discrete Case......Page 109
 3.3 The Continuous Case......Page 112
 3.4 Computing Expectations by Conditioning......Page 116
  3.4.1 Computing Variances by Conditioning......Page 128
 3.5 Computing Probabilities by Conditioning......Page 132
  3.6.1 A List Model......Page 151
  3.6.2 A Random Graph......Page 153
  3.6.3 Uniform Priors, Polya\'s Urn Model, and Bose-Einstein Statistics......Page 160
  3.6.4 Mean Time for Patterns......Page 164
  3.6.5 The k-Record Values of Discrete Random Variables......Page 167
  3.6.6 Left Skip Free Random Walks......Page 170
 3.7 An Identity for Compound Random Variables......Page 176
  3.7.1 Poisson Compounding Distribution......Page 179
  3.7.2 Binomial Compounding Distribution......Page 180
  3.7.3 A Compounding Distribution Related to the Negative Binomial......Page 181
  Exercises......Page 182
 4.1 Introduction......Page 200
 4.2 Chapman-Kolmogorov Equations......Page 204
 4.3 Classification of States......Page 212
 4.4 Long-Run Proportions and Limiting Probabilities......Page 222
  4.4.1 Limiting Probabilities......Page 239
  4.5.1 The Gambler\'s Ruin Problem......Page 240
  4.5.2 A Model for Algorithmic Efficiency......Page 244
  4.5.3 Using a Random Walk to Analyze a Probabilistic Algorithm for the Satisfiability Problem......Page 246
 4.6 Mean Time Spent in Transient States......Page 252
 4.7 Branching Processes......Page 254
 4.8 Time Reversible Markov Chains......Page 258
 4.9 Markov Chain Monte Carlo Methods......Page 268
 4.10 Markov Decision Processes......Page 272
 4.11 Hidden Markov Chains......Page 276
  4.11.1 Predicting the States......Page 280
  Exercises......Page 282
  References......Page 298
  5.2.1 Definition......Page 299
  5.2.2 Properties of the Exponential Distribution......Page 301
  5.2.3 Further Properties of the Exponential Distribution......Page 308
  5.2.4 Convolutions of Exponential Random Variables......Page 315
  5.2.5 The Dirichlet Distribution......Page 319
  5.3.1 Counting Processes......Page 320
  5.3.2 Definition of the Poisson Process......Page 322
  5.3.3 Further Properties of Poisson Processes......Page 326
  5.3.4 Conditional Distribution of the Arrival Times......Page 332
  5.3.5 Estimating Software Reliability......Page 342
  5.4.1 Nonhomogeneous Poisson Process......Page 345
   Examples of Compound Poisson Processes......Page 352
  5.4.3 Conditional or Mixed Poisson Processes......Page 357
 5.5 Random Intensity Functions and Hawkes Processes......Page 359
  Exercises......Page 363
  References......Page 380
 6.2 Continuous-Time Markov Chains......Page 381
 6.3 Birth and Death Processes......Page 383
 6.4 The Transition Probability Function Pij(t)......Page 390
 6.5 Limiting Probabilities......Page 400
 6.6 Time Reversibility......Page 407
 6.7 The Reversed Chain......Page 415
 6.8 Uniformization......Page 420
 6.9 Computing the Transition Probabilities......Page 424
  Exercises......Page 426
  References......Page 435
 7.1 Introduction......Page 436
 7.2 Distribution of N(t)......Page 437
 7.3 Limit Theorems and Their Applications......Page 441
 7.4 Renewal Reward Processes......Page 455
 7.5 Regenerative Processes......Page 466
  7.5.1 Alternating Renewal Processes......Page 469
 7.6 Semi-Markov Processes......Page 475
 7.7 The Inspection Paradox......Page 478
 7.8 Computing the Renewal Function......Page 481
  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 494
  Exercises......Page 500
  References......Page 511
 8.1 Introduction......Page 512
  8.2.1 Cost Equations......Page 513
  8.2.2 Steady-State Probabilities......Page 514
  8.3.1 A Single-Server Exponential Queueing System......Page 517
  8.3.2 A Single-Server Exponential Queueing System Having Finite Capacity......Page 527
  8.3.3 Birth and Death Queueing Models......Page 532
  8.3.4 A Shoe Shine Shop......Page 539
  8.3.5 Queueing Systems with Bulk Service......Page 541
  8.4.1 Open Systems......Page 545
  8.4.2 Closed Systems......Page 549
  8.5.1 Preliminaries: Work and Another Cost Identity......Page 554
  8.5.2 Application of Work to M/G/1......Page 555
  8.5.3 Busy Periods......Page 557
  8.6.1 The M/G/1 with Random-Sized Batch Arrivals......Page 559
  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 574
 8.8 A Finite Source Model......Page 575
 8.9 Multiserver Queues......Page 578
  8.9.1 Erlang\'s Loss System......Page 579
  8.9.3 The G/M/k Queue......Page 580
  8.9.4 The M/G/k Queue......Page 582
  Exercises......Page 583
 9.2 Structure Functions......Page 595
  9.2.1 Minimal Path and Minimal Cut Sets......Page 598
 9.3 Reliability of Systems of Independent Components......Page 601
 9.4 Bounds on the Reliability Function......Page 605
  9.4.1 Method of Inclusion and Exclusion......Page 606
  9.4.2 Second Method for Obtaining Bounds on r(p)......Page 614
 9.5 System Life as a Function of Component Lives......Page 617
 9.6 Expected System Lifetime......Page 624
  9.6.1 An Upper Bound on the Expected Life of a Parallel System......Page 627
 9.7 Systems with Repair......Page 629
  9.7.1 A Series Model with Suspended Animation......Page 634
  Exercises......Page 636
  References......Page 642
 10.1 Brownian Motion......Page 643
 10.2 Hitting Times, Maximum Variable, and the Gambler\'s Ruin Problem......Page 647
  10.3.2 Geometric Brownian Motion......Page 648
  10.4.1 An Example in Options Pricing......Page 650
  10.4.2 The Arbitrage Theorem......Page 652
  10.4.3 The Black-Scholes Option Pricing Formula......Page 655
 10.5 The Maximum of Brownian Motion with Drift......Page 660
 10.6 White Noise......Page 665
 10.7 Gaussian Processes......Page 667
 10.8 Stationary and Weakly Stationary Processes......Page 669
 10.9 Harmonic Analysis of Weakly Stationary Processes......Page 674
  Exercises......Page 676
  References......Page 681
 11.1 Introduction......Page 682
  11.2.1 The Inverse Transformation Method......Page 686
  11.2.2 The Rejection Method......Page 687
  11.2.3 The Hazard Rate Method......Page 691
    Hazard Rate Method for Generating S:  λs(t)=λ (t)......Page 692
  11.3.1 The Normal Distribution......Page 694
  11.3.2 The Gamma Distribution......Page 697
  11.3.4 The Beta (n, m) Distribution......Page 698
  11.3.5 The Exponential Distribution-The Von Neumann Algorithm......Page 699
 11.4 Simulating from Discrete Distributions......Page 701
  11.4.1 The Alias Method......Page 704
 11.5 Stochastic Processes......Page 708
  11.5.1 Simulating a Nonhomogeneous Poisson Process......Page 709
    Method 1. Sampling a Poisson Process......Page 710
    Method 2. Conditional Distribution of the Arrival Times......Page 712
    Method 3. Simulating the Event Times......Page 714
  11.5.2 Simulating a Two-Dimensional Poisson Process......Page 715
 11.6 Variance Reduction Techniques......Page 718
  11.6.1 Use of Antithetic Variables......Page 719
  11.6.2 Variance Reduction by Conditioning......Page 722
  11.6.3 Control Variates......Page 726
  11.6.4 Importance Sampling......Page 728
 11.7 Determining the Number of Runs......Page 733
  11.8.1 Coupling from the Past......Page 734
  11.8.2 Another Approach......Page 736
  Exercises......Page 737
  References......Page 744
 12.2 Coupling and Stochastic Order Relations......Page 746
 12.3 Stochastic Ordering of Stochastic Processes......Page 749
 12.4 Maximum Couplings, Total Variation Distance, and the Coupling Identity......Page 752
  12.5.1 Applications to Markov Chains......Page 755
 12.6 Coupling and Stochastic Optimization......Page 761
 12.7 Chen-Stein Poisson Approximation Bounds......Page 765
  Exercises......Page 772
  Chapter 1......Page 775
  Chapter 2......Page 778
  Chapter 3......Page 782
  Chapter 4......Page 790
  Chapter 5......Page 793
  Chapter 6......Page 797
  Chapter 7......Page 800
  Chapter 8......Page 804
  Chapter 9......Page 811
  Chapter 10......Page 813
  Chapter 11......Page 815
Index......Page 818