Class ZipfDistribution.ZipfRejectionInversionSampler

  • Enclosing class:
    ZipfDistribution

    static final class ZipfDistribution.ZipfRejectionInversionSampler
    extends java.lang.Object
    Utility class implementing a rejection inversion sampling method for a discrete, bounded Zipf distribution that is based on the method described in

    Wolfgang Hörmann and Gerhard Derflinger "Rejection-inversion to generate variates from monotone discrete distributions." ACM Transactions on Modeling and Computer Simulation (TOMACS) 6.3 (1996): 169-184.

    The paper describes an algorithm for exponents larger than 1 (Algorithm ZRI). The original method uses H(x) := (v + x)^(1 - q) / (1 - q) as the integral of the hat function. This function is undefined for q = 1, which is the reason for the limitation of the exponent. If instead the integral function H(x) := ((v + x)^(1 - q) - 1) / (1 - q) is used, for which a meaningful limit exists for q = 1, the method works for all positive exponents.

    The following implementation uses v := 0 and generates integral numbers in the range [1, numberOfElements]. This is different to the original method where v is defined to be positive and numbers are taken from [0, i_max]. This explains why the implementation looks slightly different.

    Since:
    3.6
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double exponent
      Exponent parameter of the distribution.
      private double hIntegralNumberOfElements
      Constant equal to hIntegral(numberOfElements + 0.5).
      private double hIntegralX1
      Constant equal to hIntegral(1.5) - 1.
      private int numberOfElements
      Number of elements.
      private double s
      Constant equal to 2 - hIntegralInverse(hIntegral(2.5) - h(2).
    • Constructor Summary

      Constructors 
      Constructor Description
      ZipfRejectionInversionSampler​(int numberOfElements, double exponent)
      Simple constructor.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private double h​(double x)
      h(x) := 1/x^exponent
      (package private) static double helper1​(double x)
      Helper function that calculates log(1+x)/x.
      (package private) static double helper2​(double x)
      Helper function to calculate (exp(x)-1)/x.
      private double hIntegral​(double x)
      H(x) := (x^(1-exponent) - 1)/(1 - exponent), if exponent != 1 log(x), if exponent == 1 H(x) is an integral function of h(x), the derivative of H(x) is h(x).
      private double hIntegralInverse​(double x)
      The inverse function of H(x).
      (package private) int sample​(RandomGenerator random)
      Generate one integral number in the range [1, numberOfElements].
      • Methods inherited from class java.lang.Object

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

      • exponent

        private final double exponent
        Exponent parameter of the distribution.
      • numberOfElements

        private final int numberOfElements
        Number of elements.
      • hIntegralX1

        private final double hIntegralX1
        Constant equal to hIntegral(1.5) - 1.
      • hIntegralNumberOfElements

        private final double hIntegralNumberOfElements
        Constant equal to hIntegral(numberOfElements + 0.5).
      • s

        private final double s
        Constant equal to 2 - hIntegralInverse(hIntegral(2.5) - h(2).
    • Constructor Detail

      • ZipfRejectionInversionSampler

        ZipfRejectionInversionSampler​(int numberOfElements,
                                      double exponent)
        Simple constructor.
        Parameters:
        numberOfElements - number of elements
        exponent - exponent parameter of the distribution
    • Method Detail

      • sample

        int sample​(RandomGenerator random)
        Generate one integral number in the range [1, numberOfElements].
        Parameters:
        random - random generator to use
        Returns:
        generated integral number in the range [1, numberOfElements]
      • hIntegral

        private double hIntegral​(double x)
        H(x) :=
        • (x^(1-exponent) - 1)/(1 - exponent), if exponent != 1
        • log(x), if exponent == 1
        H(x) is an integral function of h(x), the derivative of H(x) is h(x).
        Parameters:
        x - free parameter
        Returns:
        H(x)
      • h

        private double h​(double x)
        h(x) := 1/x^exponent
        Parameters:
        x - free parameter
        Returns:
        h(x)
      • hIntegralInverse

        private double hIntegralInverse​(double x)
        The inverse function of H(x).
        Parameters:
        x - free parameter
        Returns:
        y for which H(y) = x
      • helper1

        static double helper1​(double x)
        Helper function that calculates log(1+x)/x.

        A Taylor series expansion is used, if x is close to 0.

        Parameters:
        x - a value larger than or equal to -1
        Returns:
        log(1+x)/x
      • helper2

        static double helper2​(double x)
        Helper function to calculate (exp(x)-1)/x.

        A Taylor series expansion is used, if x is close to 0.

        Parameters:
        x - free parameter
        Returns:
        (exp(x)-1)/x if x is non-zero, or 1 if x=0