Probabilities and Probabilistic Functions

Let 5 be a probability space. denotes the probability of an element e and Ps( that of an event E. Usually, S is omitted, because it is clear from the context. All well-known notations from probability theory are used. A probability space and its distribution are not always carefiilly distinguished. 

If S is discrete, [5] denotes the carrier set, i.e., the elements with non-zero probability. 

If a value is chosen from 5 according to the given probability distribution and assigned to a variable x, this is denoted by x — 5. If the value of x is chosen from a given set X with uniform distribution, one also writes x g r X. 

The usual sign where I write is I . However, this, notation describes the definition of a new probability space on n-tuples (xj,. .., x ) from n given probability spaces rather than a conditional probability. Moreover, one can now formulate conditional probabilities in the newly defined probability space, such as 

A probabilistic function/from a set X to a set 7 is a function from X to the set of probability spaces on Y. The reason is that the relation of a probabilistic function to a probabilistic algorithm should be the same as that of a usual function to a deterministic algorithm. Hence for every input i, the term/(i) denotes a probability space on Y. 

---