Re: [Boost-users] [Boost.Random] Discrete distribution behavior

Subject: Re: [Boost-users] [Boost.Random] Discrete distribution behavior
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-06-05 01:57:28

AMDG

On 06/04/2012 01:53 PM, sguazt wrote:
> Dear Booster,
> 
> I have a problem in understanding how the
> boost::random::discrete_distribution works.
> 
> As far as I know, given the following events: x1, x2 and x2 and
> weights: 1, 4, and 5,
> * the associated PDF of the discrete distribution would be:
> \Pr{X=x1}=1/10
> \Pr{X=x2}=4/10
> \Pr{X=x3}=5/10
> 
> * and the CDF would be:
> \Pr{X<=x1}=1/10
> \Pr{X<=x2}=5/10
> \Pr{X<=x3}=1
> 
> So, if my random generator generates the value 0.814724, the discrete
> random variate would return the event x3 (if I'm not wrong).
> 

Wrong.  The implementation does not use
the inverse cdf.  It uses Walker's alias
algorithm which generated variates in
constant time.

The algorithm generates a table
that looks like this:

std::vector<std::pair<double, int> > table = {
  { 0.3, 1 },
  { 0.5, 2 },
  { 1.0, 0 }
};

Then the generation algorithm is

double x = uniform_01<>(engine);
int result = uniform_int<>(0, 2)(engine);
if (x < table[result].first) return result;
else return table[result].second;

If you work out the probabilities, you'll
find that they add up correctly.

In Christ,
Steven Watanabe