Probability, Markov Chains, Queues, and Simulation

William J. Stewart is professor of computer science at North Carolina State University. He is the author of "An Introduction to the Numerical Solution of Markov Chains" (Princeton).

"The book represents a valuable text for courses in statistics and stochastic processes, so it is strongly recommended to libraries."--Hassan S. Bakouch, Journal of Applied Statistics

• Preface and Acknowledgments xv PART I PROBABILITY 1 Chapter 1: Probability 3 1.1 Trials, Sample Spaces, and Events 3 1.2 Probability Axioms and Probability Space 9 1.3 Conditional Probability 12 1.4 Independent Events 15 1.5 Law of Total Probability 18 1.6 Bayes' Rule 20 1.7 Exercises 21 Chapter 2: Combinatorics--The Art of Counting 25 2.1 Permutations 25 2.2 Permutations with Replacements 26 2.3 Permutations without Replacement 27 2.4 Combinations without Replacement 29 2.5 Combinations with Replacements 31 2.6 Bernoulli (Independent) Trials 33 2.7 Exercises 36 Chapter 3: Random Variables and Distribution Functions 40 3.1 Discrete and Continuous Random Variables 40 3.2 The Probability Mass Function for a Discrete Random Variable 43 3.3 The Cumulative Distribution Function 46 3.4 The Probability Density Function for a Continuous Random Variable 51 3.5 Functions of a Random Variable 53 3.6 Conditioned Random Variables 58 3.7 Exercises 60 Chapter 4: Joint and Conditional Distributions 64 4.1 Joint Distributions 64 4.2 Joint Cumulative Distribution Functions 64 4.3 Joint Probability Mass Functions 68 4.4 Joint Probability Density Functions 71 4.5 Conditional Distributions 77 4.6 Convolutions and the Sum of Two Random Variables 80 4.7 Exercises 82 Chapter 5: Expectations and More 87 5.1 Definitions 87 5.2 Expectation of Functions and Joint Random Variables 92 5.3 Probability Generating Functions for Discrete Random Variables 100 5.4 Moment Generating Functions 103 5.5 Maxima and Minima of Independent Random Variables 108 5.6 Exercises 110 Chapter 6: Discrete Distribution Functions 115 6.1 The Discrete Uniform Distribution 115 6.2 The Bernoulli Distribution 116 6.3 The Binomial Distribution 117 6.4 Geometric and Negative Binomial Distributions 120 6.5 The Poisson Distribution 124 6.6 The Hypergeometric Distribution 127 6.7 The Multinomial Distribution 128 6.8 Exercises 130 Chapter 7: Continuous Distribution Functions 134 7.1 The Uniform Distribution 134 7.2 The Exponential Distribution 136 7.3 The Normal or Gaussian Distribution 141 7.4 The Gamma Distribution 145 7.5 Reliability Modeling and the Weibull Distribution 149 7.6 Phase-Type Distributions 155 7.6.1 The Erlang-2 Distribution 155 7.6.2 The Erlang-r Distribution 158 7.6.3 The Hypoexponential Distribution 162 7.6.4 The Hyperexponential Distribution 164 7.6.5 The Coxian Distribution 166 7.6.6 General Phase-Type Distributions 168 7.6.7 Fitting Phase-Type Distributions to Means and Variances 171 7.7 Exercises 176 Chapter 8: Bounds and Limit Theorems 180 8.1 The Markov Inequality 180 8.2 The Chebychev Inequality 181 8.3 The Chernoff Bound 182 8.4 The Laws of Large Numbers 182 8.5 The Central Limit Theorem 184 8.6 Exercises 187 PART II MARKOV CHAINS 191 Chapter 9: Discrete- and Continuous-Time Markov Chains 193 9.1 Stochastic Processes and Markov Chains 193 9.2 Discrete-Time Markov Chains: Definitions 195 9.3 The Chapman-Kolmogorov Equations 202 9.4 Classification of States 206 9.5 Irreducibility 214 9.6 The Potential, Fundamental, and Reachability Matrices 218 9.6.1 Potential and Fundamental Matrices and Mean Time to Absorption 219 9.6.2 The Reachability Matrix and Absorption Probabilities 223 9.7 Random Walk Problems 228 9.8 Probability Distributions 235 9.9 Reversibility 248 9.10 Continuous-Time Markov Chains 253 9.10.1 Transition Probabilities and Transition Rates 254 9.10.2 The Chapman-Kolmogorov Equations 257 9.10.3 The Embedded Markov Chain and State Properties 259 9.10.4 Probability Distributions 262 9.10.5 Reversibility 265 9.11 Semi-Markov Processes 265 9.12 Renewal Processes 267 9.13 Exercises 275 Chapter 10: Numerical Solution of Markov Chains 285 10.1 Introduction 285 10.1.1 Setting the Stage 285 10.1.2 Stochastic Matrices 287 10.1.3 The Effect of Discretization 289 10.2 Direct Methods for Stationary Distributions 290 10.2.1 Iterative versus Direct Solution Methods 290 10.2.2 Gaussian Elimination and LU Factorizations 291 10.3 Basic Iterative Methods for Stationary Distributions 301 10.3.1 The Power Method 301 10.3.2 The Iterative Methods of Jacobi and Gauss-Seidel 305 10.3.3 The Method of Successive Overrelaxation 311 10.3.4 Data Structures for Large Sparse Matrices 313 10.3.5 Initial Approximations, Normalization, and Convergence 316 10.4 Block Iterative Methods 319 10.5 Decomposition and Aggregation Methods 324 10.6 The Matrix Geometric/Analytic Methods for Structured Markov Chains 332 10.6.1 The Quasi-Birth-Death Case 333 10.6.2 Block Lower Hessenberg Markov Chains 340 10.6.3 Block Upper Hessenberg Markov Chains 345 10.7 Transient Distributions 354 10.7.1 Matrix Scaling and Powering Methods for Small State Spaces 357 10.7.2 The Uniformization Method for Large State Spaces 361 10.7.3 Ordinary Differential Equation Solvers 365 10.8 Exercises 375 PART III QUEUEING MODELS 383 Chapter 11: Elementary Queueing Theory 385 11.1 Introduction and Basic Definitions 385 11.1.1 Arrivals and Service 386 11.1.2 Scheduling Disciplines 395 11.1.3 Kendall's Notation 396 11.1.4 Graphical Representations of Queues 397 11.1.5 Performance Measures--Measures of Effectiveness 398 11.1.6 Little's Law 400 11.2 Birth-Death Processes: The M/M/1 Queue 402 11.2.1 Description and Steady-State Solution 402 11.2.2 Performance Measures 406 11.2.3 Transient Behavior 412 11.3 General Birth-Death Processes 413 11.3.1 Derivation of the State Equations 413 11.3.2 Steady-State Solution 415 11.4 Multiserver Systems 419 11.4.1 The M/M/c Queue 419 11.4.2 The M/M/?Queue 425 11.5 Finite-Capacity Systems--The M/M/1/K Queue 425 11.6 Multiserver, Finite-Capacity Systems--The M/M/c/K Queue 432 11.7 Finite-Source Systems--The M/M/c//M Queue 434 11.8 State-Dependent Service 437 11.9 Exercises 438 Chapter 12: Queues with Phase-Type Laws: Neuts' Matrix-Geometric Method 444 12.1 The Erlang-r Service Model--The M/Er/1 Queue 444 12.2 The Erlang-r Arrival Model--The Er/M/1 Queue 450 12.3 The M/H2/1 and H2/M/1 Queues 454 12.4 Automating the Analysis of Single-Server Phase-Type Queues 458 12.5 The H2/E3/1 Queue and General Ph/Ph/1 Queues 460 12.6 Stability Results for Ph/Ph/1 Queues 466 12.7 Performance Measures for Ph/Ph/1 Queues 468 12.8 Matlab code for Ph/Ph/1 Queues 469 12.9 Exercises 471 Chapter 13: The z-Transform Approach to Solving Markovian Queues 475 13.1 The z-Transform 475 13.2 The Inversion Process 478 13.3 Solving Markovian Queues using z-Transforms 484 13.3.1 The z-Transform Procedure 484 13.3.2 The M/M/1 Queue Solved using z-Transforms 484 13.3.3 The M/M/1 Queue with Arrivals in Pairs 486 13.3.4 The M/Er/1 Queue Solved using z-Transforms 488 13.3.5 The Er/M/1 Queue Solved using z-Transforms 496 13.3.6 Bulk Queueing Systems 503 13.4 Exercises 506 Chapter 14: The M/G/1 and G/M/1 Queues 509 14.1 Introduction to the M/G/1 Queue 509 14.2 Solution via an Embedded Markov Chain 510 14.3 Performance Measures for the M/G/1 Queue 515 14.3.1 The Pollaczek-Khintchine Mean Value Formula 515 14.3.2 The Pollaczek-Khintchine Transform Equations 518 14.4 The M/G/1 Residual Time: Remaining Service Time 523 14.5 The M/G/1 Busy Period 526 14.6 Priority Scheduling 531 14.6.1 M/M/1: Priority Queue with Two Customer Classes 531 14.6.2 M/G/1: Nonpreemptive Priority Scheduling 533 14.6.3 M/G/1: Preempt-Resume Priority Scheduling 536 14.6.4 A Conservation Law and SPTF Scheduling 538 14.7 The M/G/1/K Queue 542 14.8 The G/M/1 Queue 546 14.9 The G/M/1/K Queue 551 14.10 Exercises 553 Chapter 15: Queueing Networks 559 15.1 Introduction 559 15.1.1 Basic Definitions 559 15.1.2 The Departure Process--Burke's Theorem 560 15.1.3 Two M/M/1 Queues in Tandem 562 15.2 Open Queueing Networks 563 15.2.1 Feedforward Networks 563 15.2.2 Jackson Networks 563 15.2.3 Performance Measures for Jackson Networks 567 15.3 Closed Queueing Networks 568 15.3.1 Definitions 568 15.3.2 Computation of the Normalization Constant: Buzen's Algorithm 570 15.3.3 Performance Measures 577 15.4 Mean Value Analysis for Closed Queueing Networks 582 15.5 The Flow-Equivalent Server Method 591 15.6 Multiclass Queueing Networks and the BCMP Theorem 594 15.6.1 Product-Form Queueing Networks 595 15.6.2 The BCMP Theorem for Open, Closed, and Mixed Queueing Networks 598 15.7 Java Code 602 15.8 Exercises 607 PART IV SIMULATION 611 Chapter 16: Some Probabilistic and Deterministic Applications of Random Numbers 613 16.1 Simulating Basic Probability Scenarios 613 16.2 Simulating Conditional Probabilities, Means, and Variances 618 16.3 The Computation of Definite Integrals 620 16.4 Exercises 623 Chapter 17: Uniformly Distributed "Random" Numbers 625 17.1 Linear Recurrence Methods 626 17.2 Validating Sequences of Random Numbers 630 17.2.1 The Chi-Square "Goodness-of-Fit" Test 630 17.2.2 The Kolmogorov-Smirnov Test 633 17.2.3 "Run" Tests 634 17.2.4 The "Gap" Test 640 17.2.5 The "Poker" Test 641 17.2.6 Statistical Test Suites 644 17.3 Exercises 644 Chapter 18: Nonuniformly Distributed "Random" Numbers 647 18.1 The Inverse Transformation Method 647 18.1.1 The Continuous Uniform Distribution 649 18.1.2 "Wedge-Shaped" Density Functions 649 18.1.3 "Triangular" Density Functions 650 18.1.4 The Exponential Distribution 652 18.1.5 The Bernoulli Distribution 653 18.1.6 An Arbitrary Discrete Distribution 653 18.2 Discrete Random Variates by Mimicry 654 18.2.1 The Binomial Distribution 654 18.2.2 The Geometric Distribution 655 18.2.3 The Poisson Distribution 656 18.3 The Accept-Reject Method 657 18.3.1 The Lognormal Distribution 660 18.4 The Composition Method 662 18.4.1 The Erlang-r Distribution 662 18.4.2 The Hyperexponential Distribution 663 18.4.3 Partitioning of the Density Function 664 18.5 Normally Distributed Random Numbers 670 18.5.1 Normal Variates via the Central Limit Theorem 670 18.5.2 Normal Variates via Accept-Reject and Exponential Bounding Function 670 18.5.3 Normal Variates via Polar Coordinates 672 18.5.4 Normal Variates via Partitioning of the Density Function 673 18.6 The Ziggurat Method 673 18.7 Exercises 676 Chapter 19: Implementing Discrete-Event Simulations 680 19.1 The Structure of a Simulation Model 680 19.2 Some Common Simulation Examples 682 19.2.1 Simulating the M/M/1 Queue and Some Extensions 682 19.2.2 Simulating Closed Networks of Queues 686 19.2.3 The Machine Repairman Problem 689 19.2.4 Simulating an Inventory Problem 692 19.3 Programming Projects 695 Chapter 20: Simulation Measurements and Accuracy 697 20.1 Sampling 697 20.1.1 Point Estimators 698 20.1.2 Interval Estimators/Confidence Intervals 704 20.2 Simulation and the Independence Criteria 707 20.3 Variance Reduction Methods 711 20.3.1 Antithetic Variables 711 20.3.2 Control Variables 713 20.4 Exercises 716 Appendix A: The Greek Alphabet 719 Appendix B: Elements of Linear Algebra 721 B.1 Vectors and Matrices 721 B.2 Arithmetic on Matrices 721 B.3 Vector and Matrix Norms 723 B.4 Vector Spaces 724 B.5 Determinants 726 B.6 Systems of Linear Equations 728 B.6.1 Gaussian Elimination and LU Decompositions 730 B.7 Eigenvalues and Eigenvectors 734 B.8 Eigenproperties of Decomposable, Nearly Decomposable, and Cyclic Stochastic Matrices 738 B.8.1 Normal Form 738 B.8.2 Eigenvalues of Decomposable Stochastic Matrices 739 B.8.3 Eigenvectors of Decomposable Stochastic Matrices 741 B.8.4 Nearly Decomposable Stochastic Matrices 743 B.8.5 Cyclic Stochastic Matrices 744 Bibliography 745 Index 749