# Random Number Library Distributions

- Introduction
- Synopsis
- Class template `uniform_smallint`
- Class template `uniform_int`
- Class template `uniform_01`
- Class template `uniform_real`
- Class template `bernoulli_distribution`
- Class template `geometric_distribution`
- Class template `triangle_distribution`
- Class template `exponential_distribution`
- Class template `normal_distribution`
- Class template `lognormal_distribution`
- Class template `uniform_on_sphere`

## Introduction

In addition to the random number generators, this library provides distribution functions which map one distribution (often a uniform distribution provided by some generator) to another.

Usually, there are several possible implementations of any given mapping. Often, there is a choice between using more space, more invocations of the underlying source of random numbers, or more time-consuming arithmetic such as trigonometric functions. This interface description does not mandate any specific implementation. However, implementations which cannot reach certain values of the specified distribution or otherwise do not converge statistically to it are not acceptable.

distribution | explanation | example
--- | --- | ---
`uniform_smallint` | discrete uniform distribution on a small set of integers (much smaller than the range of the underlying generator) | drawing from an urn
`uniform_int` | discrete uniform distribution on a set of integers; the underlying generator may be called several times to gather enough randomness for the output | drawing from an urn
`uniform_01` | continuous uniform distribution on the range [0,1); important basis for other distributions | -
`uniform_real` | continuous uniform distribution on some range [min, max) of real numbers | for the range [0, 2pi): randomly dropping a stick and measuring its angle in radiants (assuming the angle is uniformly distributed)
`bernoulli_distribution` | Bernoulli experiment: discrete boolean valued distribution with configurable probability | tossing a coin (p=0.5)
`geometric_distribution` | measures distance between outcomes of repeated Bernoulli experiments | throwing a die several times and counting the number of tries until a "6" appears for the first time
`triangle_distribution` | ? | ?
`exponential_distribution` | exponential distribution | measuring the inter-arrival time of alpha particles emitted by radioactive matter
`normal_distribution` | counts outcomes of (infinitely) repeated Bernoulli experiments | tossing a coin 10000 times and counting how many front sides are shown
`lognormal_distribution` | lognormal distribution (sometimes used in simulations) | measuring the job completion time of an assembly line worker
`uniform_on_sphere` | uniform distribution on a unit sphere of arbitrary dimension | choosing a random point on Earth (assumed to be a sphere) where to spend the next vacations

The template parameters of the distribution functions are always in the order

- Underlying source of random numbers
- If applicable, return type, with a default to a reasonable type.

All distribution functions satisfy the input iterator requirements (std:24.1.1 [lib.input.iterators]) in addition to the NumberGenerator requirements. After an invocation of `operator()`, the effects of invocations of `operator*` are undefined until the next call to `operator++`.

In this description, I have refrained from documenting those members in detail which are already defined in the concept documentation.

## Synopsis of the distributions in header `<boost/random.hpp>`

    namespace boost {
      template<class UniformRandomNumberGenerator, class IntType = int>
      class uniform_smallint;
      template<class UniformRandomNumberGenerator, class IntType = int>
      class uniform_int;
      template<class UniformRandomNumberGenerator, class RealType = double>
      class uniform_01;
      template<class UniformRandomNumberGenerator, class RealType = double>
      class uniform_real;

      // discrete distributions
      template<class UniformRandomNumberGenerator>
      class bernoulli_distribution;
      template<class UniformRandomNumberGenerator, class IntType = int>
      class geometric_distribution;

      // continuous distributions
      template<class UniformRandomNumberGenerator, class RealType = double>
      class triangle_distribution;
      template<class UniformRandomNumberGenerator, class RealType = double>
      class exponential_distribution;
      template<class UniformRandomNumberGenerator, class RealType = double>
      class normal_distribution;
      template<class UniformRandomNumberGenerator, class RealType = double>
      class lognormal_distribution;
      template<class UniformRandomNumberGenerator, class RealType = double,
        class Cont = std::vector<RealType> >
      class uniform_on_sphere;
    }

