Class AliasMethodSampler


  • public class AliasMethodSampler
    extends java.lang.Object
    The alias method for sampling from a discrete probability distribution.

    The implementation is described in the paper: Michael D. Vose. A Linear Algorithm for Generating Random Numbers with a Given Distribution. IEEE Transactions on Software Engineering, 17(9):972--975, 1991.

    Initialization takes $O(n)$ where $n$ is the number of items. Sampling takes $O(1)$.

    Author:
    Dimitrios Michail
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int next()
      Sample a value from the distribution.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • AliasMethodSampler

        public AliasMethodSampler​(double[] p)
        Constructor
        Parameters:
        p - the probability distribution where position i of the array is $Prob(X=i)$
        Throws:
        java.lang.IllegalArgumentException - in case of a non-valid probability distribution
      • AliasMethodSampler

        public AliasMethodSampler​(double[] p,
                                  long seed)
        Constructor
        Parameters:
        p - the probability distribution where position $i$ of the array is $Prob(X=i)$
        seed - seed to use for the random number generator
      • AliasMethodSampler

        public AliasMethodSampler​(double[] p,
                                  java.util.Random rng)
        Constructor
        Parameters:
        p - the probability distribution where position $i$ of the array is $Prob(X=i)$
        rng - the random number generator
        Throws:
        java.lang.IllegalArgumentException - in case of a non-valid probability distribution
      • AliasMethodSampler

        public AliasMethodSampler​(double[] p,
                                  java.util.Random rng,
                                  double epsilon)
        Constructor
        Parameters:
        p - the probability distribution where position $i$ of the array is $Prob(X=i)$
        rng - the random number generator
        epsilon - tolerance used when comparing floating-point values
        Throws:
        java.lang.IllegalArgumentException - in case of a non-valid probability distribution
    • Method Detail

      • next

        public int next()
        Sample a value from the distribution.
        Returns:
        a sample from the distribution