Preface 13
Definitions 17
Chapter 1. Switching Stochastic Models 19
1.1. Random processes with discrete component 19
1.1.1.Markov and semi-Markov processes 21
1.1.2. Processes with independent increments and Markov
switching 21
1.1.3. Processes with independent increments and semi-Markov
switching 23
1.2. Switching processes 24
1.2.1. Definition of switching processes 24
1.2.2. Recurrent processes of semi-Markov type (simple case)
26
1.2.3.RPSMwithMarkov switching 26
1.2.4. General case of RPSM 27
1.2.5. Processes with Markov or semi-Markov switching 27
1.3. Switching stochastic models 28
1.3.1. Sums of random variables 29
1.3.2. Random movements 29
1.3.3. Dynamic systems in a random environment 30
1.3.4. Stochastic differential equations in a random environment
30
1.3.5. Branching processes 31
1.3.6. State-dependent flows 32
1.3.7. Two-level Markov systems with feedback 32
1.4. Bibliography 33
Chapter 2. Switching Queueing Models 37
2.1. Introduction 37
2.2. Queueing systems 38
2.2.1. Markov queueing models 38
2.2.1.1. A state-dependent system MQ/MQ/1/? 39
2.2.1.2. Queueing system MM,Q/MM,Q/1/m 40
2.2.1.3. System MQ,B/MQ,B/1/? 41
2.2.2.Non-Markov systems 42
2.2.2.1. Semi-Markov system SM/MSM,Q/1 42
2.2.2.2. System MSM,Q/MSM,Q/1/? 43
2.2.2.3. System MSM,Q/MSM,Q/1/V 44
2.2.3. Models with dependent arrival flows 45
2.2.4. Polling systems 46
2.2.5. Retrial queueing systems 47
2.3. Queueing networks 48
2.3.1. Markov state-dependent networks 49
2.3.1.1. Markov network (MQ/MQ/m/?)r 49
2.3.1.2. Markov networks (MQ,B/MQ,B/m/?)r with batches
50
2.3.2.Non-Markov networks 50
2.3.2.1. State-dependent semi-Markov networks 50
2.3.2.2. Semi-Markov networks with random batches 52
2.3.2.3. Networks with state-dependent input 53
2.4.Bibliography 54
Chapter 3. Processes of Sums of Weakly-dependent Variables
57
3.1. Limit theorems for processes of sums of conditionally
independent random variables 57
3.2. Limit theorems for sums with Markov switching 65
3.2.1. Flows of rare events 67
3.2.1.1. Discrete time 67
3.2.1.2. Continuous time 69
3.3. Quasi-ergodic Markov processes 70
3.4. Limit theorems for non-homogenous Markov processes 73
3.4.1. Convergence to Gaussian processes 74
3.4.2. Convergence to processes with independent increments
78
3.5. Bibliography 81
Chapter 4. Averaging Principle and Diffusion Approximation
for Switching Processes 83
4.1. Introduction 83
4.2. Averaging principle for switching recurrent sequences
84
4.3. Averaging principle and diffusion approximation for RPSMs
88
4.4. Averaging principle and diffusion approximation for
recurrent processes of semi-Markov type (Markov case) 95
4.4.1. Averaging principle and diffusion approximation for SMP
105
4.5. Averaging principle for RPSM with feedback 106
4.6. Averaging principle and diffusion approximation for
switching processes 108
4.6.1. Averaging principle and diffusion approximation for
processes with semi-Markov switching 112
4.7. Bibliography 113
Chapter 5. Averaging and Diffusion Approximation in
Overloaded Switching Queueing Systems and Networks 117
5.1. Introduction 117
5.2. Markov queueing models 120
5.2.1. System MQ,B/MQ,B/1/? 121
5.2.2. System MQ/MQ/1/? 124
5.2.3. Analysis of the waiting time 129
5.2.4. An output process 131
5.2.5. Time-dependent system MQ,t/MQ,t/1/? 132
5.2.6. Asystemwith impatient calls 134
5.3. Non-Markov queueing models 135
5.3.1. System GI/MQ/1/? 135
5.3.2. Semi-Markov system SM/MSM,Q/1/? 136
5.3.3. System MSM,Q/MSM,Q/1/? 138
5.3.4. System SMQ/MSM,Q/1/? 139
5.3.5. System GQ/MQ/1/? 142
5.3.6. A system with unreliable servers 143
5.3.7. Polling systems 145
5.4. Retrial queueing systems 146
5.4.1. Retrial system MQ/G/1/w.r 147
5.4.2. System M¯ /G¯/1/w.r 150
5.4.3. Retrial system M/M/m/w.r 154
5.5. Queueing networks 159
5.5.1. State-dependent Markov network (MQ/MQ/1/?)r 159
5.5.2. Markov state-dependent networks with batches 161
5.6. Non-Markov queueing networks 164
5.6.1. A network (MSM,Q/MSM,Q/1/?)r with semi-Markov
switching 164
5.6.2. State-dependent network with recurrent input 169
5.7. Bibliography 172
Chapter 6. Systems in Low Traffic Conditions 175
6.1. Introduction 175
6.2. Analysis of the first exit time from the subset of states
176
6.2.1. Definition of S-set 176
6.2.2. An asymptotic behavior of the first exit time 177
6.2.3. State space forming a monotone structure 180
6.2.4. Exit time as the time of first jump of the process of
sums with Markov switching 182
6.3. Markov queueing systems with fast service 183
6.3.1. M/M/s/m systems 183
6.3.1.1. System MM/M/l/m in a Markov environment 185
6.3.2. Semi-Markov queueing systems with fast service 188
6.4. Single-server retrial queueing model 190
6.4.1. Case 1: fast service 191
6.4.1.1. State-dependent case 194
6.4.2. Case 2: fast service and large retrial rate 195
6.4.3. State-dependent model in a Markov environment 197
6.5. Multiserver retrial queueing models 201
6.6. Bibliography 204
Chapter 7. Flows of Rare Events in Low and Heavy Traffic
Conditions 207
7.1. Introduction 207
7.2. Flows of rare events in systems with mixing 208
7.3. Asymptotically connected sets (Vn-S-sets) 211
7.3.1. Homogenous case 211
7.3.2. Non-homogenous case 214
7.4. Heavy traffic conditions 215
7.5. Flows of rare events in queueing models 216
7.5.1. Light traffic analysis in models with finite capacity
216
7.5.2. Heavy traffic analysis 218
7.6. Bibliography 219
Chapter 8. Asymptotic Aggregation of State Space 221
8.1. Introduction 221
8.2. Aggregation of finite Markov processes (stationary
behavior) 223
8.2.1. Discrete time 223
8.2.2. Hierarchic asymptotic aggregation 225
8.2.3. Continuous time 227
8.3. Convergence of switching processes 228
8.4. Aggregation of states in Markov models 231
8.4.1. Convergence of the aggregated process to a Markov process
(finite state space) 232
8.4.2. Convergence of the aggregated process with a general
state space 236
8.4.3. Accumulating processes in aggregation scheme 237
8.4.4. MP aggregation in continuous time 238
8.5. Asymptotic behavior of the first exit time from the subset
of states (non-homogenous in time case) 240
8.6. Aggregation of states of non-homogenous Markov processes
243
8.7. Averaging principle for RPSM in the asymptotically
aggregated Markov environment 246
8.7.1. Switching MP with a finite state space 247
8.7.2. Switching MP with a general state space 250
8.7.3. Averaging principle for accumulating processes in the
asymptotically aggregated semi-Markov environment 251
8.8. Diffusion approximation for RPSM in the asymptotically
aggregated Markov environment 252
8.9. Aggregation of states in Markov queueing models 255
8.9.1. System MQ/MQ/r/? with unreliable servers in heavy
traffic 255
8.9.2. System MM,Q/MM,Q/1/? in heavy traffic 256
8.10. Aggregation of states in semi-Markov queueing models
258
8.10.1. System SM/MSM,Q/1/? 258
8.10.2. System MSM,Q/MSM,Q/1/? 259
8.11. Analysis of flows of lost calls 260
8.12. Bibliography 263
Chapter 9. Aggregation in Markov Models with Fast Markov
Switching 267
9.1. Introduction 267
9.2. Markov models with fast Markov switching 269
9.2.1.Markov processes with Markov switching 269
9.2.2. Markov queueing systems with Markov type switching
271
9.2.3. Averaging in the fast Markov type environment 272
9.2.4. Approximation of a stationary distribution 274
9.3. Proofs of theorems 275
9.3.1. Proof of Theorem 9.1 275
9.3.2. Proof of Theorem 9.2 277
9.3.3. Proof of Theorem 9.3 279
9.4. Queueing systems with fast Markov type switching 279
9.4.1. System MM,Q/MM,Q/1/N 279
9.4.1.1. Averaging of states of the environment 279
9.4.1.2. The approximation of a stationary distribution 280
9.4.2. Batch system BMM,Q/BMM,Q/1/N 281
9.4.3. System M/M/s/mwith unreliable servers 282
9.4.4. Priority model MQ/MQ/m/s,N 283
9.5. Non-homogenous in time queueing models 285
9.5.1. SystemMM,Q,t/MM,Q,t/s/m with fast switching ?
averaging of states 286
9.5.2. System MM,Q/MM,Q/s/m with fast switching ?
aggregation of states 287
9.6. Numerical examples 288
9.7. Bibliography 289
Chapter 10. Aggregation in Markov Models with Fast
Semi-Markov Switching 291
10.1. Markov processes with fast semi-Markov switches 292
10.1.1.Averaging of a semi-Markov environment 292
10.1.2. Asymptotic aggregation of a semi-Markov environment
300
10.1.3. Approximation of a stationary distribution 305
10.2. Averaging and aggregation in Markov queueing systems with
semi-Markov switching 309
10.2.1.Averaging of states of the environment 309
10.2.2. Asymptotic aggregation of states of the environment
310
10.2.3. The approximation of a stationary distribution 311
10.3. Bibliography 313
Chapter 11. Other Applications of Switching Processes
315
11.1. Self-organization in multicomponent interacting Markov
systems 315
11.2. Averaging principle and diffusion approximation for
dynamic systems with stochastic perturbations 319
11.2.1. Recurrent perturbations 319
11.2.2. Semi-Markov perturbations 321
11.3. Random movements 324
11.3.1. Ergodic case 324
11.3.2. Case of the asymptotic aggregation of state space
325
11.4. Bibliography 326
Chapter 12. Simulation Examples 329
12.1. Simulation of recurrent sequences 329
12.2. Simulation of recurrent point processes 331
12.3. Simulation ofRPSM 332
12.4. Simulation of state-dependent queueing models 334
12.5. Simulation of the exit time from a subset of states of a
Markov chain 337
12.6. Aggregation of states in Markov models 340
Index 343