## Class template `uniform_smallint`

### Synopsis

    template<class UniformRandomNumberGenerator, class IntType = int>
    class uniform_smallint
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef IntType result_type;
      static const bool has_fixed_range = false;
      uniform_smallint(base_type & rng, IntType min, IntType max);
      result_type operator()();
      result_type min() const;
      result_type max() const;
    };

### Description

The distribution function `uniform_smallint` models a uniform random number generator. On each invocation, it returns a random integer value uniformly distributed in the set of integer numbers {min, min+1, min+2, ..., max}. It assumes that the desired range (max-min+1) is small compared to the range of the underlying source of random numbers and thus makes no attempt to limit quantization errors.

Let rout=(max-min+1) the desired range of integer numbers, and let rbase be the range of the underlying source of random numbers. Then, for the uniform distribution, the theoretical probability for any number i in the range rout will be pout(i) = 1/rout. Likewise, assume a uniform distribution on rbase for the underlying source of random numbers, i.e. pbase(i) = 1/rbase. Let pout_s(i) denote the random distribution generated by `uniform_smallint`. Then the sum over all i in rout of (pout_s(i)/pout(i) -1)2 shall not exceed rout/rbase2 (rbase mod rout)(rout - rbase mod rout).

The template parameter `UniformRandomNumberGenerator` shall denote a class which models a uniform random number generator. Additionally, `UniformRandomNumberGenerator::result_type` shall denote an integral type. The template parameter `IntType` shall denote an integer-like value type.

Note: The property above is the square sum of the relative differences in probabilities between the desired uniform distribution pout(i) and the generated distribution pout_s(i). The property can be fulfilled with the calculation (base_rng mod rout), as follows: Let r = rbase mod rout. The base distribution on rbase is folded onto the range rout. The numbers i < r have assigned (rbase div rout)+1 numbers of the base distribution, the rest has only (rbase div rout). Therefore, pout_s(i) = ((rbase div rout)+1) / rbase for i < r and pout_s(i) = (rbase div rout)/rbase otherwise. Substituting this in the above sum formula leads to the desired result.

Note: The upper bound for (rbase mod rout)(rout - rbase mod rout) is rout2/4. Regarding the upper bound for the square sum of the relative quantization error of rout3/(4*rbase2), it seems wise to either choose rbase so that rbase > 10*rout2 or ensure that rbase is divisible by rout.

### Members

    uniform_smallint(base_type & rng, IntType min, IntType max)

Effects: Constructs a `uniform_smallint` functor with the uniform random number generator `rng` as the underlying source of random numbers. `min` and `max` are the lower and upper bounds of the output range, respectively.

## Class template `uniform_int`

### Synopsis

    template<class UniformRandomNumberGenerator, class IntType = int>
    class uniform_int
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef IntType result_type;
      static const bool has_fixed_range = false;
      uniform_int(base_type & rng, IntType min, IntType max);
      IntType operator()();
      result_type min() const;
      result_type max() const;
    };

### Description

The distribution function `uniform_int` models a uniform random number generator. On each invocation, it returns a random integer value uniformly distributed in the set of integer numbers {min, min+1, min+2, ..., max}.

The template parameter `IntType` shall denote an integer-like value type.

### Members

    uniform_int(base_type & rng, IntType min, IntType max)

Effects: Constructs a `uniform_int` functor with the uniform random number generator `rng` as the underlying source of random numbers. `min` and `max` are the lower and upper bounds of the output range, respectively.

Note: Invocations of `operator()` may call the underlying generator several times and concatenate the result to build the required range. Thus, using this distribution with generators such as linear congruential ones which tend to produce non-random bits in some positions is strongly discouraged.

## Class template `uniform_01`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double>
    class uniform_01
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef RealType result_type;
      static const bool has_fixed_range = false;
      explicit uniform_01(base_type & rng);
      result_type operator()();
      result_type min() const;
      result_type max() const;
    };

