Categories of Timed Stochastic Relations

AbstractStochastic behavior—the probabilistic evolution of a system in time—is essential to modeling the complexity of real-world systems. It enables realistic performance modeling, quality-of-service guarantees, and especially simulations for biological systems. Languages like the stochastic pi calculus have emerged as effective tools to describe and reason about systems exhibiting stochastic behavior. These languages essentially denote continuous-time stochastic processes, obtained through an operational semantics in a probabilistic transition system. In this paper we seek a more descriptive foundation for the semantics of stochastic behavior using categories and monads. We model a first-order imperative language with stochastic delay by identifying probabilistic choice and delay as separate effects, modeling each with a monad, and combining the monads to build a model for the stochastic language