Basics of Applied Stochastic Processes (eBook)

Preface 7
Contents 10
Markov Chains 14
1.1 Introduction 15
1.2 Probabilities of Sample Paths 18
1.3 Construction of Markov Chains 21
1.4 Examples 23
1.5 Stopping Times and Strong Markov Property 29
1.6 Classification of States 32
1.7 Hitting and Absorbtion Probabilities 39
1.8 Branching Processes 43
1.9 Stationary Distributions 46
1.10 Limiting Distributions 53
1.11 Regenerative Property and Cycle Costs 55
1.12 Strong Laws of Large Numbers 58
1.13 Examples of Limiting Averages 63
1.14 Optimal Design of Markovian Systems 66
1.15 Closed Network Model 68
1.16 Open Network Model 72
1.17 Reversible Markov Chains 74
1.18 Markov Chain Monte Carlo 81
1.19 Markov Chains on Subspaces 84
1.20 Limit Theorems via Coupling 86
1.21 Criteria for Positive Recurrence 89
1.22 Review of Conditional Probabilities 94
1.23 Exercises 97
Renewal and Regenerative Processes 112
2.1 Renewal Processes 112
2.2 Strong Laws of Large Numbers 117
2.3 The Renewal Function 120
2.4 Future Expectations 127
2.5 Renewal Equations 127
2.6 Blackwell’s Theorem 129
2.7 Key Renewal Theorem 131
2.8 Regenerative Processes 134
2.9 Limiting Distributions for Markov Chains 139
2.10 Processes with Regenerative Increments 139
2.11 Average Sojourn Times in Regenerative Processes 142
2.12 Batch-Service Queueing System 145
2.13 Central Limit Theorems 148
2.14 Terminating Renewal Processes 152
2.15 Stationary Renewal Processes 157
2.16 Refined Limit Laws 161
2.17 Proof of the Key Renewal Theorem* 164
2.18 Proof of Blackwell’s Theorem* 166
2.19 Stationary-Cycle Processes* 168
2.20 Exercises 169
Poisson Processes 182
3.1 Poisson Processes on R+ 183
3.2 Characterizations of Classical Poisson Processes 186
3.3 Location of Points 189
3.4 Functions of Point Locations 192
3.5 Poisson Processes on General Spaces 194
3.6 Integrals and Laplace Functionals of Poisson Processes 196
3.7 Poisson Processes as Sample Processes 201
3.8 Deterministic Transformations of Poisson Processes 203
3.9 Marked and Space-Time Poisson Processes 207
3.10 Partitions and Translations of Poisson Processes 209
3.11 Markov/Poisson Processes 214
3.12 Poisson Input-Output Systems 216
3.13 Network of Mt/Gt/8 Stations 219
3.14 Cox Processes 224
3.15 Compound Poisson Processes 227
3.16 Poisson Law of Rare Events 229
3.17 Poisson Convergence Theorems* 231
3.18 Exercises 238
Continuous-Time Markov Chains 254
4.1 Introduction 255
4.2 Examples 258
4.3 Markov Properties 260
4.4 Transition Probabilities and Transition Rates 264
4.5 Existence of CTMCs 266
4.6 Uniformization, Travel Times and Transition Probabilities 268
4.7 Stationary and Limiting Distributions 271
4.8 Regenerative Property and Cycle Costs 276
4.9 Ergodic Theorems 277
4.10 Expectations of Cost and Utility Functions 282
4.11 Reversibility 285
4.12 Modeling of Reversible Phenomena 290
4.13 Jackson Network Processes 295
4.14 Multiclass Networks 300
4.15 Poisson Transition Times 304
4.16 Palm Probabilities 312
4.17 PASTA at Poisson Transitions 316
4.18 Relating Palm and Ordinary Probabilities 319
4.19 Stationarity Under Palm Probabilities 323
4.20 G/G/1, M/G/1 and G/M/1 Queues 327
4.21 Markov-Renewal Processes* 334
4.22 Exercises 336
Brownian Motion 354
5.1 Definition and Strong Markov Property 355
5.2 Brownian Motion as a Gaussian Process 358
5.3 Maximum Process and Hitting Times 362
5.4 Special Random Times 365
5.5 Martingales 367
5.6 Optional Stopping of Martingales 371
5.7 Hitting Times for Brownian Motion with Drift 374
5.8 Limiting Averages and Law of the Iterated Logarithm 377
5.9 Donsker’s Functional Central Limit Theorem 381
5.10 Regenerative and Markov FCLTs 386
5.11 Peculiarities of Brownian Sample Paths 390
5.12 Brownian Bridge Process 392
5.13 Geometric Brownian Motion 396
5.14 Multidimensional Brownian Motion 398
5.15 Brownian/Poisson Particle System 400
5.16 G/G/1 Queues in Heavy Traffic 402
5.17 Brownian Motion in a Random Environment 406
5.18 Exercises 407
Appendix 418
6.1 Probability Spaces and Random Variables 418
6.2 Table of Distributions 420
6.3 Random Elements and Stochastic Processes 422
6.4 Expectations as Integrals 423
6.5 Functions of Stochastic Processes 425
6.6 Independence 428
6.7 Conditional Probabilities and Expectations 430
6.8 Existence of Stochastic Processes 432
6.9 Convergence Concepts 434
Bibliographical Notes 440
References 442
Notation 448
Index 450