New bounds for Lyapounov exponents of stochastic (max,+) matrices

Alain Jean-Marie
INRIA Sophia Antipolis
Projet Mistral
Alain.Jean-Marie@sophia.inria.fr

ALAPEDES meeting
March 30, 1999

We consider the stochastic (max,+) recurrence $X(n)=A(n) \otimes X(n-1)$ in the case where the sequence $\{A(n)\}$ is i.i.d. and multinomial. Based on a decomposition of products of matrices in blocks of a certain form, we propose upper and lower bounds for $\mbox{E} X(n)$ and the Lyapunov exponent of the system. The basic computational complexity of the computation is ${\cal O} (N^3)$ (N is the size of the matrix) but the accuracy can be improved at will at the expense of larger computation times.