The Compositional Construction of Markov Processes

We describe a symmetric monoidal category whose arrows are automata in which the actions have probabilities. The endomorphisms of the identity for the tensor are classical finite Markov processes. The operations of the category permit the compositional description Markov processes. We illustrate by...

Full description

Saved in:
Bibliographic Details
Published in:Applied categorical structures 2011-02, Vol.19 (1), p.425-437
Main Authors: de Francesco Albasini, Luisa, Sabadini, Nicoletta, Walters, Robert F. C.
Format: Article
Language:English
Subjects:
Convex and Discrete Geometry
Geometry
Mathematical Logic and Foundations
Mathematics
Mathematics and Statistics
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe a symmetric monoidal category whose arrows are automata in which the actions have probabilities. The endomorphisms of the identity for the tensor are classical finite Markov processes. The operations of the category permit the compositional description Markov processes. We illustrate by describing a Markov process with 12 n states, which represents a model of the classical Dining Philosopher problem with n dining philosophers, showing how to calculate the probability of reaching deadlock in k steps. A straightforward application of the Perron-Frobenius Theorem yields that this probability tends to 1 as k tends to infinity.
ISSN:0927-2852
1572-9095
DOI:10.1007/s10485-010-9233-0