Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T02:28:22.031Z Has data issue: false hasContentIssue false
  • English
  • Français

Products of Irreducible Random Matrices in the (Max, +) Algebra

Part of: Markov processes

Published online by Cambridge University Press:  01 July 2016

Jean Mairesse
Jean Mairesse*
Affiliation:
INRIA
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the recursive equation x(n + 1)= A(n)⊗x(n), where x(n + 1) and x(n) are ℝk-valued vectors and A(n) is an irreducible random matrix of size k × k. The matrix-vector multiplication in the (max, +) algebra is defined by (A(n)⊗x(n))= maxj (Aij (n) + xj(n)). This type of equation can be used to represent the evolution of stochastic event graphs which include cyclic Jackson networks, some manufacturing models and models with general blocking (such as Kanban). Let us assume that the sequence {A(n), n ∈ ℕ} is i.i.d. or, more generally, stationary and ergodic. The main result of the paper states that the system couples in finite time with a unique stationary regime if and only if there exists a set of matrices such that and the matrices have a unique periodic regime.

Keywords

RANDOM MATRICESCYCLIC JACKSON NETWORK

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 29 , Issue 2 , June 1997 , pp. 444 - 477
Copyright
Copyright © Applied Probability Trust 1997 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Supported by the European Grant BRA-QMIPS of CEC DG XIII.

The research of the author is supported by the Direction des Recherches Etudes et Techniques (DRET) under contract no 91 815.

References

[1] Anantharam, V. and Konstantopoulos, T. (1994) Stationary solutions of stochastic recursions describing discrete event systems. In Proc. 33rd Conf on Decision and Control. Vol. 2. Lake Buena Vista, FL. pp. 1481–1486.Google Scholar
[2] Asmussen, S. (1992) On coupling and weak convergence to stationarity. Ann. Appl. Prob. 2, 739–751.CrossRefGoogle Scholar
[3] Baccelli, F. (1992) Ergodic theory of stochastic Petri networks. Ann. Prob. 20, 375–396.CrossRefGoogle Scholar
[4] Baccelli, F., Cohen, G., Olsder, G. J. and Quadrat, J. P. (1992) Synchronization and Linearity. Wiley, New York.Google Scholar
[5] Baccelli, F. and Liu, Z. (1992) On a class of stochastic recursive equations arising in queueing theory. Ann. Prob. 21, 350–374.Google Scholar
[6] Bambos, N. (1992) On closed ring queueing networks. J. Appl. Prob. 29, 979–995.CrossRefGoogle Scholar
[7] Borovkov, A. (1984) Asymptotic Methods in Queueing Theory. Wiley, New York.Google Scholar
[8] Borovkov, A. (1986) Limit theorems for queueing networks. I. Theory Prob. Appl. 31, 413–427.CrossRefGoogle Scholar
[9] Borovkov, A. (1988) Limit theorems for queueing networks. II. Theory Prob. Appl. 32, 257–272.CrossRefGoogle Scholar
[10] Borovkov, A. and Foss, S. (1992) Stochastically recursive sequences and their generalizations. Siberian Adv. Math. 2, 16–81.Google Scholar
[11] Borovkov, A. and Foss, S. (1994) Two ergodicity criteria for stochastically recursive sequences. Acta Applic. Math. 34, 125–134.CrossRefGoogle Scholar
[12] Bougerol, P. and Lacroix, J. (1985) Products of Random Matrices with Applications to Schrödinger Operators. Birkhäuser, Basel.CrossRefGoogle Scholar
[13] Brandt, A., Franken, P. and Lisek, B. (1990) Stationary Stochastic Models. Wiley, New York.Google Scholar
[14] Brilman, M. and Vincent, J. M. (1995) Synchronisation by resources sharing: a performance analysis. Technical report. MAI-IMAG, Grenoble.Google Scholar
[15] Cohen, G., Dubois, D., Quadrat, J. P. and Viot, M. (1983) Analyse du comportement périodique des systèmes de production par la théorie des dioïdes. Technical report 191. INRIA.Google Scholar
[16] Cohen, G., Dubois, D., Quadrat, J. P. and Viot, M. (1985) A linear system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Trans. Automatic Control AC–30, 210–220.CrossRefGoogle Scholar
[17] Cohen, J. E. (1988) Subadditivity, generalized product of random matrices and operations research. SIAM Rev. 30, 69–86.CrossRefGoogle Scholar
[18] Cuninghame-Green, R. (1962) Describing industrial processes with interference and approximating their steady-state behaviour. Operat. Res. Quart. 13, 95–100.CrossRefGoogle Scholar
[19] Cuninghame-Green, R. (1979) Minimax Algebra (Lecture Notes in Economics and Mathematical Systems 166). Springer, Berlin.Google Scholar
[20] Furstenberg, H. and Kesten, H. (1960) Products of random matrices. Ann. Math. Statist. 31, 457–469.CrossRefGoogle Scholar
[21] Gaubert, S. (1994) On semigroups of matrices in the (max, +) algebra. Technical report 2172. INRIA.Google Scholar
[22] Gaubert, S. and Mairesse, J. (1997) Task resource models and (max, +) automata. In Idempotency. ed. Gunawardena, J. Cambridge University Press, Cambridge.Google Scholar
[23] Glasserman, P. and Yao, D. (1994) Monotone Structure in Discrete-Event Systems. Wiley, New York.Google Scholar
[24] Gondran, M. and Minoux, M. (1977) Valeurs propres et vecteurs propres dans les dioïdes et leur interprétation en théorie des graphes. EDF Math. Inf. 2, 25–41.Google Scholar
[25] Gordon, W. and Newell, G. (1967) Closed queuing systems with exponential servers. Operat. Res. 15, 254–265.CrossRefGoogle Scholar
[26] Griffiths, R. (1990) Frenkel-Kontorova models of commensurate-incommensurate phase transitions. In Fundamental Problems in Statistical Mechanics VII. ed. van Beijeren, H. Elsevier, Amsterdam.Google Scholar
[27] Kaspi, H. and Mandelbaum, A. (1992) Regenerative closed queueing networks. Stoch. Stoch. Rep. 39, 239–258.CrossRefGoogle Scholar
[28] Kaspi, H. and Mandelbaum, A. (1994) On Harris recurrence in continuous time. Math. Operat. Res. 19, 211–222.CrossRefGoogle Scholar
[29] Loynes, R. (1962) The stability of a queue with non-independent interarrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.CrossRefGoogle Scholar
[30] Mairesse, J. (1995) Stability of stochastic discrete event systems. Algebraic approach. PhD thesis. Ecole Polytechnique, Paris.Google Scholar
[31] Meyn, S. and Tweedie, R. (1993) Markov Chains and Stochastic Stability. Springer, Berlin.CrossRefGoogle Scholar
[32] Olsder, G. J., Resing, J., De Vries, R., Keane, M. and Hooghiemstra, G. (1990) Discrete event systems with stochastic processing times. IEEE Trans. Automatic Control 35, 299–302.CrossRefGoogle Scholar
[33] Resing, J., De Vries, R., Hooghiemstra, G., Keane, M. and Olsder, G. J. (1990) Asymptotic behavior of random discrete event systems. Stoch. Proc. Appl. 36, 195–216.CrossRefGoogle Scholar
[34] Romanovskii, I. V. (1967) Optimization and stationary control of discrete deterministic process in dynamic programming. Cybernetics 3, 66–78.Google Scholar
[35] Yakovenko, S. and Kontorer, L. (1992) Nonlinear semigroups and infinite horizon optimization. In Idempotent Analysis. ed. Maslov, V. and Samborskñ, S. AMS, New York.Google Scholar