Abstract
In this paper, we consider stochastic linear systems under the max-plus algebra. For such a system, the states are governed by the recursive equation X n = A n ⊗ X n-1 ⊗ U n with the initial condition X 0 = x 0 . By transforming the linear system under the max-plus algebra into a sublinear system under the usual algebra, we establish various exponential upper bounds for the tail distributions of the states X n under the independently identically distributed (i.i.d.) assumption on {(A n , U n ), n ≥ 1} and a couple of regularity conditions on (A 1 , U 1 ) and the initial condition x 0 . These upper bounds are related to the spectral radius (or the Perron-Frobenius eigenvalue) of the nonnegative matrix in which each element is the moment generating function of the corresponding element in the state-feedback matrix A 1 . In particular, we have Kingman's upper bound for GI/GI/1 queue when the system is one-dimensional. We also show that some of these upper bounds can be achieved if A 1 is lower triangular. These bounds are applied to some commonly used systems to derive new results or strengthen known results. © 1996 IEEE.