[
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)