Discrete Random Variables Over Domains
Theoretical Computer Sceince, to appearDiscrete Random Variables Over DomainsMichael Mislove 1Department of MathematicsTulane UniversityNew Orleans, LA 70118AbstractIn this paper we initiate the study of discrete random variables over domains. Ourwork is inspired by work of Daniele Varacca, who devised indexed valuations asmodels of probabilistic computation within domain theory. Our approach relieson new results about commutative monoids defined on domains that also allowactions of the non-negative reals. Using our approach, we define two such familiesof real domain monoids, one of which allows us to recapture Varacca’s constructionof the Plotkin indexed valuations over a domain. Each of these families leads tothe construction of a family of discrete random variables over domains, the secondof which forms the object level of a continuous endofunctor on the categories RB(domains that are retracts of bifinite domains), and on FS (domains where theidentity map is the directed supremum of deflations finitely separated from theidentity). The significance of this last result lies in the fact that there is no knowncategory of continuous domains that is closed under the probabilistic power domain,which forms the standard approach to modeling probabilistic choice over domains.The fact that RB and FS are Cartesian closed and also are closed under a powerdomain of discrete random variables means we can now model, e.g., the untypedlambda calculus extended with a probabilistic choice operator, implemented viarandom variables.1IntroductionDomain theory, perhaps the most widely used method for assigning denotational meanings to programming languages, has recently seen its influencebroaden to other areas of computation and mathematics. It provides a broadrange of constructors for modeling data types, nondeterminism, functionalprogramming, and several other constructs needed in semantics. Domain theory also admits a number of Cartesian closed categories, the fundamental1This work supported by the US National Science Foundation and the US Office of NavalResearchPreprint submitted to Elsevier Preprint17 August 2006
Misloveobjects needed to model the lambda calculus. Even probabilistic computationadmits a model in the theory, although truth to tell, this particular constructor has proven to be very difficult to unravel. Of particular interest is thequestionIs there a Cartesian closed category of domainsthat is closed under the probabilistic power domain?There have been many attempts to resolve this, but the most we know to dateis contained in [12], where it is shown that the probabilistic power domain ofa finite tree is in RB, that the probabilistic power domain of a finite reversedtree is in FS, and that RB is closed under the probabilistic power domain ifthe probabilistic power domain of every finite poset is in RB. But, other thanfinite trees, the only finite posets whose probabilistic power domain is knownto be in RB is the class of flat posets, whose probabilistic power domains arebounded complete (the continuous analogs of Scott domains).We do not contribute to settling this question here, but we do provide analternative construction—what we call the power domain of discrete -randomvariables, which we show defines a continuous endofunctor on the category RB,as well as on FS and on CDOM, the category of coherent domains.Objects in RB are retracts of bifinite domains, those that can be expressedas bilimits of finite posets under embedding–projection pairs. This categoryis Cartesian closed, and it also is closed under the various power domains fornondeterminism [7]. With the addition of a mechanism to model probabilisticchoice, RB provides virtually all the tools required to support semantic modeling. Furthermore, playing off results of Varacca [23,24], we show that theformation of the power domain of discrete -random variables over RB yieldsa monad that enjoys a distributive law with respect to each of the powerdomain monads, and this in turn implies that each of these power domainmonads lifts to a monad on the category RB that are also algebras for thediscrete -random variable power domain monad. These laws are enumerated in Definition 4.8. In short, we can now form domain-theoretic modelsof computation that respect the laws of discrete -random variables as wellas any of the laws we choose for nondeterminism: angelic, demonic or convexchoice.The outline of the rest of the paper is as follows. In the next section weprovide some background about domains and about the constructions we need.We then review briefly a construction by Varacca [24] which inspired our work,and that Varacca calls the Plotkin indexed valuations. In the following section,we investigate bag domains—domain-theoretic models for multisets, and wealso explore the structure of bag domains that also admit an action of the nonnegative reals. We single out two such constructs, which are distinguished byhow the least element acts. In the first, is the identity of the monoid, as wellas being the image of 0 under the action of R 0 . We define a functor whichproduces the initial such algebra over a bag domain, and this in turn is what we2
Misloveuse to recapture Varacca’s family of Plotkin indexed valuations. The secondsuch construct is distinguished by the fact that acts as a multiplicative zeroin the monoid, rather than as an identity, and we again define a functor whichproduces the initial such algebra over a bag domain.The constructions of initial bag domain monoids admitting actions of thenon-negative reals then are exploited to define two families of discrete random variables over domains. The first is based on the construction that ledto recapturing Varacca’s results, and because acts like an additive zero, wedenote this family by RV (P ), for a domain P . The second family is based onour second initial algebra over bag domains, and since acts like a multiplicative zero in this case, we denote this family by RV (P ). We also show thatRV defines an continuous endofunctor on the category of domains that leavesboth RB and FS invariant. This yields two Cartesian closed categories of domains that support a model of probabilistic computation. In the final section,we discuss further work along this line, including how to construct Varacca’sother families of indexed valuations. We also discuss the relationship betweena random variable approach to modeling probabilistic computation and onebased directly on probability distributions.1.1 BackgroundWe begin with some basic results about partial orders, and about domains inparticular. A general reference for this material is [1] or [4].A subset A of a partially ordered set P is directed if A has an upper boundfor each of its finite subsets. A mapping between partially ordered sets isScott continuous if it preserves the order and the suprema of those directedsets that have a supremum. A directed complete partial order (dcpo) is apartially ordered set in which each directed set has a least upper bound. Acpo is a dcpo with a least element .If P is a partial order and x, y P , then we say x is way-below y (x y)if whenever A P is directed and has a supremum, if y A, then x a forsome a A. A poset P is continuous if y {x P x y} is directed andy y for each y P . A domain is a continuous dcpo. We let CPOS denotethe category of continuous posets and Scott continuous maps, and DOM thefull subcategory of domains.An abstract basis is a pair (B, ) where is a transitive relation on Bsatisfying the interpolation property:F x & F B finite ( y B) F y x.By F x we mean z x z F . If (B, ) is an abstract basis, thenI B is a round ideal if I is a -directed, -lower set, and x I ( y I) x y. The round-ideal completion of an abstract basis (B, ) isthe family of round ideals, ordered by inclusion. This forms a domain, whereI J iff ( x J) I x. In fact, every domain P is isomorphic to the3
Misloveround-ideal completion of an abstract basis, namely P is isomorphic to theround ideal completion of (P, ) under the mapping sending a point x to x,whose inverse is the mapping that sends a round ideal to its supremum.One of the fundamental results about dcpos is that the family of Scottcontinuous maps between two dcpos is another dcpo in the pointwise order.Since it’s easy to show that the finite product of a family of continuous posetsis another such, and the one-point poset is a terminal object, a central questionis under what conditions is the family of Scott continuous selfmaps [D E]between domains also continuous, i.e., which categories of dcpos and Scottcontinuous maps are Cartesian closed? This is true of DCPO, the categoryof dcpos and Scott continuous maps, but not of DOM. Still, there are severalfull subcategories of DOM that are Cartesian closed. Among the notable suchcategories are the following: 2BCD Bounded complete domains, in which every subset having an upper boundhas a least upper bound; equivalently, every non-empty subset has a greatestlower bound.RB Domains which are retracts of bifinite domains, themselves bilimits of families of finite posets under embedding-projection maps; these are pairs ofScott continuous mappings e : P Q and p : Q P satisfying p e 1Pand e p 1Q .FS Domains D satisfying the property that the identity map is the directedsupremum of Scott-continuous selfmaps f : D D each finitely separatedfrom the identity: i.e., for each f there is a finite subset Mf D with theproperty that, for each x D, there is some m Mf with f (x) m x.Actually, BCD is a full subcategory of RB, which in turn is a full subcategoryof FS, and FS is a maximal ccc of domains. An interesting (some might sayfrustrating) open question is whether RB and FS are equal. The objects in allof these categories are coherent, 3 but the category CDOM of coherent domainsand Scott continuous maps is not a ccc.We also recall some facts about categories. A monad or triple on a category.A is a a 3-tuple hT, µ, ηi where T : A A is an endofunctor, and µ : T 2 T.and η : 1A T are natural transformations satisfying the laws:µ T µ µ µTand µ ηT T µ T η.·Equivalently, if F : A B is left adjoint to G : B A with unit η : 1A GF·and counit ǫ : F G 1B , then hGF, GǫF, ηi forms a monad on A, and everymonad arises in this fashion.If hT, µ, ηi is a monad, then a T -algebra is a pair (a, h), where a A andh : T a a is an A-morphism satisfying h ηa 1a and h T h h µa .For example, domain theory provides three models for nondeterminism, thelower power domain PL ,which assigns to a domain the family of Scott-closed23See [1] for details about these categories.A domain is coherent if its Lawson topology is compact; cf. [1]4
Mislovelower sets with union as the semilattice operation, the upper power domain,PU which assigns to a domain the family of Scott-compact upper sets withunion as the operation, but with reverse inclusion as the order, and the convexpower domain, PC , which assigns to a (coherent) domain the family of sets thatcan be expressed as the intersection of a Scott-closed lower set and a Scottcompact upper set, with the Egli-Milner order, where the “sum” of sets is thesmallest such set containing their union (cf. [1] for details here). Each of thesedefines a monad on DCPO (cf. [7]), whose algebras are ordered semilattices;another example is the probabilistic power domain V whose algebras satisfyequations that characterize the probability measures over P (cf. [10]).One goal of domain theory is to provide a setting in which all of the constructors needed to model a given programming language can be combined. Ifthe aim is to model both nondeterminism and probabilistic choice, then oneneeds to combine the appropriate nondeterminism monad with the probabilistic power domain monad, so that the laws of each constructor are preserved inthe resulting model. This is the function of a distributive law, which is a nat.ural transformation d : ST T S between monads S and T on A satisfyingseveral identities—cf. [2]. The significance of distributive laws is the followingtheorem of Beck:Theorem 1.1 (Beck [2]) Let (T, η T , µT ) and (S, η S , µS ) be monads on thecategory A. Then there is a one-to-one correspondence between.(i) Distributive laws d : ST T S;.(ii) Multiplications µ : T ST S T S, satisfying (T S, η T η S , µ) is a monad;. the natural transformations η T S : S T S and T η S : T T S aremonad morphisms; the following middle unit law holds:T ηS ηT S/ T ST SLLLLLLµLIdT S LLLLL& T S LLTS(iii) Liftings T̃ of the monad T to AS , the category of S-algebras in A.2So, one way to know that the combination of the probabilistic power domain and one of the power domains for nondeterminism provides a modelsatisfying all the needed laws would be to show there is a distributive law ofone of these monads over the probabilistic power domain monad. Unfortunately, it was shown by Plotkin and Varacca [23] that there is no distributivelaw of V over PX , or of PX over V for any of the nondeterminism monads PX .This led to the work we report on next.5
Mislove2Indexed ValuationsWe now recall some of the work of Varacca [24] that was motivated by problems associated with trying to support both nondeterminism and probabilisticchoice within the same model. Once it was shown that there is no distributivelaw between V and any of the nondeterminism monads, Varacca consideredthe simpler situation of sets, where the model of nondeterminism is the powerset monad, and, in the finite case, the probabilistic monad is the family ofsimple measures on the set. A theorem of Gautam shows why the distributivelaw doesn’t hold in this setting:Theorem 2.1 (Gautam [3]) A necessary and sufficient condition for anequational theory to extend from a model X to its power set is that everylaw of the theory mentions each variable at most once on each side of theequation.2Since finite posets are domains, this implies that, even if X is a probabilisticalgebra, the operations on X cannot be extended to P(X) to satisfy thesame laws. In fact, both the nondeterminism monad over a set X and theprobabilistic monad over X violate the conditions of the theorem. For thenondeterminism monad, it is the law x x x, while for the probabilisticmonad, it is the law pA (1 p)A A. 4 Then Varacca realized that weakeningone of the laws of probabilistic choice could result in a monad that enjoys adistributive law with respect to a monad for nondeterminism. For 0 p 1and A a domain element,Varacca weakened the law pA (1 p)A A inthree ways:pA (1 p)A A,pA (1 p)A A,pA (1 p)A and A not necessarily related by order.(1)(2)(3)He called the monad he constructed satisfying (1) the Hoare indexed valuations, the one satisfying (2) the Smyth indexed valuations and the one satisfying (3), the Plotkin indexed valuations. We exploit this last construction—theso-called Plotkin indexed valuations over a domain—in the construction of apower domain of discrete random variables.2.1 Plotkin Indexed ValuationsDefinition 2.2 An indexed valuation over the poset P is a tuple (ri , pi )i Iwhere I is an index set, 5 each ri 0 is a non-negative real number andpi P for each i I.4The operator pA (1 p)A models probabilistic choice where the left branch is chosenwith probability 0 p 1 and the right branch is chosen with probability 1 p.5For our discussion, we can assume I is always finite.6
MisloveTwo indexed valuations satisfy (ri , pi )I 1 (sj , qj )J if I J and thereis a permutation φ S( I ) 6 with rφ(i) si and pφ(i) qi for each i.If I ′ {i I ri 6 0} and similarly for J, then (ri , pi )I (sj , qj )J if(ri , pi)I ′ 1 (sj , qj )J ′ . Then, is an equivalence relation on indexed valuations, and we let hri, pi iI denote the equivalence class of the indexed valuation(ri , pi)I modulo .Next, let R 0 denote the extended non-negative real numbers, with theusual order. Then given a domain P , Varacca defines a relation IVP on thefamily {hri, pi iI ri R 0 & pi P } of indexed valuations over P byhri , piiI IVP hsj , qj iJ iff ( I J ) & ( φ S( I ))ri sφ(i) & pi P qφ(i) ( i I).6(4)This forms an abstract basis whose round ideal completion is the family ofPlotkin indexed valuations over P . We denote this domain by IVP (P ).We also can “add” indexed valuations hri , pi iI and hsj , qj iJ byhri , xi ii I hsj , yj ij J htk , zk ik K·where K I J and((ri , xi ) if k i I(tk , zk ) (sj , yj ) if k j J.This operation of concatenating tuples and taking the equivalence class of the·resulting I J-tuple forms a continuous operation on indexed valuations thatis commutative, by construction. We let R 0 act on hri , piiI by r · hri , pi iI hr · ri , piiI . Varacca’s main result for the family of Plotkin indexed valuationscan be summarized as follows:Theorem 2.3 (Varacca [23])(i) If P is a continuous poset, then the family of Plotkin indexed valuationsordered by IVP as defined in (4) is an abstract basis.(ii) The round ideal completion of the Plotkin indexed valuations, IVP (P ),admits an addition and a scalar multiplication by elements of R 0 thatsatisfy the following laws:67(1) A B B A(2)A (B C) (A B) C(3) A 0 A(4)0A 0(5) 1A A(6)p(A B) pA pB(7) p(qA) (pq)Awhere p, q R 0 and A, B, C IVP (P ).S(n) denotes the permutation group on an n-element set.Note that r s iff r 0 or r s for r, s R 0 .7
Mislove(iii) IVP defines the object level of an endofunctor which is monadic overDOM, and that satisfies a distributive law with respect to each of the2power domain monads.A coherent domain is one whose Lawson topology is compact; it is a standard result of domain theory is that the Plotkin power domain applied toa coherent domain yields another such (cf. [1] for details). A corollary ofTheorem 2.3 is that the composition PP IVP defines a monad on CDOM,the category of coherent domains, whose algebras satisfy the laws listed inTheorem 2.3(i) and the laws of the Plotkin power domain:(i) X Y Y X(ii) X X X(iii) X (Y Z) (X Y ) ZIn other words, PP (IVP (P )) is the initial domain semilattice algebra over Pthat also satisfies the laws listed in Theorem 2.3(ii).3Bag domainsIn this section we develop some results that are fundamental for our mainconstruction. More details about these results are contained in [17]. The earliest comments in the literature about bag domains—domains whose elementsare bags or multisets from an underlying domain, are in [20] where Exercise103 discusses them; Poigné [21] also comments on the existence of free bagdomains. But the first paper devoted to bag domains is apparently [6], wherea topological approach to their construction is investigated. There is the workof Vickers [25] and of Johnstone [8,9], but these works were inspired by problems in database theory, and the focus is on abstract categorical construction,not on domains as we consider them. To be sure, we also are interested incategorical aspects, but our aim is more in the spirit of [6], which includesanalyzing the internal structure of these objects. Our results also allow us tocapture the constructions of Varacca [23] more concretely. We begin with asimple result about posets:Definition 3.1 Let P be a poset and let n N. For φ S(n), define amappingφ : P n P n by φ(d)i dφ 1 (i) .(5)Then φ permutes the components of d according to φ’s permutation of theindices i 1, . . . , n. Next, define a preorder n on P n byd n e iff( φ S(n)) φ(d) e iff( φ S(n)) dφ 1 (i) ei ( i 1 . . . , n).(6)nFinally, we define the equivalence relation n on P by n n n ,8(7)
Misloveand we note that (P n/ n , n ) is a partial order. We denote by [d] the imageof d P n in P n/ n .Lemma 3.2 Let P be a poset, let n N, and let d, e P n . Then the followingare equi
h: Ta ais an A-morphism satisfying h ηa 1a and h Th h µa. Forexample, domain theory provides three models fornondeterminism, the lower power domain PL,which assigns to a domain the family of Scott-closed 2 See [1] for details about these categories. 3 A domain is coherent if i
Traffic to ParkLogic Keep profitable domains Traffic monetized across parking, affiliate and direct advertising networks Via DNS template Owned registered domains Inbound Traffic Unpaid domains Expired domains Parked domains Domains can be split into unpaid, expired and parked domains by brand. Drop unprofitable domains DNS to ParkLogic
2.3 Probability spaces 22 2.4 Discrete probability spaces 44 2.5 Continuous probability spaces 54 2.6 Independence 68 2.7 Elementary conditional probability 70 2.8 Problems 73 3 Random variables, vectors, and processes 82 3.1 Introduction 82 3.2 Random variables 93 3.3 Distributions of random variables 102 3.4 Random vectors and random .
A random variable (sometimes abbreviated with rv) is a function taking values from the sample space Sand associating numbers with them.2 Conventional notation for random variables uses capital 2 From this definition it’s clear that ran-dom variables are neither random nor variables; the
Probability Distribution. Mean of a Discrete Random Variable. Standard Deviation of a Discrete Random Variable. Binomial Random Variable. Binomial Probability Formula. Tables of the Binomial Distribution. Mean and Standard Deviation of a Binomial Random Variable. Poisson Random Variable. Poisson Probability Formula. Hypergeome tric Random Variable.
Two Types of Random Variables A discrete random variable: Values constitute a finite or countably infinite set A continuous random variable: 1. Its set of possible values is the set of real numbers R, one interval, or a disjoint union of intervals on the real line (e.g., [0, 10] [20, 30]). 2.
Continuous and Discrete random variables Discrete random variables have a countable number of outcomes -Examples: Dead/alive, treatment/placebo, dice, counts, etc. Continuous random variables have an infinite continuum of possible values. -Examples: blood pressure, weight, the speed of a car, the real numbers from 1 to 6.
Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is th
Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is the distribution Gaussian, uniform, or .
