[RNG-99] AliasMethodDiscreteSampler - ASF JIRA

Voters

Watch issue

Watchers

Link

Clone

Update Comment Author

Replace String in Comment

Update Comment Visibility

Delete Comments

XML

Word

Printable

JSON

Details

Type: New Feature
Status: Closed
Priority: Minor
Resolution: Implemented
Affects Version/s: 1.3
Fix Version/s: 1.3
Component/s: sampling
Labels:
None

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