[RNG-99] AliasMethodDiscreteSampler

• Type: New Feature
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.3
• Fix Version/s: 1.3
• Component/s: sampling
• Assignee: Alex Herbert
• Reporter: Alex Herbert
• Created: 01/May/19 12:20
• Updated: 22/May/22 14:47
• Resolved: 26/Jun/19 10:14

Description

From Wikipedia:

Alias Method

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.

Create a sampler using the Alias method:

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
    }
}

Issue Links

• relates to: RNG-179 The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions
• relates to: RNG-109 DiscreteProbabilityCollectionSampler to use an internal DiscreteSampler
• links to: GitHub Pull Request #53