Max-Plus linear stochastic systems and perturbation analysis

Title:

Personal Author:

Heidergott, Bernd F.

Series:

The international series on discrete event dynamic systems ; 15

Publication Information:

New York, NY : Springer, 2006

ISBN:

9780387352060

Subject Term:

Stochastic systems

Discrete-time systems

Perturbation (Mathematics)

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... Razak School	30000010159672	QA402.37 H44 2006	Open Access Book	Book	Searching... Unknown

During the last decade, the area of stochastic max-plus linear systems has witnessed a rapid development, which created a growing interest in this area. This book provides a thorough treatment of the theory of stochastic max-plus linear systems. Max-plus algebra is an algebraic approach to discrete event systems (DES), like queuing networks that are prone to synchronization. Perturbation analysis studies the sensitivity of the performance of DES with respect to changes in a particular system parameter.

The first part of the book addresses modeling issues and stability theory for stochastic max-plus systems. The second part of the book treats perturbation analysis of max-plus systems: a calculus for differentiation of max-plus systems is developed. This calculus leads to numerical evaluations of performance indices of max-plus linear stochastic systems, such as the Lyapunov exponent or waiting times.

Preface	p. V
I Max-Plus Algebra	p. 1
1 Max-Plus Linear Stochastic Systems	p. 3
1.1 The Max-Plus Algebra	p. 3
1.2 Heap of Pieces	p. 7
1.3 The Projective Space	p. 10
1.4 Petri Nets	p. 10
1.4.1 Basic Definitions	p. 10
1.4.2 The Max-Plus Recursion for Firing Times	p. 12
1.4.3 Autonomous Systems and Irreducible Matrices	p. 15
1.4.4 The Max-Plus Recursion for Waiting Times in Non-Autonomous Event Graphs	p. 17
1.5 Queueing Systems	p. 20
1.5.1 Queueing Networks	p. 21
1.5.2 Examples of Max-Plus Linear Systems	p. 24
1.5.3 Sample Path Dynamics	p. 30
1.5.4 Invariant Queueing Networks	p. 44
1.5.5 Condition (A) Revisited	p. 46
1.5.6 Beyond Fixed Support: Patterns	p. 48
1.6 Bounds and Metrics	p. 49
1.6.1 Real-Valued Upper Bounds for Semirings	p. 49
1.6.2 General Upper Bounds over the Max-Plus Semiring	p. 51
1.6.3 The Max-Plus Semiring as a Metric Space	p. 54
2 Ergodic Theory	p. 59
2.1 Deterministic Limit Theory	p. 60
2.2 Subadditive Ergodic Theory	p. 66
2.2.1 The Irreducible Case	p. 71
2.2.2 The Reducible Case	p. 75
2.2.3 Variations and Extensions	p. 80
2.3 Stability Analysis of Waiting Times	p. 86
2.4 Harris Recurrence	p. 93
2.5 Limits in the Projective Space	p. 99
2.5.1 Countable Models	p. 100
2.5.2 General Models	p. 102
2.5.3 Periodic Regimes of Deterministics Max-Plus DES	p. 105
2.5.4 The Cycle Formula	p. 106
2.6 Lyapunov Exponents via Second Order Limits	p. 107
2.6.1 The Projective Space	p. 108
2.6.2 Backward Coupling	p. 111
II Perturbation Analysis	p. 117
3 A Max-Plus Differential Calculus	p. 119
3.1 Measure-Valued Differentiation	p. 120
3.2 The Space C[subscript p]	p. 128
3.3 D-Derivatives of Random Matrices	p. 132
3.4 An Algebraic Tool for D-Derivatives	p. 136
3.5 Rules for C[subscript p]-Differentiation of Random Matrices	p. 141
3.6 Max-Plus Gradient Estimators	p. 146
3.6.1 Homogeneous Recurrence Relations	p. 147
3.6.2 Inhomogeneous Recurrence Relations	p. 149
4 Higher-Order D-Derivatives	p. 151
4.1 Higher Order D-Derivatives	p. 151
4.2 Higher Order Differentiation in C[subscript p]-Spaces	p. 159
4.3 Higher-Order D-Differentiation on M[superscript IXJ]	p. 162
4.4 Rules of C[subscript p]-Differentiation	p. 165
4.5 D-Analyticity	p. 170
4.6 D-Analyticity on M[superscript IxJ]	p. 174
5 Taylor Series Expansions	p. 179
5.1 Finite Horizon Experiments	p. 180
5.1.1 The General Result	p. 180
5.1.2 Analyticity of Waiting Times	p. 183
5.1.3 Variability Expansions	p. 186
5.2 Random Horizon Experiments	p. 201
5.2.1 The 'Halted' Max-Plus System	p. 202
5.2.2 The Time Until Two Successive Breakdowns	p. 222
5.3 The Lyapunov Exponent	p. 229
5.3.1 Analytic Expansion of the Lyapunov Exponent	p. 230
5.3.2 The Bernoulli Scheme	p. 236
5.3.3 A Note on the Elements of the Taylor Series for the Bernoulli System	p. 240
5.4 Stationary Waiting Times	p. 243
5.4.1 Cycles of Waiting Times	p. 245
5.4.2 Light Traffic Approximation	p. 255
Appendix	p. 264
A Basic Algebra	p. 265
B A Network with Breakdowns	p. 267
C Bounds on the Moments of the Binomial Distribution	p. 271
D The Shifted Negative Binomial Distribution	p. 273
E Probability Theory	p. 275
E.1 Measures	p. 275
E.2 Polish Spaces	p. 277
E.3 The Shift-Operator	p. 278
E.4 Types of convergence	p. 279
E.4.1 Almost Sure Convergence	p. 279
E.4.2 Convergence in Probability	p. 279
E.4.3 Convergence in Distribution (Weak Convergence)	p. 280
E.4.4 Convergence in Total Variation	p. 280
E.4.5 Weak Convergence and Transformations	p. 280
E.5 Weak Convergence and Norm Convergence	p. 281
E.6 Coupling	p. 285
E.6.1 Coupling Convergence	p. 285
E.6.2 Strong Coupling Convergence and Goldstein's Maximal Coupling	p. 285
E.6.3 [Delta]-Coupling	p. 286
E.7 The Dominated Convergence Theorem	p. 286
E.8 Wald's Equality	p. 287
E.9 Regenerative Processes	p. 287
F Markov Chains	p. 289
G Tools from analysis	p. 291
G.1 Cesaro limits	p. 291
G.2 Lipschitz and Uniform Continuity	p. 291
G.3 Interchanging Limit and Differentiation	p. 292
G.4 Taylor Series Expansions	p. 293
G.5 Combinatorial Aspects of Derivatives	p. 296
H Appendix to Section 5.1.3.2	p. 299
Bibliography	p. 301
List of Symbols	p. 309
List of Assumptions	p. 313
Index	p. 315

Available:*

On Order

Summary

Summary

Table of Contents