[RNG-109] DiscreteProbabilityCollectionSampler to use an internal DiscreteSampler

• Type: Improvement
• 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: 26/Jun/19 10:25
• Updated: 25/May/22 06:46
• Resolved: 07/Aug/19 12:13

Description

The DiscreteProbabilityCollectionSampler builds a cumulative probability distribution from an input of items and their associated probabilities. This is sampled using a binary search (O(log n) time).

The library now contains DiscreteSamplers that can sample efficiently (approaching O(1) time) from a cumulative probability distribution:

• AliasMethodDiscreteSampler
• GuideTableDiscreteSampler

Test these samplers to determine which is appropriate to use as the algorithm behind the DiscreteProbabilityCollectionSampler. The test should include:

• Construction time
• Sample time
• A range of distributions (uniform, linear ramp, Poisson, Geometric, BiModal, TriModel, Random scatter)

 

Issue Links

• is related to: RNG-99 AliasMethodDiscreteSampler
• is related to: RNG-100 GuideTableDiscreteSampler
• relates to: RNG-179 The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions
• links to: GitHub Pull Request #62