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

Abstract

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{$\mathbb{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 \mathbb{N}$ to converge almost surely. Then, we prove a general scheme to give partial converse theorems. When $\max \_A\_ij(0)\ne -\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 \mathbb{N}$ when the sequence $(A(n))\_n\in \mathbb{N}$ is i.i.d., - to prove that, if $(A(n))\_n\in \mathbb{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 \mathbb{N}$ converges almost-surely, - and to reprove the convergence of $(\frac{1}{n}x(n,0))\_n\in \mathbb{N}$ if the diagonal entries are never $-\infty$.