[ 
https://issues.apache.org/jira/browse/RNG-179?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17541972#comment-17541972
 ] 

Alex Herbert commented on RNG-179:
----------------------------------

{quote}I thought integer sampling (the case when all weights are integer) does 
not require going for floats, doubles, etc.
{quote}
The API allows for construction using long[] as frequencies. This corresponds 
to {{{}fldr.c{}}}.

The construction using double[] as weights corresponds to {{{}fldrf.c{}}}.

However to plug the sampler into the existing performance benchmark requires a 
double[] for the distribution. This only affects the performance measure on the 
construction cost (single sample).

Once the sampler is built then the sampling algorithm is the same. It uses only 
integer look-up tables and a source of boolean bits.

For reference I have computed the Shannon entropy for the distributions in the 
performance benchmark.
||Distribution||n||Shannon entropy (bits)||
|4 Sided Loaded Die|4|1.626|
|Binomial(n=67, p=0.7)|68|3.953|
|Geometric(p=0.2)|93|3.610|
|Poisson (mean=3.22)|20|2.842|
|Poisson (mean1=10, mean2=20)|53|7.236|

So as mentioned above the 4 sided loaded die has the lowest entropy. Note that 
for the probability distributions these are truncated with a CDF of 0.999999999 
(1 - 1e-9).

The benchmark should perhaps be updated to use a [Dirichlet distribution 
|https://en.wikipedia.org/wiki/Dirichlet_distribution]. This sampler was added 
in RNG 1.4 after the benchmark was created. A quick test shows that the size 
and alpha parameter can be used to create distributions of various entropy:
{code:java}
ObjectSampler<double[]> s = DirichletSampler.symmetric(rng, k, alpha)
{code}
||k||alpha||entropy mean||sd||
|4|0.500|1.299|0.374|
|4|1.000|1.531|0.294|
|4|2.000|1.754|0.172|
|8|0.500|2.087|0.348|
|8|1.000|2.490|0.266|
|8|2.000|2.707|0.142|
|16|0.500|3.023|0.287|
|16|1.000|3.454|0.166|
|16|2.000|3.693|0.095|
|32|0.500|4.008|0.182|
|32|1.000|4.406|0.125|
|32|2.000|4.692|0.075|
|64|0.500|4.986|0.151|
|64|1.000|5.392|0.115|
|64|2.000|5.680|0.048|

 
{quote}Given that you've already done all the work, and that it is a documented 
algorithm, I'd think that it should be included 
{quote}
OK. I will update the code with some more information about performance and the 
benefit of exact sampling. I have already added some notes to the factory 
constructor javadoc using the double[] weights to indicate when the long[] 
method can be used.

Note that exact sampling is a strange advantage. In order to notice this would 
require that a lot of samples are obtained from the sampler, for example 2^53 
samples. This is likely to be generated with days of continuous sampling. It 
also requires that the source of bits is unbiased, which is never ensured with 
a RNG unless the full period of an unbiased sampler is used, for example the 
entire 2^64 longs output from a SplitMix generator.

However it may be that a user wishes to construct a distribution such as:
{code:java}
double[] weights = {1, 1, Math.scalb(1.0, -53), Math.scalb(1.0, -100)};
{code}
There is no other sampler in the library that can perform this and ensure that 
category 3 is observed with a probability of approximately 2^-99 (i.e. 2^-100 / 
sum(weights)). All other samplers would ignore 2^-100 and some may ignore 2^-53 
when converting the weights to probabilities.

You would have to run the sampler a long time to obtain category 2 or 3, but at 
least it would be possible.

 

> The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete 
> Probability Distributions
> ------------------------------------------------------------------------------------------------
>
>                 Key: RNG-179
>                 URL: https://issues.apache.org/jira/browse/RNG-179
>             Project: Commons RNG
>          Issue Type: New Feature
>          Components: sampling
>            Reporter: Vladimir Sitnikov
>            Priority: Major
>          Time Spent: 10m
>  Remaining Estimate: 0h
>
> It might make sense to implement Fast Loaded Dice Roller sampler.
> See https://arxiv.org/pdf/2003.03830v2.pdf, 
> https://github.com/probcomp/fast-loaded-dice-roller
> The authors claim that Fast Loaded Dice Roller is faster than the Alias 
> Method.



--
This message was sent by Atlassian Jira
(v8.20.7#820007)

Reply via email to