A First Course in Stochastic ModelsISBN: 9780471498803
492 pages
April 2003

Description
 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
Preface ix
1 The Poisson Process and Related Processes 1
1.0 Introduction 1
1.1 The Poisson Process 1
1.1.1 The Memoryless Property 2
1.1.2 Merging and Splitting of Poisson Processes 6
1.1.3 The M/G/∞ Queue 9
1.1.4 The Poisson Process and the Uniform Distribution 15
1.2 Compound Poisson Processes 18
1.3 NonStationary Poisson Processes 22
1.4 Markov Modulated Batch Poisson Processes 24
Exercises 28
Bibliographic Notes 32
References 32
2 RenewalReward Processes 33
2.0 Introduction 33
2.1 Renewal Theory 34
2.1.1 The Renewal Function 35
2.1.2 The Excess Variable 37
2.2 RenewalReward Processes 39
2.3 The Formula of Little 50
2.4 Poisson Arrivals See Time Averages 53
2.5 The Pollaczek–Khintchine Formula 58
2.6 A Controlled Queue with Removable Server 66
2.7 An Up And Downcrossing Technique 69
Exercises 71
Bibliographic Notes 78
References 78
3 DiscreteTime Markov Chains 81
3.0 Introduction 81
3.1 The Model 82
3.2 Transient Analysis 87
3.2.1 Absorbing States 89
3.2.2 Mean FirstPassage Times 92
3.2.3 Transient and Recurrent States 93
3.3 The Equilibrium Probabilities 96
3.3.1 Preliminaries 96
3.3.2 The Equilibrium Equations 98
3.3.3 The Longrun Average Reward per Time Unit 103
3.4 Computation of the Equilibrium Probabilities 106
3.4.1 Methods for a FiniteState Markov Chain 107
3.4.2 Geometric Tail Approach for an Infinite State Space 111
3.4.3 Metropolis—Hastings Algorithm 116
3.5 Theoretical Considerations 119
3.5.1 State Classification 119
3.5.2 Ergodic Theorems 126
Exercises 134
Bibliographic Notes 139
References 139
4 ContinuousTime Markov Chains 141
4.0 Introduction 141
4.1 The Model 142
4.2 The Flow Rate Equation Method 147
4.3 Ergodic Theorems 154
4.4 Markov Processes on a SemiInfinite Strip 157
4.5 Transient State Probabilities 162
4.5.1 The Method of Linear Differential Equations 163
4.5.2 The Uniformization Method 166
4.5.3 First Passage Time Probabilities 170
4.6 Transient Distribution of Cumulative Rewards 172
4.6.1 Transient Distribution of Cumulative Sojourn Times 173
4.6.2 Transient Reward Distribution for the General Case 176
Exercises 179
Bibliographic Notes 185
References 185
5 Markov Chains and Queues 187
5.0 Introduction 187
5.1 The Erlang Delay Model 187
5.1.1 The M/M/1 Queue 188
5.1.2 The M/M/c Queue 190
5.1.3 The Output Process and Time Reversibility 192
5.2 Loss Models 194
5.2.1 The Erlang Loss Model 194
5.2.2 The Engset Model 196
5.3 ServiceSystem Design 198
5.4 Insensitivity 202
5.4.1 A Closed Twonode Network with Blocking 203
5.4.2 The M/G/1 Queue with Processor Sharing 208
5.5 A Phase Method 209
5.6 Queueing Networks 214
5.6.1 Open Network Model 215
5.6.2 Closed Network Model 219
Exercises 224
Bibliographic Notes 230
References 231
6 DiscreteTime Markov Decision Processes 233
6.0 Introduction 233
6.1 The Model 234
6.2 The PolicyImprovement Idea 237
6.3 The Relative Value Function 243
6.4 PolicyIteration Algorithm 247
6.5 Linear Programming Approach 252
6.6 ValueIteration Algorithm 259
6.7 Convergence Proofs 267
Exercises 272
Bibliographic Notes 275
References 276
7 SemiMarkov Decision Processes 279
7.0 Introduction 279
7.1 The SemiMarkov Decision Model 280
7.2 Algorithms for an Optimal Policy 284
7.3 Value Iteration and Fictitious Decisions 287
7.4 Optimization of Queues 290
7.5 OneStep Policy Improvement 295
Exercises 300
Bibliographic Notes 304
References 305
8 Advanced Renewal Theory 307
8.0 Introduction 307
8.1 The Renewal Function 307
8.1.1 The Renewal Equation 308
8.1.2 Computation of the Renewal Function 310
8.2 Asymptotic Expansions 313
8.3 Alternating Renewal Processes 321
8.4 Ruin Probabilities 326
Exercises 334
Bibliographic Notes 337
References 338
9 Algorithmic Analysis of Queueing Models 339
9.0 Introduction 339
9.1 Basic Concepts 341
9.2 The M/G/1 Queue 345
9.2.1 The State Probabilities 346
9.2.2 The WaitingTime Probabilities 349
9.2.3 Busy Period Analysis 353
9.2.4 Work in System 358
9.3 The MX/G/1 Queue 360
9.3.1 The State Probabilities 361
9.3.2 The WaitingTime Probabilities 363
9.4 M/G/1 Queues with Bounded Waiting Times 366
9.4.1 The FiniteBuffer M/G/1 Queue 366
9.4.2 An M/G/1 Queue with Impatient Customers 369
9.5 The GI/G/1 Queue 371
9.5.1 Generalized Erlangian Services 371
9.5.2 Coxian2 Services 372
9.5.3 The GI /P h/1 Queue 373
9.5.4 The Ph/G/1 Queue 374
9.5.5 Twomoment Approximations 375
9.6 MultiServer Queues with Poisson Input 377
9.6.1 The M/D/c Queue 378
9.6.2 The M/G/c Queue 384
9.6.3 The MX/G/c Queue 392
9.7 The GI/G/c Queue 398
9.7.1 The GI/M/c Queue 400
9.7.2 The GI/D/c Queue 406
9.8 FiniteCapacity Queues 408
9.8.1 The M/G/c/c + N Queue 408
9.8.2 A Basic Relation for the Rejection Probability 410
9.8.3 The MX/G/c/c + N Queue with Batch Arrivals 413
9.8.4 DiscreteTime Queueing Systems 417
Exercises 420
Bibliographic Notes 428
References 428
Appendices 431
Appendix A. Useful Tools in Applied Probability 431
Appendix B. Useful Probability Distributions 440
Appendix C. Generating Functions 449
Appendix D. The Discrete Fast Fourier Transform 455
Appendix E. Laplace Transform Theory 458
Appendix F. Numerical Laplace Inversion 462
Appendix G. The RootFinding Problem 470
References 474
Index 475
The Wiley Advantage
 Fully updated with enhanced introductory material
 Presents an integrated presentation of theory, applications and algorithms
 Incorporates recent developments in computational probability
 Includes a wide range of realworld examples that illustrate the basic models and elucidate the methods of solution
 Accessible to anyone with knowledge of calculus and
probability
Reviews
“…clear and straightforward…plenty of worked (or orientated) examples as well as a substantial set of exercises…” (Short Book Reviews, August 2004)