Re: Who's familiar with random oracle model?

From: D. J. Bernstein (djb_at_cr.yp.to)
Date: 11/01/04 

Date: Mon, 1 Nov 2004 19:39:09 +0000 (UTC)

Anton Stiglic wrote:
> I looked at your defintion and the definitions at MathWorld:
> http://mathworld.wolfram.com/DistributionFunction.html
> http://mathworld.wolfram.com/ProbabilitySpace.html

Perhaps an example will help. The cumulative distribution function of a
fair die roll is the function

   1 |-> 1/6, 2 |-> 1/3, 3 |-> 1/2, 4 |-> 2/3, 5 |-> 5/6, 6 |-> 1.

The distribution of a fair die roll is the function

   {} |-> 0, {1} |-> 1/6, {2} |-> 1/6, {3} |-> 1/6, {4} |-> 1/6,
   {5} |-> 1/6, {6} |-> 1/6, {1,2} |-> 1/3, {1,3} |-> 1/3,
   {1,4} |-> 1/3, {1,5} |-> 1/3, {1,6} |-> 1/3, {2,3} |-> 1/3,
   {2,4} |-> 1/3, {2,5} |-> 1/3, {2,6} |-> 1/3, {3,4} |-> 1/3,
   {3,5} |-> 1/3, {3,6} |-> 1/3, {4,5} |-> 1/3, {4,6} |-> 1/3,
   {5,6} |-> 1/3, {1,2,3} |-> 1/2, {1,2,4} |-> 1/2, {1,2,5} |-> 1/2,
   {1,2,6} |-> 1/2, {1,3,4} |-> 1/2, {1,3,5} |-> 1/2, {1,3,6} |-> 1/2,
   {1,4,5} |-> 1/2, {1,4,6} |-> 1/2, {1,5,6} |-> 1/2, {2,3,4} |-> 1/2,
   {2,3,5} |-> 1/2, {2,3,6} |-> 1/2, {2,4,5} |-> 1/2, {2,4,6} |-> 1/2,
   {2,5,6} |-> 1/2, {3,4,5} |-> 1/2, {3,4,6} |-> 1/2, {3,5,6} |-> 1/2,
   {4,5,6} |-> 1/2, {1,2,3,4} |-> 2/3, {1,2,3,5} |-> 2/3,
   {1,2,3,6} |-> 2/3, {1,2,4,5} |-> 2/3, {1,2,4,6} |-> 2/3,
   {1,2,5,6} |-> 2/3, {1,3,4,5} |-> 2/3, {1,3,4,6} |-> 2/3,
   {1,3,5,6} |-> 2/3, {1,4,5,6} |-> 2/3, {2,3,4,5} |-> 2/3,
   {2,3,4,6} |-> 2/3, {2,3,5,6} |-> 2/3, {2,4,5,6} |-> 2/3,
   {3,4,5,6} |-> 2/3, {1,2,3,4,5} |-> 5/6, {1,2,3,4,6} |-> 5/6,
   {1,2,3,5,6} |-> 5/6, {1,2,4,5,6} |-> 5/6, {1,3,4,5,6} |-> 5/6,
   {2,3,4,5,6} |-> 5/6, {1,2,3,4,5,6} |-> 1.

If you put together

   * the set {1,2,3,4,5,6},
   * the collection of subsets listed above, and
   * the distribution shown above,

you get a probability space.

Distributions carry exactly the same information as probability spaces,
and they have a simpler user interface, so people talk about them more
often.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

Quantcast