A First Course in Stochastic Models

✍ Scribed by Henk C. Tijms

• Publisher: John Wiley & Sons
• Year: 2001
• Tongue: English
• Leaves: 491
• Edition: 1. Auflage
• Category: Library

✦ Synopsis

The field of applied probability has changed profoundly in the past twenty years. The development of computational methods has greatly contributed to a better understanding of the theory. A First Course in Stochastic Models provides a self-contained introduction to the theory and applications of stochastic models. Emphasis is placed on establishing the theoretical foundations of the subject, thereby providing a framework in which the applications can be understood. Without this solid basis in theory no applications can be solved.

• Provides an introduction to the use of stochastic models through an integrated presentation of theory, algorithms and applications.
• Incorporates recent developments in computational probability.
• Includes a wide range of examples that illustrate the models and make the methods of solution clear.
• Features an abundance of motivating exercises that help the student learn how to apply the theory.
• Accessible to anyone with a basic knowledge of probability.

A First Course in Stochastic Models is suitable for senior undergraduate and graduate students from computer science, engineering, statistics, operations resear ch, and any other discipline where stochastic modelling takes place. It stands out amongst other textbooks on the subject because of its integrated presentation of theory, algorithms and applications.

✦ Table of Contents

Cover......Page 1
A First Course in Stochastic Models......Page 4
Contents......Page 8
Preface......Page 12
1.1 The Poisson Process......Page 14
1.1.1 The Memoryless Property......Page 15
1.1.2 Merging and Splitting of Poisson Processes......Page 19
1.1.3 The M/G/ Queue......Page 22
1.1.4 The Poisson Process and the Uniform Distribution......Page 28
1.2 Compound Poisson Processes......Page 31
1.3 Non-Stationary Poisson Processes......Page 35
1.4 Markov Modulated Batch Poisson Processes......Page 37
Exercises......Page 41
References......Page 45
2.0 Introduction......Page 46
2.1 Renewal Theory......Page 47
2.1.1 The Renewal Function......Page 48
2.1.2 The Excess Variable......Page 50
2.2 Renewal-Reward Processes......Page 52
2.3 The Formula of Little......Page 63
2.4 Poisson Arrivals See Time Averages......Page 66
2.5 The Pollaczek–Khintchine Formula......Page 71
2.6 A Controlled Queue with Removable Server......Page 79
2.7 An Up- And Downcrossing Technique......Page 82
Exercises......Page 84
References......Page 91
3.0 Introduction......Page 94
3.1 The Model......Page 95
3.2 Transient Analysis......Page 100
3.2.1 Absorbing States......Page 102
3.2.2 Mean First-Passage Times......Page 105
3.2.3 Transient and Recurrent States......Page 106
3.3.1 Preliminaries......Page 109
3.3.2 The Equilibrium Equations......Page 111
3.3.3 The Long-run Average Reward per Time Unit......Page 116
3.4 Computation of the Equilibrium Probabilities......Page 119
3.4.1 Methods for a Finite-State Markov Chain......Page 120
3.4.2 Geometric Tail Approach for an Infinite State Space......Page 124
3.4.3 Metropolis—Hastings Algorithm......Page 129
3.5.1 State Classification......Page 132
3.5.2 Ergodic Theorems......Page 139
Exercises......Page 147
References......Page 152
4.0 Introduction......Page 154
4.1 The Model......Page 155
4.2 The Flow Rate Equation Method......Page 160
4.3 Ergodic Theorems......Page 167
4.4 Markov Processes on a Semi-Infinite Strip......Page 170
4.5 Transient State Probabilities......Page 175
4.5.1 The Method of Linear Differential Equations......Page 176
4.5.2 The Uniformization Method......Page 179
4.5.3 First Passage Time Probabilities......Page 183
4.6 Transient Distribution of Cumulative Rewards......Page 185
4.6.1 Transient Distribution of Cumulative Sojourn Times......Page 186
4.6.2 Transient Reward Distribution for the General Case......Page 189
Exercises......Page 192
References......Page 198
5.1 The Erlang Delay Model......Page 200
5.1.1 The M/M/1 Queue......Page 201
5.1.2 The M/M/c Queue......Page 203
5.1.3 The Output Process and Time Reversibility......Page 205
5.2.1 The Erlang Loss Model......Page 207
5.2.2 The Engset Model......Page 209
5.3 Service-System Design......Page 211
5.4 Insensitivity......Page 215
5.4.1 A Closed Two-node Network with Blocking......Page 216
5.4.2 The M/G/1 Queue with Processor Sharing......Page 221
5.5 A Phase Method......Page 222
5.6 Queueing Networks......Page 227
5.6.1 Open Network Model......Page 228
5.6.2 Closed Network Model......Page 232
Exercises......Page 237
Bibliographic Notes......Page 243
References......Page 244
6.0 Introduction......Page 246
6.1 The Model......Page 247
6.2 The Policy-Improvement Idea......Page 250
6.3 The Relative Value Function......Page 256
6.4 Policy-Iteration Algorithm......Page 260
6.5 Linear Programming Approach......Page 265
6.6 Value-Iteration Algorithm......Page 272
6.7 Convergence Proofs......Page 280
Exercises......Page 285
Bibliographic Notes......Page 288
References......Page 289
7.0 Introduction......Page 292
7.1 The Semi-Markov Decision Model......Page 293
7.2 Algorithms for an Optimal Policy......Page 297
7.3 Value Iteration and Fictitious Decisions......Page 300
7.4 Optimization of Queues......Page 303
7.5 One-Step Policy Improvement......Page 308
Exercises......Page 313
Bibliographic Notes......Page 317
References......Page 318
8.1 The Renewal Function......Page 320
8.1.1 The Renewal Equation......Page 321
8.1.2 Computation of the Renewal Function......Page 323
8.2 Asymptotic Expansions......Page 326
8.3 Alternating Renewal Processes......Page 334
8.4 Ruin Probabilities......Page 339
Exercises......Page 347
Bibliographic Notes......Page 350
References......Page 351
9.0 Introduction......Page 352
9.1 Basic Concepts......Page 354
9.2 The M/G/1 Queue......Page 358
9.2.1 The State Probabilities......Page 359
9.2.2 The Waiting-Time Probabilities......Page 362
9.2.3 Busy Period Analysis......Page 366
9.2.4 Work in System......Page 371
9.3 The M(X)/G/1 Queue......Page 373
9.3.1 The State Probabilities......Page 374
9.3.2 The Waiting-Time Probabilities......Page 376
9.4.1 The Finite-Buffer M/G/1 Queue......Page 379
9.4.2 An M/G/1 Queue with Impatient Customers......Page 382
9.5.1 Generalized Erlangian Services......Page 384
9.5.2 Coxian-2 Services......Page 385
9.5.3 The GI/Ph/1 Queue......Page 386
9.5.4 The Ph/G/1 Queue......Page 387
9.5.5 Two-moment Approximations......Page 388
9.6 Multi-Server Queues with Poisson Input......Page 390
9.6.1 The M/D/c Queue......Page 391
9.6.2 The M/G/c Queue......Page 397
9.6.3 The M(X)/G/c Queue......Page 405
9.7 The GI/G/c Queue......Page 411
9.7.1 The GI/M/c Queue......Page 413
9.7.2 The GI/D/c Queue......Page 419
9.8.1 The M/G/c/c + N Queue......Page 421
9.8.2 A Basic Relation for the Rejection Probability......Page 423
9.8.3 The M(X)/G/c/c + N Queue with Batch Arrivals......Page 426
9.8.4 Discrete-Time Queueing Systems......Page 430
Exercises......Page 433
References......Page 441
Appendix A. Useful Tools in Applied Probability......Page 444
Appendix B. Useful Probability Distributions......Page 453
Appendix C. Generating Functions......Page 462
Appendix D. The Discrete Fast Fourier Transform......Page 468
Appendix E. Laplace Transform Theory......Page 471
Appendix F. Numerical Laplace Inversion......Page 475
Appendix G. The Root-Finding Problem......Page 483
References......Page 487
Index......Page 488