Preface ix
1 Probability Review 1
1.1 Interpreting and Using Probabilities 2
1.2 Sample Spaces and Events 3
1.3 Probability 4
1.4 Random Variables 6
1.5 Probability Distributions 6
1.6 Joint, Marginal, and Conditional Distributions 11
1.7 Expectation 14
1.8 Variance and Other Moments 16
1.9 The Law of Total Probability 18
1.10 Discrete Probability Distributions 20
1.11 Continuous Probability Distributions 23
1.12 Where Do Distributions Come From? 26
1.13 The Binomial Process 28
1.14 Recommended Reading 29
2 Formulating Markov Chain Models 32
2.1 An Example 33
2.2 Modeling the Progress of Time 34
2.3 Modeling Possibilities as States 36
2.4 Simplifying Assumptions 38
2.5 Modeling Changes of State as Transitions 40
2.6 Obtaining the Data 45
2.7 Another Example 46
2.8 A Case Study 47
2.9 Higher Order Markov Chains 50
2.10 Reducing the Number of States 52
2.11 Nonstationary Markov Chains 53
2.12 Other Example 54
2.13 Summary 67
2.14 Recommended Reading 67
3 Markov Chain Calculations 72
3.1 Walk Probabilities 73
3.2 Transition Probabilities 74
3.3 State Probabilities 78
3.4 A Numerical Example 79
3.5 Expected Number of Visits 80
3.6 Sojourn Times 82
3.7 First Passage and Return Probabilities 83
3.8 Computational Formulas for All Markov Chains 86
3.9 Special Classes of Markov Chains 86
3.10 Steady-State Probabilities 87
3.11 The Uses of Steady-State Results 92
3.12 Mean First Passage Times 93
3.13 Computational Formulas for Ergodic Markov Chains 96
3.14 Terminating Markov Chains 96
3.15 Expected Number of Visits 98
3.16 Expected Duration of a Terminating Process 99
3.17 Absorption Probabilities 100
3.18 Hit Probabilities 102
3.19 Conditional Mean First Passage Times to Absorbing States 103
3.20 Computational Formulas for Terminating Processes 105
3.21 Call Center Calculations 105
3.22 Classification Terminology 106
3.23 Additional Complications in Infinite Chains 111
3.24 Dealing with a Reducible Process 112
3.25 Periodic Chains 113
3.26 Ergodic Chains 114
3.27 Recommended Reading 115
4 Rewards on Markov Chains 119
4.1 Formulation 120
4.2 A Numerical Example 120
4.3 Expected Total Reward 121
4.4 Random Variable Rewards 124
4.5 Semi-Markov Processes 126
4.6 Limiting Results for Ergodic Processes 126
4.7 Total Reward for Terminating Processes 130
4.8 Case Study 132
4.9 Discounting 133
4.10 Case Study 135
4.11 Recommended Reading 137
5 Continuous Time Markov Processes 140
5.1 An Example 141
5.2 Interpreting Transition Rates 146
5.3 The Assumptions Reconsidered 149
5.4 Aging Does Not Affect the Transition Time 150
5.5 Competing Transitions 152
5.6 Sojourn Times 153
5.7 Embedded Markov Chains 154
5.8 Deriving the Differential Equations 155
5.9 Solving the Differential Equations 157
5.10 State Probabilities 159
5.11 First Passage Probability Functions 159
5.12 State Classification 160
5.13 Steady-State Probabilities 161
5.14 Other Computable Quantities 163
5.15 Case Study 165
5.16 Birth-Death Processes 167
5.17 The Poisson Process 169
5.18 Properties of Poisson Processes 171
5.19 Khintchine’s Theorem 172
5.20 Phase-Type Distributions 173
5.21 Conclusions 175
5.22 Recommended Reading 175
6 Queueing Models 179
6.1 An Example 180
6.2 General Characteristics 182
6.3 Performance Measures 186
6.4 Relations Among Performance Measures 188
6.5 Little’s Formula 190
6.6 Markovian Queueing Models 191
6.7 The M/M/1 Model 193
6.8 The Significance of Traffic Intensity 198
6.9 Unnormalized Solutions 200
6.10 Limited Queue Capacity 202
6.11 Multiple Servers 204
6.12 Is It Better to Merge or Separate Servers? 207
6.13 Which is Better: More Servers or Faster Servers 208
6.14 Case Study: A Grain Elevator 209
6.15 The M/M/c/c and M/M/1 Models 210
6.16 Finite Sources 212
6.17 The Machine Repairmen Model 214
6.18 Numerical Calculations Using a Spreadsheet 214
6.19 Queue Discipline Variations 217
6.20 Non-Markovian Queues 218
6.21 The M/G/1 Model 219
6.22 Approximate Solutions for Other Models 220
6.23 Conclusion 221
6.24 Recommended Reading 221
7 Networks of Queues 225
7.1 Open Networks of Markovian Queues 226
7.2 An Example Open Network 227
7.3 Extensions 228
7.4 Closed Networks 229
7.5 A Preliminary Example 229
7.6 Relative Arrival Rates 230
7.7 Unnormalized Solutions for Individual Stations 232
7.8 Assembling the Pieces of the Solution 234
7.9 Calculating the Normalization Constant 235
7.10 Performance Measures for Closed Networks 237
7.11 Creating a Closed Model 239
7.12 Case Study 242
7.13 Extensions 247
7.14 Approximate Methods 247
7.15 Recommended Reading 248
8 Using the Transition Diagram to Compute 251
8.1 An Example 252
8.2 Definitions 254
8.3 Steady-State Probabilities 258
8.4 How to Generate All In-trees 259
8.5 Check Your Understanding 262
8.6 Generalization to Other Quantities 263
8.7 Mean First Passage Times 264
8.8 Results for Terminating Processes 265
8.9 How to Simplify the Arithmetic 266
8.10 How to Systematically Generate r-Forests 267
8.11 Summary of Results 267
8.12 How to Remember the Formulas 268
8.13 Advanced Topics 268
8.14 Recommended Reading 269
Appendix 1 271
Appendix 2 278
Index 300