### Description

The distribution function `uniform_01` models a uniform random number generator. On each invocation, it returns a random floating-point value uniformly distributed in the range [0..1). The value is computed using `std::numeric_limits<RealType>::digits` random binary digits, i.e. the mantissa of the floating-point value is completely filled with random bits. [Note: Should this be configurable?]

The template parameter `RealType` shall denote a float-like value type with support for binary operators +, -, and /. It must be large enough to hold floating-point numbers of value `rng.max()-rng.min()+1`.

`base_type::result_type` must be a number-like value type, it must support `static_cast<>` to `RealType` and binary operator -.

Note: The current implementation is buggy, because it may not fill all of the mantissa with random bits. I'm unsure how to fill a (to-be-invented) `boost::bigfloat` class with random bits efficiently. It's probably time for a traits class.

### Members

    explicit uniform_01(base_type & rng)

Effects: Constructs a `uniform_01` functor with the given uniform random number generator as the underlying source of random numbers.

## Class template `uniform_real`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double>
    class uniform_real
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef RealType result_type;
      static const bool has_fixed_range = false;
      uniform_real(base_type & rng, RealType min, RealType max);
      result_type operator()();
      result_type min() const;
      result_type max() const;
    };

### Description

The distribution function `uniform_real` models a uniform random number generator. On each invocation, it returns a random floating-point value uniformly distributed in the range [min..max). The value is computed using `std::numeric_limits<RealType>::digits` random binary digits, i.e. the mantissa of the floating-point value is completely filled with random bits.

Note: The current implementation is buggy, because it may not fill all of the mantissa with random bits.

### Members

    explicit uniform_real(base_type & rng, RealType min, RealType max)

Effects: Constructs a `uniform_real` functor. `rng` specifies the uniform random number generator to be used as the underlying source of random numbers, `min` and `max` are the lower and upper bounds of the output range.

## Class template `bernoulli_distribution`

### Synopsis

    template<class UniformRandomNumberGenerator>
    class bernoulli_distribution
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef bool result_type;
      bernoulli_distribution(base_type & rng, double q);
      result_type operator()();
    };

### Description

Instantiations of class template `bernoulli_distribution` model a number generator. It transforms a uniform distribution into a Bernoulli one.

### Members

    bernoulli_distribution(base_type & rng, double q)

Effects: Constructs a `bernoulli_distribution` functor with the uniform random number generator `rng` as the underlying source of random numbers. `q` is the parameter for the distribution.

    result_type operator()()

Returns: A random boolean value with p(true) = q and p(false) = 1-q. For example, with q = 1/2 this can be interpreted as tossing a coin.

## Class template `geometric_distribution`

### Synopsis

    template<class UniformRandomNumberGenerator, class IntType = int>
    class geometric_distribution
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef IntType result_type;
      geometric_distribution(base_type& rng, double q);
      result_type operator()();
    };

### Description

Instantiations of class template `geometric_distribution` model a number generator. It transforms a uniform distribution into a geometric one.

### Members

    geometric_distribution(base_type& rng, const result_type& q)

Effects: Constructs a `geometric_distribution` functor with the uniform random number generator `rng` as the underlying source of random numbers. `q` is the parameter for the distribution.

    result_type operator()()

Returns: A random integer value i >= 1 with p(i) = (1-q) * qi-1. For example, with q = 5/6 this can be interpreted as the number of times one has to roll a die until a given number shows up.

## Class template `triangle_distribution`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double>
    class triangle_distribution
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef RealType result_type;
      triangle_distribution(base_type& rng, result_type a, result_type b, result_type c);
      result_type operator()();
    };

### Description

Instantiations of class template `triangle_distribution` model a number generator. It transforms a uniform distribution into a triangle one.

### Members

    triangle_distribution(base_type& rng, result_type a, result_type b, result_type c)

