Generates random numbers following a discrete distribution.

You're viewing an older version of this page (#368). View the current version.

View versions (2)

Interface

Overview

This class generates random numbers from a discrete distribution and is optimised for sampling a small population many times.

The discrete statistical distribution can only take discrete values. It has probability function

P(x_k) \qquad k = 1, 2, \ldots, n
(1)

cumulative distribution function

D(x_n) = \sum_{k = 1} ^ n P(x_k)
(2)

and population mean

\mu = \frac{1}{n} \sum_{k = 1} ^ n P(x_k)
(3)



When this class is first initialised, it calculates the CDF of the probability array (so there is a small initialisation cost). With each request for a new random number, it generates an uniform random deviate between 0 and 1 and finds its corresponding abscissa value, as illustrated in the graph below. A binary search is used to detect the interval in which that value is situated, which in return gives the actual discrete random number. For instance if the ordinate would be approximately equal to 0.7 as in the graph, the corresponding abscissa would be around 20000, which corresponds to an index in the values array that finally gives the random number.

1/cdf.png

Speed

The average running time for generating 100,000,000 random numbers using this class on a 750MHz microprocessor is 16 seconds.

Example 1

The given example displays 20 random floating point numbers from a discrete distribution. It uses two different generators to achieve this. The first generator uses a particular value to initialize the seed, while the second one is using the system timer. Notice that it was necessary to divide the timer by the <em> MERSENNEDIV </em> value in order to keep the seed in the interval from 0 to 1. Since the seed of the first generator is never changed, the first 10 numbers will always remain the same. However since the second generator is initialized via the system timer, the next 10 numbers will obviously vary with each execution of the program.

Also notice the declaration of the probability array P and value array V. They are used as constructor arguments when declaring the generators to specify the probabilities P[i] associated to each value V[i] in the values table. Always make sure that the components of P sum up to 1.

#include <iostream>
#include <time.h>
#include <codecogs/statistics/distributions/discrete/discrete/randomsample.h>
using namespace std;

int main()
{
  double P[4] = {   0.4,   0.1,   0.2,   0.3 };
  double V[4] = { 1.234, 2.345, 3.456, 4.567 };
		
  Stats::Dists::Discrete::Discrete::RandomSample<double> A(4, P, V, false, 0.3416);
  Stats::Dists::Discrete::Discrete::RandomSample<double> B(4, P, false, time(0) / MERSENNEDIV);
		
  for (int i = 0; i < 20; ++i)
    cout << A.genReal() << " ";
  cout << endl;
		
  for (int i = 0; i < 20; ++i)
    cout << B.genReal() << " ";
  cout << endl;
		
  return 0;
}

Output:

4.567 1.234 4.567 1.234 4.567 3.456 1.234 2.345 1.234 1.234 1.234 3.456 3.456 2.345 2.345 3.456 4.567 3.456 1.234 2.345 
0 0 0 3 0 0 2 0 2 1 1 0 3 0 3 0 0 3 2 0

References

  • MathWorld, http://mathworld.wolfram.com/DiscreteDistribution.html
  • The Newran03 random number generator library of Robert Davies, http://www.robertnz.net/nr03doc.htm
GPL Licence — free for non commercial use. See Licence details.

Members of RandomSample

CLASS METHOD

RandomSample

Constructor that sets up the class variables and initializes the associated random number generator with the given seed.

Parameters

seed
Default value = 0.2354
normalise
Set this value to 'true' to normalise the data provided in /e p, so it sums up to 1.
val
Array of associated values. It not specified they will be a sequential series from 0 to n-1. i.e.
Blank
V[n] = {0, 1, 2, ..., n - 1}

Parameters

p
Array of probabilities (should sum up to 1; otherwise you must normalise the data by setting normalise=true).
n
Number of points.

CLASS METHOD

RandomSample

Constructor that sets up the class variables and initializes the associated random number generator with the given seed.

Parameters

seed
Default value = 0.2354
normalise
Set this value to 'true' to normalise the data provided in /e p, so it sums up to 1.
p
Array of probabilities (should sum up to 1; otherwise you must normalise the data by setting normalise=true).
n
Number of points.

CLASS METHOD

RandomSample

CLASS METHOD

init

Parameters

normalise
Default Value = true

CLASS METHOD

genIndex

CLASS METHOD

genReal

CLASS METHOD

sample

This function is a simple wrapper around the randomsample class provided in this module. It uses a static to keep a single instance of this class, so that each call to this function returns a new random number. As a result this function is not necessarily thread safe, in the sense that with an identical initial seed, the sequence of random numbers may differ on a multitasking or multi threaded system.

The seed is only set on the first call to this function. Thereafter this parameter is ignored. If you do no want to set the seed, then we suggest you use the system clock the first time you call this function, i.e.

#include <time.h>
 ...
 sample(N,  p, time(0) / MERSENNEDIV);

If you require more advance behaviour, we strongly recommend that you directly use the underlying class randomsample that is provided with this module.

Parameters

N
the number of rates in custom distribution
p
an array of N rates that define the occurrence rate of each event.
normalise
Default Value = true
seed
sets the initial seed for the random generator. Only used in the first call to this function

Returns

this function returns an index in the range 0 to (N-1), which act as an index into the array define in p.