应用随机过程:概率模型导论(英文版·第12版)

1 Introduction to Probability Theory 1
1．1 Introduction 1
1．2 Sample Space and Events 1
1．3 Probabilities Defined on Events 3
1．4 Conditional Probabilities 6
1．5 Independent Events 9
1．6 Bayes’ Formula 11
1．7 Probability Is a Continuous Event Function 14
Exercises 15
References 21
2 Random Variables 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 28
2．2．3 The Geometric Random Variable 30
2．2．4 The Poisson Random Variable 31
2．3 Continuous Random Variables 32
2．3．1 The Uniform Random Variable 33
2．3．2 Exponential Random Variables 35
2．3．3 Gamma Random Variables 35
2．3．4 Normal Random Variables 35
2．4 Expectation of a Random Variable 37
2．4．1 The Discrete Case 37
2．4．2 The Continuous Case 39
2．4．3 Expectation of a Function of a Random Variable 41
2．5 Jointly Distributed Random Variables 44
2．5．1 Joint Distribution Functions 44
2．5．2 Independent Random Variables 49
2．5．3 Covariance and Variance of Sums of Random Variables 50 Properties of Covariance 52
2．5．4 Joint Probability Distribution of Functions of Random Variables 59
2．6 Moment Generating Functions 62
2．6．1 The Joint Distribution of the Sample Mean and Sample Variance from a Normal Population 70
2．7 Limit Theorems 73
2．8 Proof of the Strong Law of Large Numbers 79
2．9 Stochastic Processes 84
Exercises 86
References 99
3 Conditional Probability and Conditional Expectation 101
3．1 Introduction 101
3．2 The Discrete Case 101
3．3 The Continuous Case 104
3．4 Computing Expectations by Conditioning 108
3．4．1 Computing Variances by Conditioning 120
3．5 Computing Probabilities by Conditioning 124
3．6 Some Applications 143
3．6．1 A List Model 143
3．6．2 A Random Graph 145
3．6．3 Uniform Priors， Polya’s Urn Model， and Bose–Einstein Statistics 152
3．6．4 Mean Time for Patterns 156
3．6．5 The k-Record Values of Discrete Random Variables 159
3．6．6 Left Skip Free Random Walks 162
3．7 An Identity for Compound Random Variables 168
3．7．1 Poisson Compounding Distribution 171
3．7．2 Binomial Compounding Distribution 172
3．7．3 A Compounding Distribution Related to the Negative Binomial 173
Exercises 174
4 Markov Chains 193
4．1 Introduction 193
4．2 Chapman–Kolmogorov Equations 197
4．3 Classification of States 205
4．4 Long-Run Proportions and Limiting Probabilities 215
4．4．1 Limiting Probabilities 232
4．5 Some Applications 233
4．5．1 The Gambler’s Ruin Problem 233
4．5．2 A Model for Algorithmic Efficiency 237
4．5．3 Using a Random Walk to Analyze a Probabilistic Algorithm for the Satisfiability Problem 239
4．6 Mean Time Spent in Transient States 245
4．7 Branching Processes 2475．2．2 Properties of the Exponential Distribution 295
4．8 Time Reversible Markov Chains 251
4．9 Markov Chain Monte Carlo Methods 261
4．10 Markov Decision Processes 265
4．11 Hidden Markov Chains 269
4．11．1 Predicting the States 273
Exercises 275
References 291
5 The Exponential Distribution and the Poisson Process 293
5．1 Introduction 293
5．2 The Exponential Distribution 293
5．2．1 Definition 293
5．2．2 Properties of the Exponential Distribution 295
5．2．3 Further Properties of the Exponential Distribution 302
5．2．4 Convolutions of Exponential Random Variables 309
5．2．5 The Dirichlet Distribution 313
5．3 The Poisson Process 314
5．3．1 Counting Processes 314
5．3．2 Definition of the Poisson Process 316
5．3．3 Further Properties of Poisson Processes 320
5．3．4 Conditional Distribution of the Arrival Times 326
5．3．5 Estimating Software Reliability 336
5．4 Generalizations of the Poisson Process 339
5．4．1 Nonhomogeneous Poisson Process 339
5．4．2 Compound Poisson Process 346
Examples of Compound Poisson Processes 346
5．4．3 Conditional or Mixed Poisson Processes 351
5．5 Random Intensity Functions and Hawkes Processes 353
Exercises 357
References 374
6 Continuous-Time Markov Chains 375
6．1 Introduction 375
6．2 Continuous-Time Markov Chains 375
6．3 Birth and Death Processes 377
6．4 The Transition Probability Function Pi j (t) 384
6．5 Limiting Probabilities 394
6．6 Time Reversibility 401
6．7 The Reversed Chain 409
6．8 Uniformization 414
6．9 Computing the Transition Probabilities 418
Exercises 420
References 429
7 Renewal Theory and Its Applications 431
7．1 Introduction 431
7．2 Distribution of N (t) 432
7．3 Limit Theorems and Their Applications 436
7．4 Renewal Reward Processes 450
7．5 Regenerative Processes 461
7．5．1 Alternating Renewal Processes 464
7．6 Semi-Markov Processes 470
7．7 The Inspection Paradox 473
7．8 Computing the Renewal Function 476
7．9 Applications to Patterns 479
7．9．1 Patterns of Discrete Random Variables 479
7．9．2 The Expected Time to a Maximal Run of Distinct Values 486
7．9．3 Increasing Runs of Continuous Random Variables 488
7．10 The Insurance Ruin Problem 489
Exercises 495
References 506
8 Queueing Theory 507
8．1 Introduction 507
8．2 Preliminaries 508
8．2．1 Cost Equations 508
8．2．2 Steady-State Probabilities 509
8．3 Exponential Models 512
8．3．1 A Single-Server Exponential Queueing System 512
8．3．2 A Single-Server Exponential Queueing System Having Finite Capacity 522
8．3．3 Birth and Death Queueing Models 527
8．3．4 A Shoe Shine Shop 534
8．3．5 Queueing Systems with Bulk Service 536
8．4 Network of Queues 540
8．4．1 Open Systems 540
8．4．2 Closed Systems 544
8．5 The System M G 1 549
8．5．1 Preliminaries： Work and Another Cost Identity 549
8．5．2 Application of Work to M G 1 550
8．5．3 Busy Periods 552
8．6 Variations on the M G 1 554
8．6．1 The M G 1 with Random-Sized Batch Arrivals 554
8．6．2 Priority Queues 555
8．6．3 An M G 1 Optimization Example 558
8．6．4 The M G 1 Queue with Server Breakdown 562
8．7 The Model G M 1 565
8．7．1 The G M 1 Busy and Idle Periods 569
8．8 A Finite Source Model 570
8．9 Multiserver Queues 573
8．9．1 Erlang’s Loss System 574
8．9．2 The M M k Queue 575
8．9．3 The G M k Queue 575
8．9．4 The M G k Queue 577
Exercises 578
9 Reliability Theory 591
9．1 Introduction 591
9．2 Structure Functions 591
9．2．1 Minimal Path and Minimal Cut Sets 594
9．3 Reliability of Systems of Independent Components 597
9．4 Bounds on the Reliability Function 601
9．4．1 Method of Inclusion and Exclusion 602
9．4．2 Second Method for Obtaining Bounds on r(p) 610
9．5 System Life as a Function of Component Lives 613
9．6 Expected System Lifetime 620
9．6．1 An Upper Bound on the Expected Life of a Parallel System 623
9．7 Systems with Repair 625
9．7．1 A Series Model with Suspended Animation 630
Exercises 632
References 638
10 Brownian Motion and Stationary Processes 639
10．1 Brownian Motion 639
10．2 Hitting Times， Maximum Variable， and the Gambler’s Ruin Problem 643
10．3 Variations on Brownian Motion 644
10．3．1 Brownian Motion with Drift 644
10．3．2 Geometric Brownian Motion 644
10．4 Pricing Stock Options 646
10．4．1 An Example in Options Pricing 646
10．4．2 The Arbitrage Theorem 648
10．4．3 The Black–Scholes Option Pricing Formula 651
10．5 The Maximum of Brownian Motion with Drift 656
10．6 White Noise 661
10．7 Gaussian Processes 663
10．8 Stationary and Weakly Stationary Processes 665
10．9 Harmonic Analysis of Weakly Stationary Processes 670
Exercises 672
References 677
11 Simulation 679
11．1 Introduction 679
11．2 General Techniques for Simulating Continuous Random Variables 683
11．2．1 The Inverse Transformation Method 683
11．2．2 The Rejection Method 684
11．2．3 The Hazard Rate Method 688
11．3 Special Techniques for Simulating Continuous Random Variables 691
11．3．1 The Normal Distribution 691
11．3．2 The Gamma Distribution 694
11．3．3 The Chi-Squared Distribution 695
11．3．4 The Beta (n， m) Distribution 695
11．3．5 The Exponential Distribution—The Von Neumann Algorithm 696
11．4 Simulating from Discrete Distributions 698
11．4．1 The Alias Method 701
11．5 Stochastic Processes 705
11．5．1 Simulating a Nonhomogeneous Poisson Process 706
11．5．2 Simulating a Two-Dimensional Poisson Process 712
11．6 Variance Reduction Techniques 715
11．6．1 Use of Antithetic Variables 716
11．6．2 Variance Reduction by Conditioning 719
11．6．3 Control Variates 723
11．6．4 Importance Sampling 725
11．7 Determining the Number of Runs 730
11．8 Generating from the Stationary Distribution of a Markov Chain 731
11．8．1 Coupling from the Past 731
11．8．2 Another Approach 733
Exercises 734
References 741
12 Coupling 743
12．1 A Brief Introduction 743
12．2 Coupling and Stochastic Order Relations 743
12．3 Stochastic Ordering of Stochastic Processes 746
12．4 Maximum Couplings， Total Variation Distance， and the Coupling Identity 749
12．5 Applications of the Coupling Identity 752
12．5．1 Applications to Markov Chains 752
12．6 Coupling and Stochastic Optimization 758
12．7 Chen–Stein Poisson Approximation Bounds 762
Exercises 769
Solutions to Starred Exercises 773
Index 817