Other random distributions

Back to Other random results. Forward to MPFR interface. Up to Contents.

This library includes implementation of a few other random distributions

• NormalDistribution samples from a Gaussian. This uses the ratio method with Leva's modifications to avoid computing logarithms too frequently.
• ExponentialDistribution samples from an exponential distribution. This is uses FloatU to avoid log(0) and to allow rare large values to be returned.
• RandomSelect selects for a discrete set with specified weights using the Walker algorithm. With integer weights this is an exact implementation.
• LeadingZeros returns the number of zero bits after the binary point of a uniform random number in (0,1). This is exact.
• ExponentialProb returns true with probability exp(−p) using von Neumann's algorithm. This is exact.
• InverseEProb returns true with probability 1/e using von Neumann's algorithm. This is exact.
• InversePiProb returns true with probability 1/π using one of Ramanujan's expansions for 1/π. (The algorithm is from Flajolet et al., 2011.) This is exact.
• DiscreteNormal and DiscreteNormalAlt are two classes for sampling from the discrete normal distribution; the first is tuned for speed and the second is tuned to minimize the use of random bits. (These are based on the algorithm used by ExactNormal.) These are exact.
• UniformInteger provides a facility for partially sampling integers from the interval [0,m). DiscreteNormalAlt uses this class to achieve ideal scaling in the consumption of random bits. 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 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 which return a RandomNumber

• ExactExponential samples exactly from an exponential distribution. The surprisingly simple algorithm is due to von Neumann but adapted here to use infinite precision.
• ExactNormal samples exactly from a normal distribution. This applies the ideas behind ExactExponential to the normal distribution.
• 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 5.6 + 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 algorithms used by ExactExponential and ExactNormal have been included in MPFR. See also MPFR interface.

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⁻⁵⁴) (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; r.Reseed();
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 << "\n";
}

A more extensive example of generating exact distributions is given by RandomExact.cpp.

Back to Other random results. Forward to MPFR interface. Up to Contents.