To Display a Set
We consider here a few related ideas:
Early in the 20th century it was noticed that a probability distribution over a topological space was about the same thing as a finite positive measure on that space and the two ideas were largely merged.
The Peano curve maps the unit interval of reals to the unit square continuously while preserving measure; half the interval maps to half the square etc.
We might choose a random point in the square by applying that map to a random number chosen from the uniform distribution on the interval.
The programmer will choose the point in the square by first choosing X and then Y.
With a bit more work he could choose bits alternately for X and Y and this would preserve measure and satisfy the mathematician.
This mapping would be discontinuous but with a small finite state machine the program can consume a string of random bits and produce bits of X and Y resulting in a continuous map from the interval onto the square that also preserves measure.
That machine was Peano’s invention.
- Choosing a set member according to some given probability distribution,
- Finding a one-to-many map from the reals to sets that preserve a probability distribution (measure),
- Enumerating the members of a set which is to find a one-to-one map from the natural numbers to the set,
- Finding effective enumerations which are efficient to compute.
To choose a point in the unit circle the programmer will typically choose a point in [0, 1]×[0, 1], map that to a point in [−1, 1]×[−1, 1] by a linear transformation, and then reject the choice unless the point fall within the circle.
This means that a good deal of entropy is wasted.
This may be objectionable on two counts:
- Entropy may be expensive (but this is not often the case),
- The mapping is no longer measure preserving.
Several Particular Maps
Here we choose a random member from a very large finite set of ‘lite bit arrays’.
Indeed we provide an algorithm for displaying the j’th element from the lexicographic enumeration of the set.
Here we choose a random point within a simplex while squandering log(n!) bits of entropy.
Here we choose a random point on a hemisphere for a certain physics application, squandering about ½ the random bits.
Routine rnd here chooses a real number distributed according to Gauss’s normal distribution.
It squanders about ½ the random bits.
This generates a random permutation of n integers.
It consumes die choices from k sided dies.
It would be good to specify an efficient algorithm based on a random bit stream.