[jira] [Created] (RNG-100) GuideTableDiscreteSampler

["Alex D Herbert (JIRA)" <ji...@apache.org>]

Alex D Herbert created RNG-100:
----------------------------------

             Summary: GuideTableDiscreteSampler
                 Key: RNG-100
                 URL: https://issues.apache.org/jira/browse/RNG-100
             Project: Commons RNG
          Issue Type: New Feature
          Components: sampling
    Affects Versions: 1.3
            Reporter: Alex D Herbert
            Assignee: Alex D Herbert
             Fix For: 1.3


From
{noformat}
Devroye, Luc (1986). Non-Uniform Random Variate Generation.
New York: Springer-Verlag. Chapter 3.2.4 "The method of guide tables" p. 96.
{noformat}
[Chapter 3|http://luc.devroye.org/chapter_three.pdf] from the author's website.

The method divides the range for the cumulative probability table of {{K}} values into {{alpha * K}} equispaced intervals. Each interval i contains the maximum sample value where the cumulative probability is less than i / table.length.

Given a uniform deviate u in the range [0, 1] the guide can be obtained using floor(u * table.length). This guide value is the start point for search of the cumulative probability table. The number of comparisons of the uniform deviate within the cumulative probability table is upper bounded by 2 (see Devroye, p97) making the search very efficient.

Create a sampler using the Guide table method:
{code:java}
package org.apache.commons.rng.sampling.distribution;

public class GuideTableDiscreteSampler implements DiscreteSampler {
    public GuideTableDiscreteSampler(UniformRandomProvider rng, 
                                     double[] probabilities,
                                     double alpha) {
        // Validate probabilities sum to >0
        // Construct cumulative probability table
        // Construct guide table
    }

    @Override
    public int sample() {
        // Look-up sample value in guide table
        // Search cumulative probability table
    }
}
{code}

The alpha value is not required. However large alpha increase the size of the guide table and improve performance at the cost of storage.




--
This message was sent by Atlassian JIRA
(v7.6.3#76005)