An introduction to Markov nets

This work proposes a generalization of Markov chains in discrete time. Constructing a Markov chain with state space amounts to randomizing infinite sequences with values in , elements of the space $\Omega=X^\mathbb{N}$ equipped with the Borelian $\sigma$ -algebra. An other representation of $\Omega$ looks at its elements as maximal paths of a regular tree . Let us change the word path into configuration. Tree is a partial order, the configurations of which are sub-partial orders, with the property of being total orders.

The model of event structures, introduced by Winskel [6], appears as a natural generalization of the tree model. An event structure is a partial order, the elements of which are called events, and the configurations fo which are now partial orders, not necessarily total. A probabilistic structure is defined upon an event structure by means of a probability measure on the space of maximal configurations, equiped with the Borel $\sigma$ -algebra relative to the induced Scott topology. If the event structure is actually a tree, the configurations of which are then paths, then we are back to the former tree model.

Moreover, the tree model is obtained from the initial structure of the Markov chain through the unfolding of a finite graph into a tree. This unfolding operation also exists within the model of Petri nets, leading to an event structure. The probabilistic Petri nets I have studied can thus be seen as a generalization of discrete time Markov chains; they are Markov chains with ``several tokens'', that can move together -- whence the notion of concurrency --, in a probabilistic fashion and with an amount of memory limited to the current state of the system -- to keep it Markov.

The following steps correspond to the milestones of the work (references concern the papers I have published on the topic):

Give an extension theorem, based on Prokhorov extension theorem of projective systems of probability measures, that applies to event structure [2,5].
Construct consistent families of probability measures, that can be extended thanks to the above theorem; the connection between probability and concurrency is the main point [3].
Adapt classical tools from Markov chains theory (filtartions, stopping times, strong Markov property) [1].
Study asymptotic behaviour, give an equivalent of stationary measure and a Law of large numbers [4].

We have followed these steps together with A. Benveniste, in order to provide the models of Markov nets and of distributed probabilistic event structures. We have designed a Markovian model with local states, without any totally ordered global clock. These are the peculiar features of the model.

Bibliography

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.