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)$.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int[] alias  
      private java.util.Comparator<java.lang.Double> comparator  
      private double[] prob  
      private java.util.Random rng  
    • 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
    • Field Detail

      • rng

        private final java.util.Random rng
      • comparator

        private java.util.Comparator<java.lang.Double> comparator
      • prob

        private final double[] prob
      • alias

        private final int[] alias
    • 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