First Course in Stochastic Models

Henk C. Tijms is a Dutch mathematician and Emeritus Professor of Operations Research at the VU University Amsterdam. He studied mathematics in Amsterdam where he graduated from the University of Amsterdam in 1972 under supervision of Gijsbert de Leve.

"…successfully combined theory and real world examples into a systematic introduction...an excellent reference for the applied statistician who deals in various queuing models." (Technometrics, August 2005) “…clear and straightforward…plenty of worked (or orientated) examples as well as a substantial set of exercises…” (Short Book Reviews, August 2004)

• Preface ix1 The Poisson Process and Related Processes 11.0 Introduction 11.1 The Poisson Process 11.1.1 The Memoryless Property 21.1.2 Merging and Splitting of Poisson Processes 61.1.3 The M/G/∞ Queue 91.1.4 The Poisson Process and the Uniform Distribution 151.2 Compound Poisson Processes 181.3 Non-Stationary Poisson Processes 221.4 Markov Modulated Batch Poisson Processes 24Exercises 28Bibliographic Notes 32References 322 Renewal-Reward Processes 332.0 Introduction 332.1 Renewal Theory 342.1.1 The Renewal Function 352.1.2 The Excess Variable 372.2 Renewal-Reward Processes 392.3 The Formula of Little 502.4 Poisson Arrivals See Time Averages 532.5 The Pollaczek–Khintchine Formula 582.6 A Controlled Queue with Removable Server 662.7 An Up- And Downcrossing Technique 69Exercises 71Bibliographic Notes 78References 783 Discrete-Time Markov Chains 813.0 Introduction 813.1 The Model 823.2 Transient Analysis 873.2.1 Absorbing States 893.2.2 Mean First-Passage Times 923.2.3 Transient and Recurrent States 933.3 The Equilibrium Probabilities 963.3.1 Preliminaries 963.3.2 The Equilibrium Equations 983.3.3 The Long-run Average Reward per Time Unit 1033.4 Computation of the Equilibrium Probabilities 1063.4.1 Methods for a Finite-State Markov Chain 1073.4.2 Geometric Tail Approach for an Infinite State Space 1113.4.3 Metropolis—Hastings Algorithm 1163.5 Theoretical Considerations 1193.5.1 State Classification 1193.5.2 Ergodic Theorems 126Exercises 134Bibliographic Notes 139References 1394 Continuous-Time Markov Chains 1414.0 Introduction 1414.1 The Model 1424.2 The Flow Rate Equation Method 1474.3 Ergodic Theorems 1544.4 Markov Processes on a Semi-Infinite Strip 1574.5 Transient State Probabilities 1624.5.1 The Method of Linear Differential Equations 1634.5.2 The Uniformization Method 1664.5.3 First Passage Time Probabilities 1704.6 Transient Distribution of Cumulative Rewards 1724.6.1 Transient Distribution of Cumulative Sojourn Times 1734.6.2 Transient Reward Distribution for the General Case 176Exercises 179Bibliographic Notes 185References 1855 Markov Chains and Queues 1875.0 Introduction 1875.1 The Erlang Delay Model 1875.1.1 The M/M/1 Queue 1885.1.2 The M/M/c Queue 1905.1.3 The Output Process and Time Reversibility 1925.2 Loss Models 1945.2.1 The Erlang Loss Model 1945.2.2 The Engset Model 1965.3 Service-System Design 1985.4 Insensitivity 2025.4.1 A Closed Two-node Network with Blocking 2035.4.2 The M/G/1 Queue with Processor Sharing 2085.5 A Phase Method 2095.6 Queueing Networks 2145.6.1 Open Network Model 2155.6.2 Closed Network Model 219Exercises 224Bibliographic Notes 230References 2316 Discrete-Time Markov Decision Processes 2336.0 Introduction 2336.1 The Model 2346.2 The Policy-Improvement Idea 2376.3 The Relative Value Function 2436.4 Policy-Iteration Algorithm 2476.5 Linear Programming Approach 2526.6 Value-Iteration Algorithm 2596.7 Convergence Proofs 267Exercises 272Bibliographic Notes 275References 2767 Semi-Markov Decision Processes 2797.0 Introduction 2797.1 The Semi-Markov Decision Model 2807.2 Algorithms for an Optimal Policy 2847.3 Value Iteration and Fictitious Decisions 2877.4 Optimization of Queues 2907.5 One-Step Policy Improvement 295Exercises 300Bibliographic Notes 304References 3058 Advanced Renewal Theory 3078.0 Introduction 3078.1 The Renewal Function 3078.1.1 The Renewal Equation 3088.1.2 Computation of the Renewal Function 3108.2 Asymptotic Expansions 3138.3 Alternating Renewal Processes 3218.4 Ruin Probabilities 326Exercises 334Bibliographic Notes 337References 3389 Algorithmic Analysis of Queueing Models 3399.0 Introduction 3399.1 Basic Concepts 3419.2 The M/G/1 Queue 3459.2.1 The State Probabilities 3469.2.2 The Waiting-Time Probabilities 3499.2.3 Busy Period Analysis 3539.2.4 Work in System 3589.3 The MX/G/1 Queue 3609.3.1 The State Probabilities 3619.3.2 The Waiting-Time Probabilities 3639.4 M/G/1 Queues with Bounded Waiting Times 3669.4.1 The Finite-Buffer M/G/1 Queue 3669.4.2 An M/G/1 Queue with Impatient Customers 3699.5 The GI/G/1 Queue 3719.5.1 Generalized Erlangian Services 3719.5.2 Coxian-2 Services 3729.5.3 The GI /P h/1 Queue 3739.5.4 The Ph/G/1 Queue 3749.5.5 Two-moment Approximations 3759.6 Multi-Server Queues with Poisson Input 3779.6.1 The M/D/c Queue 3789.6.2 The M/G/c Queue 3849.6.3 The MX/G/c Queue 3929.7 The GI/G/c Queue 3989.7.1 The GI/M/c Queue 4009.7.2 The GI/D/c Queue 4069.8 Finite-Capacity Queues 4089.8.1 The M/G/c/c + N Queue 4089.8.2 A Basic Relation for the Rejection Probability 4109.8.3 The MX/G/c/c + N Queue with Batch Arrivals 4139.8.4 Discrete-Time Queueing Systems 417Exercises 420Bibliographic Notes 428References 428Appendices 431Appendix A. Useful Tools in Applied Probability 431Appendix B. Useful Probability Distributions 440Appendix C. Generating Functions 449Appendix D. The Discrete Fast Fourier Transform 455Appendix E. Laplace Transform Theory 458Appendix F. Numerical Laplace Inversion 462Appendix G. The Root-Finding Problem 470References 474Index 475