On the exponentiality of stochastic linear systems under the max-plus algebra

Abstract

Considers stochastic linear systems under the max-plus algebra. For such a system, the states are governed by the recursive equation X/sub n/=A/sub n//spl otimes/X/sub n-1//spl oplus/U/sub n/ with the initial condition condition X/sub 0/=x/sub 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/sub n/ under the independently identically distributed (i.i.d.) assumption on {(A/sub n/,U/sub n/)/sub 1/n/spl ges/1} and a couple of regularity conditions on (A/sub 1/,U/sub 1/) and the initial condition x/sub 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/sub 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/sub 1/ is lower triangular. These bounds are applied to some commonly used systems to derive new results or strengthen known results.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 28 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.