Les bornes stochastiques "st" selon un patron, PRISM

Nous avons déjà dit que l'algorithme de Vincent utilise des égalités dans les conditions de la comparaison et de la monotonie "st". En permettant d'utiliser les valeurs plus grandes dans le cas de borne supérieure que celles imposées par ces contraintes, on peut créer et/ou supprimer les transitions dans la matrice bornante imposant ainsi la structure de la borne. L'idée est de trouver une structure de matrice permettant une résolution numérique facile et de faire une preuve générale de borne indépendante du patron. Plus grand au sens "st" signifie déplacer la distribution de probabilité vers des états plus grands; ce qui signifie simplement sur la matrice de transition déplacer une probabilités vers les états à droite.

Nous avons proposé un formalisme de patron matriciel décrivant des conditions supplémentaires, liées à la structure de la borne, pour chaque élément de la matrice. Ce patron matriciel est une matrice dont les éléments appartiennent à un alphabet où chaque lettre correspond à un type de condition différent.

Le patron booléen, par exemple, est un patron avec les éléments $0$ ou $1$ avec la sémantique suivante : si l'élément en la position $(i,j)$ dans le patron a la valeur $1$, dans la matrice bornante à cette position on doit avoir une valeur strictement positive (c'est à dire une transition). Si par contre l'élément correspondant dans le patron vaut $0$, dans la matrice bornante on doit avoir la valeur $0$ (pas de transition). Ce type de patron impose la structure exacte du graphe de transitions de la borne ce qui pour la plupart des applications peut être une condition trop forte. Pour cette raison on a introduit une nouvelle lettre dans l'alphabet, signifiant l'absence de conditions supplémentaires liées à la structure. Il est possible d'avoir les conditions structurelles dépendant de la matrice initiale. Par exemple, la condition suivante : ``si à la position $(i,j)$ dans la matrice initiale il y a un élément non-nul, alors dans la matrice bornante l'élément $(i,j)$ doit être non-nul" permet de garder une transition.

Nous avons proposé un algorithme qui pour une matrice de transition initiale calcule une borne "st" ayant la structure décrite par le patron, ou indique que cela n'est pas possible. Nous avons également montré que cet algorithme renvoie une telle borne pour chaque patron qui est compatible avec la matrice initiale (un patron est dit compatible avec une matrice s'il existe au moins une borne st ayant la structure définie par le patron).

Ce travail représente une généralisation de l'approche algorithmique dans la méthode des bornes stochastiques. Le même algorithme peut être utilisé pour différentes structures de bornes. En effet, pour définir une nouvelle structure de borne il est seulement nécessaire de définir le patron associé. Nous avons proposé des patrons pour certaines structures connues :

• Upper-Hessenberg : c'est à dire un matrice triangulaire supérieure augmentée de la sous diagonale. On peut résoudre par un algorithme d'élimination simple et linéaire.
• Complément stochastique avec bloc $D$ triangulaire supérieure : c'est à dire une matrice décomposable en 4 blocs dont le bloc inférieur droit est triangulaire supérieur et en prenant un bloc supérieur gauche de petite taille. On peut résoudre plus facilement par l'approche de Quessette.
• Single Input Markov Chain : matrice décomposable en blocs tels que pour rentrer dans les états d'un bloc, il est nécessaire de passer par un état d'entrée. L'algorithme de Feinberg et Chiu permet une résolution hiérarchique rapide.

Il est également possible d'imposer grâce à un patron certaines propriétés de la chaîne bornante (par exemple l'irréductibilité).