Uploaded image for project: 'Commons RNG'
  1. Commons RNG
  2. RNG-100

GuideTableDiscreteSampler

    XMLWordPrintableJSON

Details

    • New Feature
    • Status: Closed
    • Minor
    • Resolution: Implemented
    • 1.3
    • 1.3
    • sampling
    • None

    Description

      From

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

      Chapter 3 from the author's website.

      The method divides the range for the cumulative probability table of K values into alpha * K equispaced intervals. Each interval i contains the maximum sample value where the cumulative probability is less than i / table.length.

      Given a uniform deviate u in the range [0, 1] the guide can be obtained using floor(u * table.length). This guide value is the start point for search of the cumulative probability table. The number of comparisons of the uniform deviate within the cumulative probability table is upper bounded by 2 (see Devroye, p97) making the search very efficient.

      Create a sampler using the Guide table method:

      package org.apache.commons.rng.sampling.distribution;
      
      public class GuideTableDiscreteSampler implements DiscreteSampler {
          public GuideTableDiscreteSampler(UniformRandomProvider rng, 
                                           double[] probabilities,
                                           double alpha) {
              // Validate probabilities sum to >0
              // Construct cumulative probability table
              // Construct guide table
          }
      
          @Override
          public int sample() {
              // Look-up sample value in guide table
              // Search cumulative probability table
          }
      }
      

      The alpha value is not required. However large alpha increase the size of the guide table and improve performance at the cost of storage.

      Attachments

        Issue Links

          Activity

            People

              aherbert Alex Herbert
              aherbert Alex Herbert
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 20m
                  20m