CODEWITHSUNDEEP
c++c++11randomdistribution
LSchueler
LSchueler

Reputation: 1514

Own implementation of Random Number Distribution for C++11

I need to implement my own random number distribution class in C++11, but I can't find a minimalistic implementation to get me started.

I have already searched the gcc source code, but only found the header files and not the implementations of the different non-uniform distributions.

Can you point me to a simple yet complete example of a non-uniform distribution class in C++11 or post one here?

Upvotes: 0

Views: 252

Answers (1)

pjs
pjs

Reputation: 19855

I guess implementing your own distribution is nothing too exotic...

You guess wrong. Luc Devroye wrote an 800 page book on the topic. There is no single technique that works for all distributions. There are 4 general approaches:

  1. Inversion - If the cumulative distribution function FX(b), -∞ < b < ∞, is a continuous and invertible function, then FX(X), the CDF applied to its own random variable, has a uniform(0,1) distribution. Equate FX(X)=U and solve for X (if possible).

  2. Convolution - Summing or differencing random variables yields a new distribution. For instance, the sum of two uniforms has a triangular distribution; or, the sum of n independent chi-squared(1)'s yields a chi-square(n)

  3. Composition - Some complex distributions can be built up piecewise from simpler distributions using conditional probability.

  4. Tricks/special relations - Leverage unique relationships between different distributions such as the fact that the square of a standard normal is a chi-squared(1) random variable; or that a chi-squared(2) is identical to an exponential(2). Together with Pythagoras' thm, these two facts are at the heart of the Box-Muller method for generating normals. Plot two independent standard normals together, and you get a 2-d vector from (0,0) which heads off in a uniform(0,2π) direction and has length sqrt(exponential(2)). Generate such a vector and convert it back to Cartesian coordinates using both sine and cosine transformations to yield the two independent normals.

Devroye's book fills in the details for many "popular" distributions, but since there are an infinite number of distributions out there an exhaustive treatment would be impossible.

Section 4.3 on page 59 of this tutorial paper has one worked example for each of the four techniques sketched out above, and a proof of inversion on pages 60-62.

Upvotes: 4

Related Questions