Li Constructive Computation in Stochastic Models with Applications

The RG-Factorizations
1. Auflage 2011
ISBN: 978-3-642-11492-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 650 Seiten

'Constructive Computation in Stochastic Models with Applications: The RG-Factorizations' provides a unified, constructive and algorithmic framework for numerical computation of many practical stochastic systems. It summarizes recent important advances in computational study of stochastic models from several crucial directions, such as stationary computation, transient solution, asymptotic analysis, reward processes, decision processes, sensitivity analysis as well as game theory. Graduate students, researchers and practicing engineers in the field of operations research, management sciences, applied probability, computer networks, manufacturing systems, transportation systems, insurance and finance, risk management and biological sciences will find this book valuable. Dr. Quan-Lin Li is an Associate Professor at the Department of Industrial Engineering of Tsinghua University, China.

Autoren/Hrsg.

Li, Quan-Lin

Inhaltsverzeichnis

1;Preface;8
2;Table of Contents;14
3;1 Stochastic Models;22
3.1;1.1 Stochastic Systems;22
3.1.1;1.1.1 The Markov Property;23
3.1.2;1.1.2 A Discrete-Time Markov Chain with Discrete State Space;23
3.1.3;1.1.3 A Continuous-Time Markov Chain with Discrete Space;27
3.1.4;1.1.4 A Continuous-Time Birth Death Process;29
3.1.5;1.1.5 Block-Structured Markov Chains;30
3.2;1.2 Motivating Practical Examples;33
3.2.1;1.2.1 A Queue with Server Vacations;34
3.2.2;1.2.2 A Queue with Repairable Servers;35
3.2.3;1.2.3 A Call Center;36
3.2.4;1.2.4 A Two-Loop Closed Production System;38
3.2.5;1.2.5 An E-mail Queueing System Under Attacks;41
3.3;1.3 The QBD Processes;44
3.3.1;1.3.1 Heuristic Expressions;44
3.3.2;1.3.2 The LU-Type RG-Factorization;46
3.3.3;1.3.3 The UL-Type RG-Factorization;48
3.3.4;1.3.4 Linear QBD-Equations;50
3.3.4.1;1.3.4.1 The Homogeneous Linear QBD-Equations;51
3.3.4.2;1.3.4.2 The Nonhomogeneous Linear QBD-Equations;52
3.4;1.4 Phase-Type Distributions;54
3.4.1;1.4.1 The Exponential Distribution;54
3.4.2;1.4.2 The Erlang Distribution;55
3.4.3;1.4.3 The PH Distribution;56
3.4.4;1.4.4 The Bivariate PH Distribution;61
3.4.5;1.4.5 The Multivariate PH Distribution;62
3.4.6;1.4.6 The Discrete-Time Multivariate PH Distribution;63
3.5;1.5 The Markovian Arrival Processes;64
3.5.1;1.5.1 The Poisson Process;64
3.5.2;1.5.2 The PH Renewal Process;65
3.5.3;1.5.3 The Markovian Modulated Poisson Process;69
3.5.4;1.5.4 The Markovian Modulated PH Process;70
3.5.5;1.5.5 The Markovian Arrival Processes;70
3.5.6;1.5.6 The Batch Markovian Arrival Process;73
3.5.7;1.5.7 The Multivariate Markovian Arrival Process;74
3.5.8;1.5.8 The Multivariate Batch Markovian Arrival Process;76
3.6;1.6 Matrix-Exponential Distribution;78
3.7;1.7 Notes in the Literature;81
3.8;References;86
4;2 Block-Structured Markov Chains;93
4.1;2.1 The Censoring Chains;94
4.2;2.2 The UL-type RG-Factorization;97
4.2.1;2.2.1 Level-Dependent Markov Chains of M/G/1 Type;105
4.2.2;2.2.2 Level-Independent Markov Chains of M/G/1 Type;108
4.2.3;2.2.3 Level-Dependent Markov Chains of GI/M/1 Type;109
4.2.4;2.2.4 Level-Independent Markov Chains of GI/M/1 Type;110
4.2.5;2.2.5 The QBD Processes;110
4.3;2.3 The LU-Type RG-Factorization;111
4.3.1;2.3.1 Level-Dependent Markov Chains of M/G/1 Type;115
4.3.2;2.3.2 Level-Dependent Markov Chains of GI/M/1 Type;116
4.3.3;2.3.3 The QBD Processes;116
4.4;2.4 The Stationary Probability Vector;117
4.5;2.5 A- and B-measures;119
4.6;2.6 Markov Chains with Finitely-Many Levels;130
4.6.1;2.6.1 The UL-Type RG-Factorization;130
4.6.2;2.6.2 The LU-Type RG-Factorization;131
4.6.3;2.6.3 The Stationary Probability Vector;134
4.7;2.7 Continuous-Time Markov Chains;135
4.7.1;2.7.1 The UL-type RG-factorization;136
4.7.2;2.7.2 The LU-Type RG-Factorization;140
4.7.3;2.7.3 The Stationary Probability Vector;144
4.8;2.8 Notes in the Literature;145
4.9;References;149
5;3 Markov Chains of GI/G/1 Type;152
5.1;3.1 Markov Chains of GI/G/1 Type;153
5.2;3.2 Dual Markov Chains;166
5.3;3.3 The A- and B-Measures;169
5.4;3.4 Spectral Analysis;179
5.5;3.5 Distribution of the Minimal Positive Root;186
5.5.1;3.5.1 The Positive Recurrence;186
5.5.2;3.5.2 The Null Recurrence;188
5.5.3;3.5.3 The Transience;188
5.5.4;3.5.4 The Minimal Positive Root;188
5.6;3.6 Continuous-time Chains;191
5.7;3.7 Notes in the Literature;193
5.8;References;195
6;4 Asymptotic Analysis;197
6.1;4.1 A Necessary and Sufficient Condition;198
6.2;4.2 Three Asymptotic Classes of {p };204
6.3;4.3 The Asymptotics Based on the Solution n;206
6.3.1;4.3.1 A is Irreducible;206
6.3.2;4.3.2 Markov Chains of Gi/m/1Type;211
6.3.3;4.3.3 Markov Chains of M/G/1 Type;211
6.3.4;4.3.4 A is Reducible;212
6.4;4.4 The Asymptotics Based on the Boundary Matrices;213
6.4.1;4.4.1 .D is a Pole;214
6.4.2;4.4.2 . D is an Algebraic Singular Point;215
6.5;4.5 Long-Tailed Asymptotics of the Sequence {Rk};219
6.6;4.6 Subexponential Asymptotics of {p k};226
6.6.1;4.6.1 Markov Chains of M/G/1 Type;229
6.6.2;4.6.2 Regularly Varying Asymptotics of {rk};230
6.7;4.7 Notes in the Literature;230
6.8;References;234
7;5 Markov Chains on Continuous State Space;237
7.1;5.1 Discrete-Time Markov Chains;238
7.1.1;5.1.1 Markov Chains of GI/G/1 Type;241
7.1.2;5.1.2 Markov Chains of GI/M/1 Type;241
7.1.3;5.1.3 Markov Chains of M/G/1 Type;241
7.1.4;5.1.4 QBD Processes;242
7.2;5.2 The RG-Factorizations;242
7.2.1;5.2.1 The UL-Type RG-Factorization;243
7.2.2;5.2.2 The LU-Type RG-Factorization;244
7.2.3;5.2.3 The Stationary Probability Distribution;245
7.2.4;5.2.4 Markov Chains of GI/G/1 Type;247
7.2.5;5.2.5 Markov Chains of GI/M/1 Type;247
7.2.6;5.2.6 Markov Chains of M/G/1 Type;248
7.2.7;5.2.7 QBD Processes;249
7.2.8;5.2.8 An Algorithmic Framework;249
7.2.8.1;5.2.8.1 A Laguerre-Polynomial Orthogonal Base;249
7.2.8.2;5.2.8.3 A Finite-Interval Orthogonal Base;250
7.3;5.3 The GI/G/1 Queue;252
7.3.1;5.3.1 Constructing a Markov Chain of GI/M/1 Type;252
7.3.2;5.3.2 Constructing a Markov Chain of M/G/1 Type;256
7.4;5.4 Continuous-Time Markov Chains;258
7.5;5.5 The QBD Processes;262
7.5.1;5.5.1 The UL-Type RG-Factorization;264
7.5.2;5.5.2 The LU-Type RG-Factorization;269
7.6;5.6 Structured Matrix Expressions;273
7.7;5.7 A CMAP/CPH/1 Queue;284
7.7.1;5.7.1 The CPH Distribution;284
7.7.2;5.7.2 The CMAP;285
7.7.3;5.7.3 The CMAP/CPH/1 Queue;287
7.8;5.8 Piecewise Deterministic Markov Processes;288
7.8.1;5.8.1 Semi-Dynamic Systems;288
7.8.2;5.8.2 The .-Memoryless Distribution Family ;290
7.8.3;5.8.3 Time Shift . -Invariant Transition Kernel ;294
7.8.4;5.8.4 Piecewise Deterministic Markov Processes;295
7.8.5;5.8.5 The Stationary Distribution;296
7.8.6;5.8.6 The GI/G/k Queue;300
7.8.6.1;5.8.6.1 The State Change is Induced by a Service Event;300
7.8.6.2;5.8.6.2 The State Change is Induced by an Arrival Event;302
7.8.6.3;5.8.6.3 An Embedded Markov Chain of GI/M/1 Type;302
7.9;5.9 Notes in the Literature;305
7.10;References;307
8;6 Block-Structured Markov Renewal Processes;309
8.1;6.1 The Censoring Markov Renewal Processes;310
8.2;6.2 The UL-Type RG-Factorization;315
8.2.1;6.2.1 Level-Dependent Markov Renewal Processes of M/G/1 Type;323
8.2.2;6.2.2 Level-Dependent Markov Renewal Processes of GI/M/1 Type;324
8.2.3;6.2.3 Markov Renewal Equations;325
8.3;6.3 The LU-Type RG-Factorization;326
8.4;6.4 Finite Levels;329
8.4.1;6.4.1 The UL-Type RG-Factorization;330
8.4.2;6.4.2 The LU-Type RG-Factorization;331
8.5;6.5 Markov Renewal Processes of GI/G/1 Type;332
8.6;6.6 Spectral Analysis;338
8.7;6.7 The First Passage Times;342
8.7.1;6.7.1 An Algorithmic Framework;342
8.7.2;6.7.2 Markov Renewal Processes of GI/G/1 Type;343
8.8;6.8 Notes in the Literature;347
8.9;References;349
9;7 Examples of Practical Applications;352
9.1;7.1 Processor-Sharing Queues;353
9.2;7.2 Fluid Queues;359
9.3;7.3 A Queue with Negative Customers;366
9.3.1;7.3.1 The Supplementary Variables;367
9.3.2;7.3.2 A Markov Chain of GI/G/1 Type;369
9.3.3;7.3.3 The Stationary Queue Length;376
9.3.4;7.3.4 The Busy Period;377
9.4;7.4 A Repairable Retrial Queue;382
9.4.1;7.4.1 The Supplementary Variables;383
9.4.2;7.4.2 A Level-Dependent Markov Chain of M/G/1 Type;385
9.4.3;7.4.3 The Stationary Performance Measures;392
9.5;7.5 Notes in the Literature;396
9.5.1;7.5.1 The Processor-Sharing Queues;396
9.5.2;7.5.2 The Fluid Queues;397
9.5.3;7.5.3 The Queues with Negative Customers;398
9.5.4;7.5.4 The Retrial Queues;399
9.6;References;402
10;8 Transient Solution;410
10.1;8.1 Transient Probability;411
10.1.1;8.1.1 Discrete-Time Markov Chains;411
10.1.2;8.1.2 An Approximate Algorithm;413
10.1.3;8.1.3 Continuous-Time Markov Chains;416
10.2;8.2 The First Passage Times;422
10.2.1;8.2.1 Discrete-Time GPH Distribution;423
10.2.2;8.2.2 Continuous-Time GPH Distribution;427
10.2.3;8.2.3 GMAPs;430
10.2.4;8.2.4 Time-Inhomogeneous PH(t) Distribution;431
10.2.5;8.2.5 Time-Inhomogeneous MAP (t);432
10.2.6;8.2.6 A Time-Inhomogeneous MAP(t)/PH(t)/1 Queue;432
10.3;8.3 The Sojourn Times;433
10.3.1;8.3.1 Discrete-Time Markov Chains;433
10.3.2;8.3.2 Continuous-Time Markov Chains;438
10.4;8.4 Time-Inhomogeneous Discrete-Time Models;441
10.4.1;8.4.1 The Transient Probability Vector;442
10.4.2;8.4.2 The Asymptotic Periodic Distribution;443
10.5;8.5 Notes in the Literature;447
10.6;References;449
11;9 Quasi-Stationary Distributions;453
11.1;9.1 Finitely-Many Levels;454
11.1.1;9.1.1 The UL-Type RG-Factorization;455
11.1.2;9.1.2 The LU-Type RG-Factorization;456
11.1.3;9.1.3 State a -Classification and Quasi-stationary Distribution;458
11.2;9.2 Infinitely-Many Levels;459
11.2.1;9.2.1 The UL-Type RG-Factorization;460
11.2.2;9.2.2 Two Sets of Expressions;461
11.2.3;9.2.3 The LU-Type RG-Factorization;464
11.3;9.3 Markov Chains of M/G/1 Type;468
11.3.1;9.3.1 The UL-Type RG-Factorization;468
11.3.2;9.3.2 The State a -Classification;471
11.3.3;9.3.3 Two Sets of Expressions;473
11.3.4;9.3.4 Conditions for a -Positive Recurrence;476
11.4;9.4 Markov Chains of GI/M/1 Type;478
11.4.1;9.4.1 Spectral Analysis;482
11.4.2;9.4.2 Two Sets of Expressions;489
11.4.3;9.4.3 Conditions for a -Positive Recurrence;499
11.5;9.5 Markov Chains of GI/G/1 Type;502
11.6;9.6 Level-Dependent QBD Processes;511
11.6.1;9.6.1 The UL-Type RG-Factorization;512
11.6.2;9.6.2 Conditions for a -Positive Recurrence;518
11.7;9.7 Continuous-Time Markov Chains;521
11.7.1;9.7.1 The UL-Type RG-Factorization;523
11.7.2;9.7.2 The LU-Type RG-Factorization;527
11.8;9.8 Decay Rate for the GPH Distribution;528
11.8.1;9.8.1 The Discrete-Time PH Distribution with Finitely Many Phases;528
11.8.2;9.8.2 The Discrete-Time GPH Distribution with Infinitely-manyPhases;531
11.8.3;9.8.3 The Level-Dependent QBD Processes;532
11.8.4;9.8.4 The Continuous-Time GPH Distribution;534
11.8.5;9.8.5 The Level-Dependent Markov Chains of M/G/1 Type;535
11.8.6;9.8.6 The Level-Dependent Markov Chains of GI/M/1 Type;537
11.9;9.9 QBD Processes with Infinitely-Many Phases;538
11.10;9.10 Notes in the Literature;542
11.11;References;544
12;10 Markov Reward Processes;547
12.1;10.1 Continuous-Time Markov Reward Processes;548
12.1.1;10.1.1 The Expected Instantaneous Reward Rate at Time t;550
12.1.2;10.1.2 The nth Moment of the Instantaneous Reward Rate at Time t;550
12.1.3;10.1.3 The Distribution of the Instantaneous Reward Rate at Time t;550
12.1.4;10.1.4 The Accumulated Reward Over [0,t);551
12.1.5;10.1.5 The Expected Accumulated Reward ..(t) Over [0,t);551
12.1.6;10.1.6 The nth Moment of the Accumulated Reward ..(t) Over [0,t);551
12.2;10.2 The Transient Accumulated Rewards;552
12.3;10.3 The First Accumulated Time;555
12.4;10.4 Computation of the Reward Moments;557
12.4.1;10.4.1 The Moments of the Transient Accumulated Reward;557
12.4.2;10.4.2 The Moments of the First Accumulated Time;559
12.5;10.5 Accumulated Reward in a QBD Process;563
12.6;10.6 An Up-Type Reward Process in Finitely-Many Levels;569
12.7;10.7 An Up-Type Reward Process in Infinitely-Many Levels;575
12.8;10.8 A Down-Type Peward Process;581
12.9;10.9 Discrete-Time Markov Reward Processes;586
12.10;10.10 Notes in the Literature;589
12.11;References;591
13;11 Sensitivity Analysis and Evolutionary Games;595
13.1;11.1 Perturbed Discrete-Time Markov Chains;596
13.1.1;11.1.1 Markov Chains with Finitely-Many Levels;596
13.1.2;11.1.2 Markov Chains with Infinitely-Many Levels;600
13.1.3;11.1.3 The Realization Matrix and Potential Vector;602
13.1.4;11.1.4 The Censored Structure in Sensitivity Analysis;603
13.1.5;11.1.5 The Transient Performance Measure;605
13.2;11.2 Two Important Markov Chains;605
13.2.1;11.2.1 Perturbed Markov Chains of GI/M/1 Type;606
13.2.2;11.2.2 Perturbed Markov Chains of M/G/1 Type;609
13.3;11.3 Perturbed Continuous-Time Markov Chains;613
13.4;11.4 Perturbed Accumulated Reward Processes;618
13.5;11.5 A Perturbed MAP/PH/1 Queue;621
13.5.1;11.5.1 A Perturbed PH Distribution;621
13.5.2;11.5.2 A Perturbed MAP;622
13.5.3;11.5.3 A Perturbed MAP/PH/1 Queue;623
13.6;11.6 Symmetric Evolutionary Games;626
13.7;11.7 Constructively Perturbed Birth Death Process;639
13.7.1;11.7.1 An Embedded Chain;639
13.7.2;11.7.2 A Probabilistic Construction;643
13.8;11.8 Asymmetric Evolutionary Games;647
13.8.1;11.8.1 A 2 x 2 Game with Independent Structure ;647
13.8.2;11.8.2 A 2 x 2 Game with Dependent Structure ;652
13.8.3;11.8.3 A 2 x 2 Game with Information Interaction ;657
13.8.4;11.8.4 A 3 x 2 Asymmetric Evolutionary Game ;661
13.9;11.9 Notes in the Literature;666
13.10;References;668
14;Appendix;673
14.1;Appendix A Matrix Notation and Computation;673
14.1.1;A.1 Kronecker Product;673
14.1.2;A.2 Perron-Frobenius Theory;674
14.1.3;A.3 Inverses of Matrices of Infinite Size;675
14.2;Appendix B Heavy-Tailed Distributions;679
14.3;References;688
15;Index;690