Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Perfomance Modeling

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