
Boost Users : 
Subject: Re: [Boostusers] [Boost.Random] Discrete distribution behavior
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 20120605 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net