We analyze the asymptotic behavior of random variables $x(n,x\_0)$ defined by $x(0,x\_0)=x\_0$ and $x(n+1,x\_0)=A(n)x(n,x\_0)$, where $\sAn$ is a stationary and ergodic sequence of random matrices with entries in the semi-ring \mbox{ $\R\cup\{ -\infty\}$} whose addition is the $\max$ and whose multiplication is $+$. Such sequences modelize a large class of discrete event systems, among which timed event graphs, 1-bounded Petri nets, some queuing networks, train or computer networks. We give necessary conditions for $(\frac{ 1}{ n}x(n,x\_0))\_{ n\in\N}$ to converge almost surely. Then, we prove a general scheme to give partial converse theorems. When $\max\_{ A\_{ ij}(0)\neq -\infty}|A\_{ ij}(0)|$ is integrable, it allows us: - to give a necessary and sufficient condition for the convergence of $(\frac{ 1}{ n}x(n,0))\_{ n\in\N}$ when the sequence $(A(n))\_{ n\in\N}$ is i.i.d., - to prove that, if $(A(n) )\_{ n\in\N}$ satisfy a condition of reinforced ergodicity and a condition of fixed structure (i.e. $\P(A\_{ ij}(0)=-\infty)\in\{ 0,1\}$), then $(\frac{ 1}{ n}x(n,0))\_{ n\in\N}$ converges almost-surely, - and to reprove the convergence of $(\frac{ 1}{ n}x(n,0))\_{ n\in\N}$ if the diagonal entries are never $-\infty$.

Categories: math.PR

Law of Large Numbers for products of random matrices with coefficients in the max-plus semi-ring