Class GuideTableDiscreteSampler

java.lang.Object
org.apache.commons.rng.sampling.distribution.GuideTableDiscreteSampler
All Implemented Interfaces:
DiscreteSampler, SharedStateDiscreteSampler, SharedStateSampler<SharedStateDiscreteSampler>
public final class GuideTableDiscreteSampler extends Object implements SharedStateDiscreteSampler
Compute a sample from n values each with an associated probability. If all unique items are assigned the same probability it is more efficient to use the DiscreteUniformSampler.

The cumulative probability distribution is searched using a guide table to set an initial start point. This implementation is based on:

Devroye, Luc (1986). Non-Uniform Random Variate Generation. New York: Springer-Verlag. Chapter 3.2.4 "The method of guide tables" p. 96.

The size of the guide table can be controlled using a parameter. A larger guide table will improve performance at the cost of storage space.

Sampling uses UniformRandomProvider.nextDouble().

Since:
1.3
See Also:

  • Field Details

    • DEFAULT_ALPHA

      private static final double DEFAULT_ALPHA
      The default value for alpha.
      See Also:

    • rng

      private final UniformRandomProvider rng
      Underlying source of randomness.

    • cumulativeProbabilities

      private final double[] cumulativeProbabilities
      The cumulative probability table (f(x)).

    • guideTable

      private final int[] guideTable
      The inverse cumulative probability guide table. This is a guide map between the cumulative probability (f(x)) and the value x. It is used to set the initial point for search of the cumulative probability table.

      The index in the map is obtained using p * map.length where p is the known cumulative probability f(x) or a uniform random deviate u. The value stored at the index is value x+1 when p = f(x) such that it is the exclusive upper bound on the sample value x for searching the cumulative probability table f(x). The search of the cumulative probability is towards zero.

  • Constructor Details

    • GuideTableDiscreteSampler

      private GuideTableDiscreteSampler(UniformRandomProvider rng, double[] cumulativeProbabilities, int[] guideTable)
      Parameters:
      rng - Generator of uniformly distributed random numbers.
      cumulativeProbabilities - The cumulative probability table (f(x)).
      guideTable - The inverse cumulative probability guide table.

  • Method Details

    • sample

      public int sample()
      Creates an int sample.
      Specified by:
      sample in interface DiscreteSampler
      Returns:
      a sample.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • withUniformRandomProvider

      public SharedStateDiscreteSampler withUniformRandomProvider(UniformRandomProvider rng)
      Create a new instance of the sampler with the same underlying state using the given uniform random provider as the source of randomness.
      Specified by:
      withUniformRandomProvider in interface SharedStateSampler<SharedStateDiscreteSampler>
      Parameters:
      rng - Generator of uniformly distributed random numbers.
      Returns:
      the sampler

    • of

      public static SharedStateDiscreteSampler of(UniformRandomProvider rng, double[] probabilities)
      Create a new sampler for an enumerated distribution using the given probabilities. The samples corresponding to each probability are assumed to be a natural sequence starting at zero.

      The size of the guide table is probabilities.length.

      Parameters:
      rng - Generator of uniformly distributed random numbers.
      probabilities - The probabilities.
      Returns:
      the sampler
      Throws:
      IllegalArgumentException - if probabilities is null or empty, a probability is negative, infinite or NaN, or the sum of all probabilities is not strictly positive.

    • of

      public static SharedStateDiscreteSampler of(UniformRandomProvider rng, double[] probabilities, double alpha)
      Create a new sampler for an enumerated distribution using the given probabilities. The samples corresponding to each probability are assumed to be a natural sequence starting at zero.

      The size of the guide table is alpha * probabilities.length.

      Parameters:
      rng - Generator of uniformly distributed random numbers.
      probabilities - The probabilities.
      alpha - The alpha factor used to set the guide table size.
      Returns:
      the sampler
      Throws:
      IllegalArgumentException - if probabilities is null or empty, a probability is negative, infinite or NaN, the sum of all probabilities is not strictly positive, or alpha is not strictly positive.

    • validateParameters

      private static void validateParameters(double[] probabilities, double alpha)
      Validate the parameters.
      Parameters:
      probabilities - The probabilities.
      alpha - The alpha factor used to set the guide table size.
      Throws:
      IllegalArgumentException - if probabilities is null or empty, or alpha is not strictly positive.

    • getGuideTableIndex

      private static int getGuideTableIndex(double p, int tableLength)
      Gets the guide table index for the probability. This is obtained using p * (tableLength - 1) so is inside the length of the table.
      Parameters:
      p - Cumulative probability.
      tableLength - Table length.
      Returns:
      the guide table index.