Expand description

Fast Loaded Dice Roller

The Fast Loaded Dice Roller (FLDR)* algorithm is a space and time efficient algorithm for near-optimal sampling from a weighted discrete distribution. This crate provides an implementation of the FLDR algorithm that is generic over the type of random number generator (RNG) used. There is an optional implementation, rand::RngCoin<R>, that uses the rand crate as a dependency for convenience.

Citation

I neither created nor discovered the FLDR algorithm. This crate is simply an implementation.

* Citation for the Fast Loaded Dice Roller algorithm:

@inproceedings{saad2020fldr,
  title           = {The Fast Loaded Dice Roller: A Near-optimal Exact Sampler for Discrete Probability Distributions},
  author          = {Saad, Feras A. and Freer, Cameron E. and Rinard, Martin C. and Mansinghka, Vikash K.},
  booktitle       = {AISTATS 2020: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics},
  volume          = 108,
  series          = {Proceedings of Machine Learning Research},
  address         = {Palermo, Sicily, Italy},
  publisher       = {PMLR},
  year            = 2020,
  keywords        = {random variate generation, sampling, discrete random variables},
  abstract        = {This paper introduces a new algorithm for the fundamental problem of generating a random integer from a discrete probability distribution using a source of independent and unbiased random coin flips. This algorithm, which we call the Fast Loaded Dice Roller (FLDR), has efficient complexity properties in space and time: the size of the sampler is guaranteed to be linear in the number of bits needed to encode the target distribution and the sampler consumes (in expectation) at most 6.5 bits of entropy more than the information-theoretically minimal rate, independently of the values or size of the target distribution. We present an easy-to-implement, linear-time preprocessing algorithm and a fast implementation of the FLDR using unsigned integer arithmetic. Empirical evaluations establish that the FLDR is 2x--10x faster than multiple baseline algorithms for exact sampling, including the widely-used alias and interval samplers. It also uses up to 10000x less space than the information-theoretically optimal sampler, at the expense of a less than 1.5x runtime overhead.},
}

Structs

  • Represents the discrete-distribution-generator (DDG) tree used to randomly sample items with specified weights. The FLDR algorithm operates on this object to maintain a size that scales linearly with the number of bits needed to encode the input distribution.

Traits

  • Sampling from the FLDR requires a fair coin, i.e. a random variable that outputs true or false with equal probability. This trait describes the interface for a fair coin, but lets the user choose the specifics of how to implement it.