To Display a Set

We consider here a few related ideas:

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.

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. See this. 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.

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.

Biased Binary