1．Introduction to ProbabiIity Theory 1 1．1．IntrodUCtion 1 1．2．Sample Space and Events l 1．3．Probabilities Defined on Events 4 1．4．COIlditionaJ Probabilities 7 1．5．Independent Events 1 0 1．6．Bayes’Formula l 2 Exercises 1 5 References 2 1 2．Random VariabIes 23 2．1．Random Variables 23 2．2．Discrete Random Variables 27 2．2．1．The Bernoulli Random Variable 28 2．2．2．The Binomial Random Variable 29 2．2.3．The Geometric Random Variable 3 1 2．2．4．The POisson Random Variable 32 2.3．Continuous Random Variables 34 2.3．1．The Uniforlil Random Variable 35 2．3．2．Exponential Random Variables 36 2．3.3．Gamma Random Variables 37 2.3．4．Normal Random Variables 37 2．4．EXl9ectation Of a Ralldom Variable 38 2．4．1．The Discrete Case 38 2．4．2．The Continuous Case 4 l 2．4.3．Exlaectation of a Function Of a Random Variable 43 2．5．JOinnv Distributed Random Variables 47 2．5．1．Joint Distribution Functions 47 2．5．2．Independent Random Variables 5 l 2．5.3．Covariance and Variance of Sums of Random VariabIes 53 2．5．4．Joint Probabilitv Distribution of FUrictions of Random Variables 61 2．6．Moment Generating Functions 64 2．6．1．The Joint Distribution of the Sample Mean and Sample Variance from a Norrllal Population 74 2．7．Limit Theorems 77 2．8．StOChastic Processes 83 Exercises 85 References 96 3．ConditionaI ProbabiIity and C0nditional Expectation 97 3．1．Introduction 97 3．2．The Discrete Case 97 3．3．The Continuous Case 102 3．4．Computing Expectations by Conditioning 105 3．4．1．Computing Variances by Coilditioning 116 3．5．Computing Probabilities by Conditioning 119 3．6．Some Alaplicatioils 1 36 3．6．1．A List Model 136 3．6．2．A Random GraDh 138 3．6.3．Unifotin Priors，Polva's Urn Model，and Bose.Einstein Statistics 146 3．6．4．Mean Time for PatteIns 150 3．6．5．A Compound Poisson Identity 1 54 3．6．6．The k.Record Values of Discrete Random Variables 158 Exercises 161 4．Markov Chains 181 4．1 Introduction 181 4．2 Chapman.Kp1mogorov Equations 185 4.3 Classifientinn nf States 189 4．4． Limiting Probabilities 200 4．5． Some Applications 2 l 3 4．5．1．The GambIer’s Ruin Problem 213 4．5．2．A MOdel fof Algorithmic Efficiency 217 4．5．3．Using a Random Walk t0 Analyze a Probabilistic Algorithm for the Satisfiabilitv Problem 220 4．6． Mean Time Spent in Transient States 226 4．7． Branching Processes 228 4．8．Time Reversible Markov Chains 232 4．9． Markov Chain Monte Carlo MethOds 243 4．1 0．Markov DecisiOn Processes 248 Exercises 252 References 268 5．The ExponentiaI Distribution and the Poisson Process 269 5．1．Introduction 269 5．2．The Exponential Distribution 270 5．2．1．Definition 270 5．2．2．Properties of t11e Exponential Distribution 272 5．2．3．Further Properties of the Exponential Distribution 279 5．2．4．ConvolutiOIlS of Exponential Random Variables 284 5．3．The Poisson Process 288 5．3．1．Cpunting Processes 288 5．3．2．Definition of t11e POisson Process 289 5．3．3．Interarrival and Waiting Time Distributions 293 5．3．4．Further Properties Of POisson Processes 295 5．3．5．Coilditional Distribution Of the Arrival Times 30l 5．3．6．Estimating Software Reliability 3 l 3 5．4．Generalizations of the Poisson Process 3 l 6 5．4．1．Nonhomogeneous Poisson Process 3 1 6 5．4．2．Compollnd Poisson Process 321 5．4．3．Conditional or Mixed Poisson Processes 327 EXeFCises 330 References 348 6．C0ntinuous.Time Markov Chains 349 6．1．Introduction 349 6．2．Continuous.Time Markov Chaias 350 6.3．Birth and Death Processes 352 6．4．The Transition Probability Function Pii(f)359 6．5．Limiting Probabilities 368 6．6．Time Reversibilitv 376 6．7．Uniformization 384 6，8．Computing the Transitioil PrObabilities 388 Exercises 390 References 399 7．RenewaI Theory and Its Applications 401 7．1． Introduction 40l 7．2． Distribution of N(f)403 7.3． Limit Theorems and Their ApplicatiOns 407 7．4． Renewal Reward Processes 416 7．5． Regenerative Processes 425 7．5．1．A1temating Renewal Processes 428 7．6． Semi.Markov Processes 434 7．7．The Inspection Paradox 437 7．8． Coml9uting the Renewal Function 440 7．9． Applications to PattelTlS 443 7．9．1．Patterns Of Discrete Random Vailables 443 7．9．2．The Expected Time t0 a Maximal Run of Distinct Values 45l 7．9．3．Increasing Runs Of Continuous Random Variables 453 7．10．The Insurance Ruin PrOblem 455 Exercises 460 RefeFences 472 8．Queueing Theory 475 8．1．IntrOdtiCtion 475 8．2．Preliminaries 476 8．2．1．Cost EquationS 477 8．2．2．Steadv.State Probabilities 478 8.3．Exl90nential Models 480 8．3．1．A Single.Server Exponential Qucueing System 480 8．3．2．A Single-Server Expoilential QacHeing System Having Finite Caloacitv 487 8．3.3．A Shoeshine Shop 490 8．3．4．A Queueing System with Bulk Service 493 8．4．Network of Oueues 496 8．4．1．Open Svstems 496 8．4．2．Closed Svstems 50l 8．5．The System M／G／1 507 8．5．1．Preliminaries：Work and Anotller COSt Identitv 507 8．5．2．Alaplication OfWork to M／G／l 508 8．5.3．BUSY Periods 509 8．6．Variations on the M／G／l 510 8．6．1．The M／G／1 with Random-Sized Batch Arrivals 510 8．6．2．Prioritv Oueues 5 l 2 8．6．3．An M／G／l optimization Example 5 I 5 8．7．The Model G／M／1 519 8．7．1．The G／M／l Busy and Idle Periods 524 8．8．A Finite Source Model 525 8．9．Multiserver 0ueues 528 8．9．1．Erlang’s Loss System 529 8．9．2．The M／M／k Oueue 530 8．9．3．The G／M／k Queue 530 8．9．4．The M／G／k Queue 532 Exercises 534 References 546 9．ReIiability Theory 547 9．1．Introduction 547 9．2．Structure Functions 547 9．2．1．Minimal Path and Minimal Cut Sets 550 9．3．Reliabilitv of Systems Of Indelaendent Comlaonents 554 9．4．Bounds on the ReliabilitV Function 559 9．4．1．Method of Inclusion and Exclusion 560 9．4．2．Second Method for Obtaining Bounds on r(p)569 9．5．System Lifle as a Function of Comoonent Lives 571 9．6．Expected System Lifetime 580 9．6．1．An Upper Bound on the Exlaected Life Of a Parallel System 584 9．7．Systems with Repair 586 9．7．1．A Series Model with Suslaended Animation 591 Exercises 593 Refefences 600 1 0．Brownian M0tion and Stationary Processes 601 10．1．Brownian MOtion 60l 10．2．Hitting Times，Maximum Variable，and the Gambler’s Ruin Pmhlam 605 10．3．Variations on Brownian MOtiOn 607 10．3．1．Browniall MotiOn with Drift 607 10．3．2．Geometric Brownian Motion 607 l O．4．Pricing Stock Optioas 608 1 O．4．1．An Example in Options Pricing 608 l 0．4．2．The Arbitrage Theorem 6 1 l l O．4.3．The Black.Scholes Option Pricing Formula 6 l 4 10．5．White Noise 620 lO．6．Gaussian Processes 622 10．7．Stationarv alld Weakly Stationary Processes 625 10．8．Harlnonic Analysis Of Weaklv Stationary Processes 630 Exercises 633 References 638 1 1．SimuIation 639 11．1．Introduction 639 11．2．General Techniques for Simulating ContinUOUS Random Variables 644 11．2．1．The Inverse TransfGIrmation Method 644 1 1．2．2．The Reiection Method 645 11．2.3．The Hazard Rate Method 649 11．3．SDecial Techniques for Simulating ContinUOUS Random Variables 653 11．3．1．The Normal Distribution 653 l l.3．2．The Gamma Distribution 656 1l.3．3．The Chi.Squared Distribution 657 11．3．4．The Beta n，m)Distribution 657 ll.3．5．The Exponential Distribution..The Von Neumann Algorithm 658 11．4．SimulatinR from Discrete DistributiOns 66 l 11．4．1．The Alias Method 664 11．5．Stochastic Processes 668 11．5．1．Simulating a Nonhomogeneous Poisson Process 669 11．5．2．Simulating a Two.Dimensional POisson Process 676 11．6．Variance Reduction Techniques 679 11．6．1．Use of Anthetic Variables 680 l 1．6．2．Variance RedHetion by Conditioning 684 l 1．6．3．Control Variates 688 11．6.4．Importance Sampling 690 11．7．Determining me Number of Runs 696 11.8. Coupling from the Past 696 Exercises 699 References 707 Appendix: Solutions to Starred Exercises 709 Index 749
鄂公網(wǎng)安備 42010302001612號 