Une introduction aux réseaux de Markov

Ce travail se présente comme une généralisation des chaînes de Markov en temps discret. La construction d'une chaîne de Markov à espaces d'états consiste en une probabilisation des suites infinies sur , éléments de l'espace $\Omega=X^\mathbb{N}$ muni de sa tribu borélienne. Une autre représentation de l'espace $\Omega$ considère ses éléments comme des chemins maximaux d'un arbre régulier . Changeons le mot chemin en configuration. L'arbre est un ordre partiel dont les configurations sont des sous-ordres partiels, qui ont la propriété d'être des ordres totaux.

Le modèle des structures d'événements, introduit par Winskel [6], apparaît alors comme une généralisation naturelle du modèle de l'arbre. Une structure d'événements est en effet un ordre partiel, dont les éléments sont vus comme des événements, et pour lequel les configurations sont à présent des sous-ordres partiels, non nécéssairement totaux. Une structure probabiliste est définie sur une structure d'événements par la donnée d'une mesure de probabilité sur l'espace des configurations maximales, muni de sa tribu borélienne relative à la topologie de Scott. Si la structure d'événements en question est en fait un arbre, dont les configurations sont bien des chemins, alors nous retrouvons le modèle précédent.

D'autre part, le modèle de l'arbre est dérivé de la structure initiale de la chaîne de Markov, par une opération de dépliage d'un graphe a priori quelconque vers un arbre. Un analogue de cette opération de dépliage est obtenu avec le modèle des réseaux de Petri, bien connu de la communauté d'informatique théorique, dont le dépliage est en effet une structure d'événements. Les réseaux de Petri probabilistes que j'ai étudiés peuvent donc être vus comme une généralisation des chaînes de Markov en temps discret; ce sont des chaînes de Markov « à plusieurs jetons», dont les jetons peuvent bouger simultanément -- d'où la notion de parallélisme --, de manière probabiliste et avec une mémoire limitée à l'état présent du système -- pour garder un caractère markovien.

Les étapes suivantes correspondent aux jalons de ce travail (les références renvoient aux articles que j'ai publiés sur le sujet):

Donner un théorème de prolongement de mesures, fondé sur le théorème d'extensions des systèmes projectifs de mesures de Prokhorov, et s'appliquant aux structures d'événements [2,5].
Construire des familles de probabilités consistentes, dont le prolongement est garanti par le théorème précédent; le lien entre probabilités et parallélisme est ici crucial [3].
Adapter les outils classiques de la théorie des chaînes de Markov (filtrations, temps d'arrêt, propriété de Markov forte) [1].
Étudier le comportement asymptotique, donner un analogue de la mesure stationnaire et une loi des grands nombres [4].

Ce sont ces étapes que j'ai suivies en élaborant en collaboration avec A. Benveniste le modèle des réseaux de Markov et des structures d'événements probabilistes distribuées. Nous avons proposé un modèle markovien à états locaux, possédant des propriétés de parallélisme, et en l'absence d'horloge globale totalement ordonnée. Ce sont ces caractéristiques qui en font l'originalité.

Bibliographie

1: S. Abbes.
The (true) concurrent Markov property and some applications to Markov nets.
In G. Ciardo and P. Darondeau, editors, International Conference on Theory and Applications of Petri nets, ICATPN 05, volume 3536 of LNCS, pages 70-89. Springer, 2005.
2: S. Abbes.
A projective formalism for topological and probabilistic event structures.
Mathematical Structures in Computer Science, 2007.
À paraître.
3: S. Abbes and A. Benveniste.
Probabilistic true-concurrency models: branching cells and distributed probabilities for event structures.
Information and Computation, 204(2):231-274, 2006.
4: S. Abbes and A. Benveniste.
Probabilistic true-concurrency models: Markov nets and a law of large numbers.
Theoretical Computer Science, 2007.
À paraître.
5: S. Abbes and K. Keimel.
Projective topology on bifinite domains and applications.
Theoretical Computer Science, 365(3):171-183, 2006.
6: M. Nielsen, G. Plotkin, and G. Winskel.
Petri nets, event structures and domains, part 1.
Theoretical Computer Science, 13:85-108, 1981.