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