Taylor Expansions for Poisson Driven $(\max,+)$-Linear Systems
Résumé
We give a Taylor expansion for the mean value of the canonical stationary state variables ${W_n}={X_n-T_n}$ of open $(\max,+)$-linear stochastic systems with Poisson input process, that is systems with (transient) state variables ${X_n}$ satisfying the vectorial recursion $X_{n+1}=A_nX_n øplus B_{n+1} T_{n+1}$ in this algebra, where ${T_n}$ is a Poisson point process, and ${A_n}$ and ${B_n}$ are sequences of random matrices satisfying certain independence properties. Probabilistic expressions are derived for coefficients of all orders, under certain integrability conditions: the $k$-th coefficient in the Taylor expansion of the $i$-th component $\Etnt of $\Ee is the expectation of a polynomial $p_{k+1}(D_0^i,\ldots,D_k^i)$, known in explicit form, of the random variables $D_0^i,\ldots,D_k^i$, where $D_n^i=(A_{-1}\ldots A_{-n}B_{-n})^i$. The polynomials ${p_k}$ are of independent combinatorial interest: their monomials belong to a subset of those obtained in the multinomial expansion; they are also invariant by cyclic permutation and by translations along the main diagonal. The method for proving these results is based on two ingredients: a) the ($\max,+$)-linear representation of the stationary state variables as functionals of the input point process; b) the Taylor expansion representation of functionals of marked point processes, and in particular of Poisson point processes. Several applications of these results are proposed within the framework of stochastic Petri nets. It is well known that $(\max,+)$-linear systems allow one to represent stochastic Petri nets belonging to the class of event graphs. This class contains various instances of queueing networks like acyclic or cyclic fork-join queueing networks, finite or infinite capacity tandem queueing networks with various types of blocking (manufacturing and communication), synchronized queueing networks etc. It also contains some basic manufacturing models such as Kanban networks, Job-Shop systems etc. The applicability of this expansion method is discussed for several systems of this type.In the M/D case (i.e. all service times are deterministic), the approach is quite practical, as all coefficients of the expansion are obtained in closed form. In the M/GI case, the computation of the coefficient of order $k$ can be seen as that of joint distributions in a stochastic PERT graph of an order which is linear in $k$, a problem for which no polynomial algorithms are apparently known. We nevertheless show that expansions of limited order can be obtained in explicit form along these lines.