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

Glenn Merlet

Published 2006-07-18Version 1

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$.