随机模型计算性计算理论及应用

1 Stochastic Models 1 1.1 Stochastic Systems 1 1.1.1 The Markov Property 2 1.1.2 A Discrete-Time Markov Chain with Discrete State Space 2 1.1.3 A Continuous-Time Markov Chain with Discrete Space 6 1.1.4 A Continuous-Time Birth Death Process 8 1.1.5 Block-Structured Markov Chains 9 1.2 Motivating Practical Examples 12 1.2.1 A Queue with Server Vacations 13 1.2.2 A Queue with Repairable Servers 14 1.2.3 A Call Center 15 1.2.4 A Two-Loop Closed Production System 17 1.2.5 An E-mail Queueing System Under Attacks 20 1.3 The QBD Processes 23 1.3.1 Heuristic Expressions 23

1 Stochastic Models 1 1.1 Stochastic Systems 1 1.1.1 The Markov Property 2 1.1.2 A Discrete-Time Markov Chain with Discrete State Space 2 1.1.3 A Continuous-Time Markov Chain with Discrete Space 6 1.1.4 A Continuous-Time Birth Death Process 8 1.1.5 Block-Structured Markov Chains 9 1.2 Motivating Practical Examples 12 1.2.1 A Queue with Server Vacations 13 1.2.2 A Queue with Repairable Servers 14 1.2.3 A Call Center 15 1.2.4 A Two-Loop Closed Production System 17 1.2.5 An E-mail Queueing System Under Attacks 20 1.3 The QBD Processes 23 1.3.1 Heuristic Expressions 23 1.3.2 The LU-Type RG-Factorization 25 1.3.3 The UL-Type RG-Factorization 27 1.3.4 Linear QBD-Equations 29 1.4 Phase-Type Distributions 33 1.4.1 The Exponential Distribution 33 1.4.2 The Erlang Distribution 34 1.4.3 The PH Distribution 35 1.4.4 The Bivariate PH Distribution 40 1.4.5 The Multivariate PH Distribution 41 1.4.6 The Discrete-Time Multivariate PH Distribution 42 1.5 The Markovian Arrival Processes 43 1.5.1 The Poisson Process 43 1.5.2 The PH Renewal Process 44 1.5.3 The Markovian Modulated Poisson Process 48 1.5.4 The Markovian Modulated PH Process 49 1.5.5 The Markovian Arrival Processes 49 1.5.6 The Batch Markovian Arrival Process 52 1.5.7 The Multivariate Markovian Arrival Process 53 1.5.8 The Multivariate Batch Markovian Arrival Process 55 1.6 Matrix-Exponential Distribution 57 1.7 Notes in the Literature 60 Problems 62 References 65 2 Block-Structured Markov Chains 72 2.1 The Censoring Chains 73 2.2 The UL-type RG-Factorization 76 2.2.1 Level-Dependent Markov Chains of M/G/1 Type 84 2.2.2 Level-Independent Markov Chains of M/G/1 Type 87 2.2.3 Level-Dependent Markov Chains of GI/M/1 Type 88 2.2.4 Level-Independent Markov Chains of GI/M/1 Type 89 2.2.5 The QBD Processes 89 2.3 The LU-Type RG-Factorization 90 2.3.1 Level-Dependent Markov Chains of M/G/1 Type 94 2.3.2 Level-Dependent Markov Chains of GI/M/1 Type 95 2.3.3 The QBD Processes 95 2.4 The Stationary Probability Vector 96 2.5 A- and B-measures 98 2.6 Markov Chains with Finitely-Many Levels 109 2.6.1 The UL-Type RG-Factorization 109 2.6.2 The LU-Type RG-Factorization 110 2.6.3 The Stationary Probability Vector 113 2.7 Continuous-Time Markov Chains 114 2.7.1 The UL-type RG-factorization 115 2.7.2 The LU-Type RG-Factorization 119 2.7.3 The Stationary Probability Vector 123 2.8 Notes in the Literature 124 Problems 126 References 128 3 Markov Chains of GI/G/1 Type 131 3.1 Markov Chains of GI/G/1 Type 132 3.2 Dual Markov Chains 145 3.3 The A- and B-Measures 148 3.4 Spectral Analysis 158 3.5 Distribution of the Minimal Positive Root 165 3.5.1 The Positive Recurrence 165 3.5.2 The Null Recurrence 167 3.5.3 The Transience 167 3.5.4 The Minimal Positive Root 167 3.6 Continuous-time Chains 170 3.7 Notes in the Literature 172 Problems 173 References 174 4 Asymptotic Analysis 176 4.1 A Necessary and Sufficient Condition 177 4.2 Three Asymptotic Classes of 183 4.3 The Asymptotics Based on the Solution 185 4.3.1 A is Irreducible 185 4.3.2 Markov Chains of GI/M/1 Type 190 4.3.3 Markov Chains of M/G/1 Type 190 4.3.4 A is Reducible 191 4.4 The Asymptotics Based on the Boundary Matrices 192 4.4.1 is a Pole 193 4.4.2 is an Algebraic Singular Point 194 4.5 Long-Tailed Asymptotics of the Sequence {Rk} 198 4.6 Subexponential Asymptotics of 205 4.6.1 Markov Chains of M/G/1 Type 208 4.6.2 Regularly Varying Asymptotics of 209 4.7 Notes in the Literature 209 Problems 211 References 213 5 Markov Chains on Continuous State Space 216 5.1 Discrete-Time Markov Chains 217 5.1.1 Markov Chains of GI/G/1 Type 220 5.1.2 Markov Chains of GI/M/1 Type 220 5.1.3 Markov Chains of M/G/1 Type 220 5.1.4 QBD Processes 221 5.2 The RG-Factorizations 221 5.2.1 The UL-Type RG-Factorization 222 5.2.2 The LU-Type RG-Factorization 223 5.2.3 The Stationary Probability Distribution 224 5.2.4 Markov Chains of GI/G/1 Type 226 5.2.5 Markov Chains of GI/M/1 Type 226 5.2.6 Markov Chains of M/G/1 Type 227 5.2.7 QBD Processes 228 5.2.8 An Algorithmic Framework 228 5.3 The GI/G/1 Queue 231 5.3.1 Constructing a Markov Chain of GI/M/1 Type 231 5.3.2 Constructing a Markov Chain of M/G/1 Type 235 5.4 Continuous-Time Markov Chains 237 5.5 The QBD Processes 241 5.5.1 The UL-Type RG-Factorization 243 5.5.2 The LU-Type RG-Factorization 248 5.6 Structured Matrix Expressions 252 5.7 A CMAP/CPH/1 Queue 263 5.7.1 The CPH Distribution 263 5.7.2 The CMAP 264 5.7.3 The CMAP/CPH/1 Queue 266 5.8 Piecewise Deterministic Markov Processes 267 5.8.1 Semi-Dynamic Systems 267 5.8.2 The -Memoryless Distribution Family 269 5.8.3 Time Shift -Invariant Transition Kernel 273 5.8.4 Piecewise Deterministic Markov Processes 274 5.8.5 The Stationary Distribution 275 5.8.6 The GI/G/k Queue 279 5.9 Notes in the Literature 284 Problems 285 References 286 6 Block-Structured Markov Renewal Processes 288 6.1 The Censoring Markov Renewal Processes 289 6.2 The UL-Type RG-Factorization 294 6.2.1 Level-Dependent Markov Renewal Processes of M/G/1 Type 302 6.2.2 Level-Dependent Markov Renewal Processes of GI/M/1 Type 303 6.2.3 Markov Renewal Equations 304 6.3 The LU-Type RG-Factorization 305 6.4 Finite Levels 308 6.4.1 The UL-Type RG-Factorization 309 6.4.2 The LU-Type RG-Factorization 310 6.5 Markov Renewal Processes of GI/G/1 Type 311 6.6 Spectral Analysis 317 6.7 The First Passage Times 321 6.7.1 An Algorithmic Framework 321 6.7.2 Markov Renewal Processes of GI/G/1 Type 322 6.8 Notes in the Literature 326 Problems 327 References 328 7 Examples of Practical Applications 331 7.1 Processor-Sharing Queues 332 7.2 Fluid Queues 338 7.3 A Queue with Negative Customers 345 7.3.1 The Supplementary Variables 346 7.3.2 A Markov Chain of GI/G/1 Type 348 7.3.3 The Stationary Queue Length 355 7.3.4 The Busy Period 356 7.4 A Repairable Retrial Queue 361 7.4.1 The Supplementary Variables 362 7.4.2 A Level-Dependent Markov Chain of M/G/1 Type 364 7.4.3 The Stationary Performance Measures 371 7.5 Notes in the Literature 375 7.5.1 The Processor-Sharing Queues 375 7.5.2 The Fluid Queues 376 7.5.3 The Queues with Negative Customers 377 7.5.4 The Retrial Queues 378 Problems 379 References 381 8 Transient Solution 389 8.1 Transient Probability 390 8.1.1 Discrete-Time Markov Chains 390 8.1.2 An Approximate Algorithm 392 8.1.3 Continuous-Time Markov Chains 395 8.2 The First Passage Times 401 8.2.1 Discrete-Time GPH Distribution 402 8.2.2 Continuous-Time GPH Distribution 406 8.2.3 GMAPs 409 8.2.4 Time-Inhomogeneous PH(t) Distribution 410 8.2.5 Time-Inhomogeneous MAP (t) 411 8.2.6 A Time-Inhomogeneous MAP(t)/PH(t)/1 Queue 411 8.3 The Sojourn Times 412 8.3.1 Discrete-Time Markov Chains 412 8.3.2 Continuous-Time Markov Chains 417 8.4 Time-Inhomogeneous Discrete-Time Models 420 8.4.1 The Transient Probability Vector 421 8.4.2 The Asymptotic Periodic Distribution 422 8.5 Notes in the Literature 426 Problems 427 References 428 9 Quasi-Stationary Distributions 432 9.1 Finitely-Many Levels 433 9.1.1 The UL-Type RG-Factorization 434 9.1.2 The LU-Type RG-Factorization 435 9.1.3 State -Classification and Quasi-stationary Distribution 437 9.2 Infinitely-Many Levels 438 9.2.1 The UL-Type RG-Factorization 439 9.2.2 Two Sets of Expressions 440 9.2.3 The LU-Type RG-Factorization 443 9.3 Markov Chains of M/G/1 Type 447 9.3.1 The UL-Type RG-Factorization 447 9.3.2 The State -Classification 450 9.3.3 Two Sets of Expressions 452 9.3.4 Conditions for -Positive Recurrence 455 9.4 Markov Chains of GI/M/1 Type 457 9.4.1 Spectral Analysis 461 9.4.2 Two Sets of Expressions 468 9.4.3 Conditions for -Positive Recurrence 478 9.5 Markov Chains of GI/G/1 Type 481 9.6 Level-Dependent QBD Processes 490 9.6.1 The UL-Type RG-Factorization 491 9.6.2 Conditions for -Positive Recurrence 497 9.7 Continuous-Time Markov Chains 500 9.7.1 The UL-Type RG-Factorization 502 9.7.2 The LU-Type RG-Factorization 506 9.8 Decay Rate for the GPH Distribution 507 9.8.1 The Discrete-Time PH Distribution with Finitely Many Phases 507 9.8.2 The Discrete-Time GPH Distribution with Infinitely-many Phases 510 9.8.3 The Level-Dependent QBD Processes 511 9.8.4 The Continuous-Time GPH Distribution 513 9.8.5 The Level-Dependent Markov Chains of M/G/1 Type 514 9.8.6 The Level-Dependent Markov Chains of GI/M/1 Type 516 9.9 QBD Processes with Infinitely-Many Phases 517 9.10 Notes in the Literature 521 Problems 522 References 523 10 Markov Reward Processes 526 10.1 Continuous-Time Markov Reward Processes 527 10.1.1 The Expected Instantaneous Reward Rate at Time t 529 10.1.2 The nth Moment of the Instantaneous Reward Rate at Time t 529 10.1.3 The Distribution of the Instantaneous Reward Rate at Time t 529 10.1.4 The Accumulated Reward Over [0,t) 530 10.1.5 The Expected Accumulated Reward Ф(t) Over [0,t) 530 10.1.6 The nth Moment of the Accumulated Reward Ф(t) Over [0,t) 530 10.2 The Transient Accumulated Rewards 531 10.3 The First Accumulated Time 534 10.4 Computation of the Reward Moments 536 10.4.1 The Moments of the Transient Accumulated Reward 536 10.4.2 The Moments of the First Accumulated Time 538 10.5 Accumulated Reward in a QBD Process 542 10.6 An Up-Type Reward Process in Finitely-Many Levels 548 10.7 An Up-Type Reward Process in Infinitely-Many Levels 554 10.8 A Down-Type Reward Process 560 10.9 Discrete-Time Markov Reward Processes 565 10.10 Notes in the Literature 568 Problems 568 References 570 11 Sensitivity Analysis and Evolutionary Games 574 11.1 Perturbed Discrete-Time Markov Chains 575 11.1.1 Markov Chains with Finitely-Many Levels 575 11.1.2 Markov Chains with Infinitely-Many Levels 579 11.1.3 The Realization Matrix and Potential Vector 581 11.1.4 The Censored Structure in Sensitivity Analysis 582 11.1.5 The Transient Performance Measure 584 11.1.6 The Discounted Performance Measure 584 11.2 Two Important Markov Chains 584 11.2.1 Perturbed Markov Chains of GI/M/1 Type 585 11.2.2 Perturbed Markov Chains of M/G/1 Type 588 11.3 Perturbed Continuous-Time Markov Chains 592 11.4 Perturbed Accumulated Reward Processes 597 11.5 A Perturbed MAP/PH/1 Queue 600 11.5.1 A Perturbed PH Distribution 600 11.5.2 A Perturbed MAP 601 11.5.3 A Perturbed MAP/PH/1 Queue 602 11.6 Symmetric Evolutionary Games 605 11.7 Constructively Perturbed Birth Death Process 618 11.7.1 An Embedded Chain 618 11.7.2 A Probabilistic Construction 622 11.8 Asymmetric Evolutionary Games 626 11.8.1 A 2 2 Game with Independent Structure 626 11.8.2 A 2 2 Game with Dependent Structure 631 11.8.3 A 2 2 Game with Information Interaction 636 11.8.4 A 3 2 Asymmetric Evolutionary Game 640 11.9 Notes in the Literature 645 Problems 646 References 647 Appendix 652 Appendix A Matrix Notation and Computation 652 A.1 Kronecker Product 652 A.2 Perron-Frobenius Theory 653 A.3 Inverses of Matrices of Infinite Size 654 References 658 Appendix B Heavy-Tailed Distributions 658 References 667 Index 669

本书介绍了随机模型中计算技术的主要基础理论，总结了近十年来国内外所取得的新成果与进展。它构造性地建立了一般马尔可夫过程的RG-分解，其中RG-分解是马尔可夫过程与高斯消元法的完美结合，为求解无限维（或大型）线性方程组提供了有效途径。全书共分为三个部分。第一部分描述了如何把排队系统、可靠性工程、制造系统、计算机网络、交通系统、服务系统等应用随机模型转化为块型结构的马尔可夫过程，这为研究许多实际系统的性能评价、优化与决策提供了统一的数学理论框架。第二部分提供了研究随机模型的计算理论基础，包括Censoring不变性、RG-分解、RG-对偶性、谱分析、稳态计算、瞬态计算、渐近性分析、敏感性分析等。第三部分研究了随机模型中的一些热点问题，例如拟平稳分布、连续状态马尔可夫过程、马尔可夫报酬过程、马尔可夫决策过程、演化博弈论等。　　本书的读者对象为代数、应用概率、运筹学、管理科学、制造系统、计算机网络、交通系统、服务系统、生物工程等领域中高年级大学生、研究生、科技人员与工程技术人员。