[
https://issues.apache.org/jira/browse/RNG-99?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16831046#comment-16831046
]
Alex D Herbert commented on RNG-99:
-----------------------------------
{quote}Do you intend to provide a "combined" implementation that will select
the best method according to the input(s)?
{quote}
The Alias method benefits from the table being a size that is a power of 2.
This is just so the first look-up can use the modulus operator (or a mask) on
an int to get the index. My implementation uses up to 11 bits for the index and
the remaining 53 bits to generate a double. This works for tables up to 2^11 or
2048 in size. After that the method requires 96-bits from a generator, 32 for
an int index and 64 to create a double.
The example cases on the Wikipedia Alias page are extreme. Obviously selecting
from uniform distributions should use nextBoolean() (for 2) or nextInt(int).
Selecting from a distribution with probabilities that are not irrational (i.e.
can be rounded to a nice number of significant digits) can be done using more
advanced guide table methods. The method suggested is an advanced guide table
method that relies on expressing probabilities as unsigned 30-bit integers with
an assumed denominator of 2^30.
It provides an example for Poisson and Binomial distributions. It appears to
require 30-bits per sample expressing 5 digits of a base-64 number.
Unfortunately the c code core dumps when I run it. So this will require an
investigation. But it may be a method that can be used for Poisson sampling and
perhaps more generic sampling from rounded probabilities. I'll just have to get
it to work so I can investigate.
> AliasMethodDiscreteSampler
> --------------------------
>
> Key: RNG-99
> URL: https://issues.apache.org/jira/browse/RNG-99
> Project: Commons RNG
> Issue Type: New Feature
> Components: sampling
> Affects Versions: 1.3
> Reporter: Alex D Herbert
> Assignee: Alex D Herbert
> Priority: Minor
> Fix For: 1.3
>
>
> From Wikipedia:
> [Alias Method|https://en.wikipedia.org/wiki/Alias_method]
> {noformat}
> In computing, the alias method is a family of efficient algorithms for
> sampling from
> a discrete probability distribution, due to A. J. Walker. That is, it returns
> integer
> values 1 ≤ i ≤ n according to some arbitrary probability distribution. The
> algorithms
> typically use O(n log n) or O(n) preprocessing time, after which random
> values can
> be drawn from the distribution in O(1) time.
> {noformat}
> Create a sampler using the Alias method:
> {code:java}
> package org.apache.commons.rng.sampling.distribution;
> public class AliasMethodDiscreteSampler implements DiscreteSampler {
> public AliasMethodDiscreteSampler(UniformRandomProvider rng,
> double[] probabilities) {
> // Validate probabilities sum to >0
> // Construct alias tables
> }
> @Override
> public int sample() {
> // Sample from alias tables
> }
> }
> {code}
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
