honey::DiscreteGen_< Real > Class Template Reference

Generate a random integer variate from a generalized discrete distribution. More...

#include <DiscreteGen.h>

Inheritance diagram for honey::DiscreteGen_< Real >:

Collaboration diagram for honey::DiscreteGen_< Real >:

Public Types
typedef vector< Real >	List

Public Member Functions
	DiscreteGen_ (RandomGen &gen, List pdf)
virtual Real	next () const
	Get next randomly distributed variate. Requires a random generator (see ctor or setGen()) More...
virtual Real	pdf (Real x) const
	Probability Density Function. More...
virtual Real	cdf (Real x) const
	Cumulative Distribution Function. More...
virtual Real	cdfInv (Real P) const
	Inverse of the CDF. More...
virtual Real	mean () const
	Calc mean. More...
virtual Real	variance () const
	Calc variance. More...
szt	variateMin () const
szt	variateMax () const
Public Member Functions inherited from honey::RandomDist< Real >
	RandomDist (optional< RandomGen & > gen=optnull)
	Construct with a random generator to use for next() More...
virtual	~RandomDist ()
virtual Real	cdfComp (Real x) const
	Complement of the CDF. More...
Real	stdDev () const
	Calc standard deviation. More...
void	setGen (RandomGen &gen)
	Set random generator to use for next() More...
RandomGen &	getGen () const
	Get random generator. More...

Friends
template<class >
class	DiscreteGen_

Additional Inherited Members
Protected Types inherited from honey::RandomDist< Real >
typedef Numeral< Real >::Real_	Real_
typedef Real_::DoubleType	Double_
typedef Double_::Real	Double
typedef Alge_< Real >	Alge
typedef Alge_< Double >	Alge_d
typedef Uniform_< Double >	Uniform
Protected Member Functions inherited from honey::RandomDist< Real >
Real	cdfInvFind (Real P, Real min, Real max, bool discrete=false) const
	Generic binary search algorithm to find Cdf. More...

Detailed Description

template<class Real>
class honey::DiscreteGen_< Real >

Generate a random integer variate from a generalized discrete distribution.

A generalized discrete distribution takes a list of N probabilities and generates variates suitable for array indexing (0 to N-1). The probabilities are weights, they can be any real number (don't have to be between 0 and 1). The list will be normalized during initialization. After normalization, all probabilities will be in range [0,1] and add up to 1.

Parameters

pdf	List of N probabilities. Probability range > 0

Return values

x	Random integer variate. Range [0,N-1]

Member Typedef Documentation

template<class Real >

typedef vector<Real> honey::DiscreteGen_< Real >::List

Constructor & Destructor Documentation

template<class Real >

honey::DiscreteGen_< Real >::DiscreteGen_	(	RandomGen &	gen,
		List	pdf
	)

Build a lookup table of size N = PdfSize so that variate generation is constant time O(1). Every index in the lookup table has a uniform chance of P = 1 / N because the index is selected with: Uniform().next() * N We need to convert this uniform chance per table index into a weighted chance per table index.

The strategy is to cram 2 probability weights into each table index:

• First we select a random index with Uniform().next() * N. Lets say the result is 10.3, so we use index 10.
• We then use the left-over fractional component (0.3) to select one of the two probablities at index 10.

Since the weights are normalized between 0 and 1 and add up to 1, there must be at least one weight < P, and at least one weight > P

We cram 2 weights into an index by first dropping in an entire weight that is < P, then we fill up to P using a portion of a large weight that is > P. The leftover portion of the large weight (which now may be < P) will go on to fill the next table index.

In the end, the normalized weights will fill up the table slots exactly, giving a perfect weighted lookup table.

Member Function Documentation

template<class Real >

Real honey::DiscreteGen_< Real >::cdf ( Real  x ) const

virtual

Cumulative Distribution Function.

The integral of the PDF from -inf to x.

Parameters

x	value, range depends on distribution.

Return values

P	a probability in range [0,1] that a random variate will be <= x.

Reimplemented from honey::RandomDist< Real >.

template<class Real >

Real honey::DiscreteGen_< Real >::cdfInv ( Real  P ) const

virtual

Inverse of the CDF.

Parameters

P	cumulative probability

Return values

x	A value that has probability P of being >= a random variate X. Also, x satisfies: cdf(x) = P.

Reimplemented from honey::RandomDist< Real >.

template<class Real >

virtual Real honey::DiscreteGen_< Real >::mean ( ) const

inlinevirtual

Calc mean.

Reimplemented from honey::RandomDist< Real >.

template<class Real >

Real honey::DiscreteGen_< Real >::next ( ) const

virtual

Get next randomly distributed variate. Requires a random generator (see ctor or setGen())

Reimplemented from honey::RandomDist< Real >.

template<class Real >

Real honey::DiscreteGen_< Real >::pdf ( Real  x ) const

virtual

Probability Density Function.

The PDF integrates to 1 over the entire range of possible values of x.

Parameters

x	value, range depends on distribution.

Return values

p	a relative likelihood in range [0,inf] that a random variate X will equal x.

Reimplemented from honey::RandomDist< Real >.

template<class Real >

virtual Real honey::DiscreteGen_< Real >::variance ( ) const

inlinevirtual

Calc variance.

Reimplemented from honey::RandomDist< Real >.

template<class Real >

szt honey::DiscreteGen_< Real >::variateMax ( ) const

inline

template<class Real >

szt honey::DiscreteGen_< Real >::variateMin ( ) const

inline

Friends And Related Function Documentation

template<class Real >

template<class >

friend class DiscreteGen_

friend

---

The documentation for this class was generated from the following files:

• src/common/Honey/Math/Random/Dist/DiscreteGen.h
• src/common/Honey/Math/Random/Dist/DiscreteGen.cpp