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)
