A Cartesian closed category for random variables

Abstract

We present a novel, yet rather simple construction within the traditional framework of Scott domains to provide semantics to probabilistic programming, thus obtaining a solution to a long-standing open problem in this area. We work with the Scott domain of random variables from a standard and fixed probability space—theunit interval or the Cantor space—to any given Scott domain. The map taking any such random variable to its corresponding probability distribution provides a Scott continuous surjection onto the probabilistic power domain of the underlying Scott domain, which preserving canonical basis elements, establishing a new basic result in classical domain theory. If the underlying Scott domain is effectively given, then this map is also computable. We obtain a Cartesian closed category by enriching the category of Scott domains by a partial equivalence relation to capture the equivalence of random variables on these domains. The constructor of the do- main of random variables on this category, with the two standard probability spaces, leads to four basic strong commutative monads, suitable for defining the semantics of probabilistic programming.