Effects: Constructs a `triangle_distribution` functor with the uniform random number generator `rng` as the underlying source of random numbers. `a, b, c` are the parameters for the distribution.

    result_type operator()()

Returns: A random floating-point value `x` where `a <= x <= c`; `x` has a triangle distribution, where `b` is the most probable value for `x`.

## Class template `exponential_distribution`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double>
    class exponential_distribution
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef RealType result_type;
      exponential_distribution(base_type& rng, const result_type& lambda);
      result_type operator()();
    };

### Description

Instantiations of class template `exponential_distribution` model a number generator. It transforms a uniform distribution into an exponential one.

### Members

    exponential_distribution(base_type& rng, const result_type& lambda)

Effects: Constructs an `exponential_distribution` functor with the uniform random number generator `rng` as the underlying source of random numbers. `lambda` is the parameter for the distribution.

    result_type operator()()

Returns: A random floating-point value x > 0 with p(x) = `lambda` * exp(-`lambda` * x).

## Class template `normal_distribution`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double>
    class normal_distribution
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef RealType result_type;
      explicit normal_distribution(base_type& rng, const result_type& mean = 0,
    			       const result_type& sigma = 1);
      result_type operator()();
    };

### Description

Instantiations of class template `normal_distribution` model a number generator. It transforms a uniform distribution into a normal (Gaussian) one.

### Members

    normal_distribution(base_type& rng, const result_type& mean = 0,
    		     const result_type& sigma = 1)

Effects: Constructs a `normal_distribution` functor with the uniform random number generator `rng` as the underlying source of random numbers. `mean` and `sigma` are the parameters for the distribution.

    result_type operator()()

Returns: A random floating-point value x with p(x) = 1/sqrt(2*pi*sigma) * exp(- (x-mean)2 / (2*sigma2) ).

## Class template `lognormal_distribution`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double>
    class lognormal_distribution
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef RealType result_type;
      explicit lognormal_distribution(base_type& rng, const result_type& mean,
    			          const result_type& sigma);
      result_type operator()();
    };

### Description

Instantiations of class template `lognormal_distribution` model a number generator. It transforms a uniform distribution into a lognormal one.

### Members

    lognormal_distribution(base_type& rng, const result_type& mean = 0,
    	   	       const result_type& sigma = 1)

Effects: Constructs a `normal_distribution` functor with the uniform random number generator `rng` as the underlying source of random numbers. `mean` and `sigma` are the parameters for the distribution.

    result_type operator()()

Returns: A random floating-point value x with p(x) = 1/(x * sigma * sqrt(2*pi*sigma)) * exp(- (log(x)-mean)2 / (2*sigma2) ) for x > 0.

## Class template `uniform_on_sphere`

### Synopsis

    template<class UniformRandomNumberGenerator, class RealType = double,
      class Cont = std::vector<RealType> >
    class uniform_on_sphere
    {
    public:
      typedef UniformRandomNumberGenerator base_type;
      typedef Cont result_type;
      explicit uniform_on_sphere(base_type & rng, int dim = 2);
      const result_type & operator()();
    };

### Description

Instantiations of class template `uniform_on_sphere` model a Generator (std:25.2.6 [lib.alg.generate]). It transforms a uniform distribution into a uniform distribution on the unit sphere of arbitrary dimension. The `Cont` template parameter must be a STL-like container type with `begin` and `end` operations returning non-const ForwardIterators of type `Cont::iterator`.

### Members

    explicit uniform_on_sphere(base_type & rng, int dim = 2)

Effects: Constructs a `uniform_on_sphere` functor with the uniform random number generator `rng` as the underlying source of random numbers. `dim` is the dimension of the sphere.

    result_type operator()()

Returns: A position on the unit sphere of `dim` dimensions in cartesian coordinates. The positions are uniformly distributed on the unit sphere.

Complexity: Proportional to the number of dimensions.

Jens Maurer, 2000-06-14