Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 12 open journal systems 


Cycle time of stochastic max-plus linear systems.

Glenn Merlet, LIAFA CNRS-Paris 7


Abstract
We analyze the asymptotic behavior of sequences of random variables defined by an initial condition, a stationary and ergodic sequence of random matrices, and an induction formula involving multiplication is the so-called max-plus algebra. This type of recursive sequences are frequently used in applied probability as they model many systems as some queueing networks, train and computer networks, and production systems. We give a necessary condition for the recursive sequences to satisfy a strong law of large numbers, which proves to be sufficient when the matrices are i.i.d. Moreover, we construct a new example, in which the sequence of matrices is strongly mixing, that condition is satisfied, but the recursive sequence do not converges almost surely.


Full text: PDF

Pages: 322-340

Published on: March 10, 2008
Bibliography
  1. Baccelli, François. Ergodic theory of stochastic Petri networks. Ann. Probab. 20 (1992), no. 1, 375--396. MR1143426 (93a:68110)
  2. Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity.An algebra for discrete event systems.Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Ltd., Chichester, 1992. xx+489 pp. ISBN: 0-471-93609-X MR1204266 (94b:93001)
  3. F. Baccelli and D. Hong. Tcp is max-plus linear and what it tells us on its throughput. In SIGCOMM 00:Proceedings of the conference on Applications, Technologies, Architectures and Protocols for Computer Communication, pages 219--230. ACM Press, 2000.
  4. Baccelli, François; Liu, Zhen. On a class of stochastic recursive sequences arising in queueing theory. Ann. Probab. 20 (1992), no. 1, 350--374. MR1143425 (93c:60137)
  5. Bousch, Thierry; Mairesse, Jean. Finite-range topical functions and uniformly topical functions. Dyn. Syst. 21 (2006), no. 1, 73--114. MR2200765 (2006k:26020)
  6. H. Braker. Algorithms and Applications in Timed Discrete Event Systems. PhD thesis, Delft University of Technology, Dec 1993.
  7. Cohen, Guy; Dubois, Didier; Quadrat, Jean-Pierre; Viot, Michel. A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Trans. Automat. Control 30 (1985), no. 3, 210--220. MR0778424 (86c:93002)
  8. Cohen, Joel E. Subadditivity, generalized products of random matrices and operations research. SIAM Rev. 30 (1988), no. 1, 69--86. MR0931278 (89g:60300)
  9. de Kort, A. F.; Heidergott, B.; Ayhan, H. A probabilistic $(max,+)$ approach for determining railway infrastructure capacity. European J. Oper. Res. 148 (2003), no. 3, 644--661. MR1976565
  10. Gaubert, Stéphane; Mairesse, Jean. Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Automat. Control 44 (1999), no. 4, 683--697. MR1684424 (99m:68139)
  11. Griffiths, Robert B. Frenkel-Kontorova models of commensurate-incommensurate phase transitions. Fundamental problems in statistical mechanics VII (Altenberg, 1989), 69--110, North-Holland, Amsterdam, 1990. MR1103829 (92c:82042)
  12. Heidergott, Bernd. A characterisation of $(max,+)$-linear queueing systems. Queueing Systems Theory Appl. 35 (2000), no. 1-4, 237--262. MR1782609 (2001h:90014)
  13. Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work.Modeling and analysis of synchronized systems: a course on max-plus algebra and its applications.Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2006. xii+213 pp. ISBN: 978-0-691-11763-8; 0-691-11763-2 MR2188299 (2006g:93079)
  14. D. Hong. Lyapunov exponents: When the top joins the bottom. Technical Report RR-4198, INRIA, http://www.inria.fr/rrrt/rr-4198.html, 2001.
  15. Mairesse, Jean. Products of irreducible random matrices in the $(max,+)$ algebra. Adv. in Appl. Probab. 29 (1997), no. 2, 444--477. MR1450939 (98k:60165)
  16. G. Merlet. Produits de matrices al'eatoires : exposants de Lyapunov pour des matrices al'eatoires suivant une mesure de Gibbs, th'eor`emes limites pour des produits au sens max-plus. PhD thesis, Universit'e de Rennes, 2005. http://tel.archives-ouvertes.fr/tel-00010813.
  17. G. Merlet. Law of large numbers for products of random matrices in the (max,+) algebra. Technical report, Keio University, http://hal.archives-ouvertes.fr/ccsd-00085752, 2006.
  18. J.-M. Vincent. Some ergodic results on stochastic iterative discrete events systems. Discrete Event Dynamic Systems, 7(2):209--232, 1997.













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489