应用随机过程：概率模型导论

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