應用隨機過程

本書是一部經典的隨機過程著作，敍述深入淺出、涉及面廣。主要內容有隨機變量、條件期望、馬爾可夫鏈、指數分佈、泊松過程、平穩過程、更新理論及排隊論等，也包括了隨機過程在物理、生物、運籌、網絡、遺傳、經濟、保險、金融及可靠性中的應用。第12版幾乎各章都有新的內容，也新增了例子和習題，其中**的變化是增加了講解耦合方法的第12章，講述了這種方法在分析隨機系統時的作用。還值得一提的是，第5章介紹了一種可以適用於平穩和非平穩泊松過程的獲取結果的新方法。本書配有上百道習題，其中帶星號的習題還提供瞭解答。 ^[2] 

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 ^[2]