Approche Dynamique Max,+

Une autre approche qui a fait l'objet de travaux préliminaires au PRiSM utilise les propriétés du dyoide $(Max,+)$. L'idée est ici de concevoir une nouvelle définition constructive de la distribution de probabilités stationnaires d'une chaine de Markov en temps discret en utilisant les opérateurs $Max$ et $+$ puis d'en dériver des encadrements.

La construction que nous avons établie définit la distribution stationnaire $\pi$ comme limite supérieure d'un schéma iteratif croissant sur des vecteurs à composantes positives. On n'utilise donc pas ici de probabilités mais des matrices positives et des vecteurs positifs. Ce schéma utilise les opérateurs $Max$, $+$ et la multiplication par des scalaires positifs. De même un schéma itératif décroissant utilisant les opérateurs $Min$ et $+$ a été démontré. Le schémà croissant repose sur les idées suivantes:

• Supposons que nous ayons construit un vecteur positif $X$ dont toutes les composantes sont inférieures à celle de $\pi$. Alors, puisque $P$ est une matrice positive, $X P$ est un vecteur inférieur à $\pi P$, c'est à dire $\pi$. Donc $Z=max (X,X P)$ est, composante par composante, entre $X$ et $\pi$.
• l'inégalité triviale suivante donne le point initial pour la séquence:

  
  

  $$Min_i P(i,j) \leq \pi(j) = \sum_i \pi (i) P(i,j) \leq Max_i P(i,j)$$
  
  
  Posons alors $\nabla_j = Min_i P(i,j)$. La seconde partie de l'inégalité permet l'initialisation de la séquence décroissante des bornes supérieures.

• Le schéma initial a de multiples limites. On le modifie donc pour que le seul point limite soit la distribution stationnaire $\pi$.

Nous n'avons, pour le moment, de preuve de l'algorithme que lorsque $\nabla$ est non nul, mais des expériences numériques montrent que, même dans le cas contraire, on peut faire converger la séquence par un choix judicieux du vecteur initial. Un point important est que, dans cette nouvelle approche, on obtient à chaque étape une borne pour toutes les composantes de la distribution. La qualité du résultat va donc s'accroitre avec le temps de calcul.

Le projet se propose de prouver d'autres bornes associées à des simplification de calcul. Par exemple, dans le calcul de la borne, il est possible de remplacer certains éléments de $P$ (positifs par définition) par des valeurs nulles, tout en conservant le vecteur $\nabla$. Clairement, le calcul de la borne est plus simple car il y a maintenant moins d'éléments non nuls et forunit une borne (car on a élmininé des termes positifs de la somme). De même on peut annuler des colonnes entières de $P$ pour pouvoir traiter le cas de matrices infinies. La preuve de la borne repose sur des propriétés des opérateurs $Max$ et $+$ et de la multiplication par des variables positives.

Au cours du projet, ces algorithmes seront implantés dans PEPS. Certains fonctionnent déjà sur la représentation tensorielle puisqu'ils emploient le produit vecteur-matrice, qui a été longuement étudié dans l'approche tensorielle. Par contre, la simplification d'un réseau d'automate pour minimiser le calcul est encore un problème ouvert.