Other random distributions

Back to Other random results. Forward to Saving and restoring the state. Up to Contents.

This library includes implementation of a few other random distributions

• RandomLib::NormalDistribution samples from a Gaussian. This uses the ratio method with Leva's modifications to avoid computing logarithms too frequently.
• RandomLib::ExponentialDistribution samples from an exponential distribution. This is uses FloatU to avoid log(0) and to allow rare large values to be returned.
• RandomLib::RandomSelect selects for a discrete set with specified weights using the Walker algorithm. With integer weights this is an exact implementation.
• RandomLib::LeadingZeros returns the number of zero bits after the binary point of a uniform random number in (0,1). This is exact.
• RandomLib::ExponentialProb returns true with probability exp(-p) using von Neumann's algorithm. This is exact.

These provide fast, reasonably accurate (or, where noted, exact) implementations of these distributions.

In general, it is difficult to sample from an distribution and round the result exactly to the nearest representable real number. However, for some simple distributions, the exact distribution is given by a series of uniform distributions and this provides a method for sampling exactly. The class which represents the result of sampling from such distributions is RandomLib::RandomNumber. It can be thought of as an infinite precision random number. At any time only some of the leading digits have been computed and the result then stands for any number obtained by filling in the remaining digits uniformly and randomly. The following are distributions with return a RandomNumber

• RandomLib::ExactExponential samples exactly from an exponential distribution. The surprisingly simple algorithm is due to von Neumann but adapted here to use infinite precision.
• RandomLib::ExactPower samples exactly from a power distribution (n + 1) xⁿ for x in (0,1) and integer n >= 0.

No attempt has been to optimize these exact distributions for speed. However, with base = 2, ExactExponential delivers k bits of accuracy consuming, on average, only about 8 + k bits of randomness; so a fast implementation is possible. (Similarly it's possible to return true with probability 1/e consuming 6 bits of randomness.)

The following code samples from the exponential distribution, rounding the results exactly to the nearest double. Thus the probability that 0.75 is returned is exactly 2 exp(-3/4) sinh(2^-54) (with no error in the evaluation of exp and sinh). (This assumes, of course, that the underlying random number generator is perfect.)

  RandomLib::Random r;
  const int b = 32;
  RandomLib::ExactExponential<b> edist;
  for (size_t i = 0; i < 10; ++i) {
    RandomLib::RandomNumber<b> x = edist(r);  // Sample exactly
    double y = x.Value<double>(r); // Round exactly to nearest double
    std::cout << y << std::endl;
  }

Back to Other random results. Forward to Saving and restoring the state. Up to Contents.