A Monad for Randomized Algorithms

AbstractIn this paper, we introduce a monad of random choice for domains that does not suffer from the main two drawbacks of the probabilistic powerdomain. It is not known whether any Cartesian closed category of domains is closed under the probabilistic powerdomain, but the Cartesian closed category BCD is closed under this monad of random choice. Also, there is no distributive law between the probabilistic powerdomain and any of the nondeterministic powerdomains, but there is a distributive law between the monad of random choice and the lower powerdomain. In order to work with the convex powerdomain, an alteration to the monad of random choice is made, so that the Cartesian closed categories RB and FS are closed under this construction. Then, in these categories, there is a distributive law between this monad and the convex powerdomain. This work is based on the uniform continuous random variables of Goubault-Larrecq and Varacca, which do not form a monad. This paper gives motivation for this model and changes the definition of the Kleisli extension of Goubault-Larrecq and Varacca so that it is monotone, which was the problem with their definition