Discrete Uniform Transform¹

Introduction

Transform units serve two functions. Their primary function is to adapt the output from a driver unit to whaterver range is appropriate to a specific application. Their secondary function is to influence how values concentrate within various regions of the application range. The DiscreteUniform transform is what you want when range-adaptation is the sole concern, and when you're content to allow whatever distribution the driver values already have to pass through just being rescaled and truncated to the next lower integer.

The range of values output by DiscreteUniform.convert() is controlled by one parameter implemented as a Java field, itemCount, a positive integer.

The convert() method maps a value x in the driver domain from zero to unity into a value v in the application range from zero to itemCount-1 using the truncating formula:

Profile

Figure 1 illustrates the influence which DiscreteUniform.convert() exerts over driver sequences. The vertical v axis shows the application range when itemCount = 10, which is the succession of integers from 0 to 9. The horizontal k axis shows the sample values v_k which have been obtained from driver values x_k using the convert(). All three source sequences are nominally uniform. Each left-side sample graph presents 200 values; the right-side histogram presents a sidewise bar for each range value. Ideally, this would result in 20 samples per range value, but this happens exactly only in the bottom row of graphs.

Figure 1: Panel of DiscreteUniform output from three different Driver sources. Each row of graphs provides a time-series graph of samples (left) and a histogram analyzed from the same samples (right). The first row of graphs was generated using the standard random number generator. The second row was generated using the balanced-bit generator. The third row was generated using an ascending sequence of driver values, equally spaced from zero to unity.

The source sequences used to create Figure 1 are the same sequences used to create the profile panel for ContinuousUniform, which passes through its driver values undecorated. You can view the actual source sequences by clicking the link. All three source sequences are nominally uniform. The first source is standard randomness from Lehmer. The second source is balanced-bit values from Balance. The third source is an ascending succession produced using DriverSequence.

For each graph in Figure 1 the average sample value is plotted as a dashed green line, while the interval between ± one standard deviation around the average is filled in with a lighter green background.

For the standard random number generator's (top row of Figure 1), uniformity manifests only over the long term; the source generator's concern for the independence of consecutive samples works against short-term uniformity. The standard-randomness histogram appearing on the right of the top row is hardly uniform, though the distance from the vertical v axis to the smallest f(v) value is about the same as the distance from the smallest f(v) value from the largest f(v) value. Besides, no other distribution suggests itself.

The balanced-bit generator (middle row of Figure 1) actively strives for uniformity over the short term. The balanced-bit histogram appearing in Figure 1 has a quarter the horizontal distance from the smallest f(v) value to the largest f(v) value.

There is no surer way of obtaining uniform driver values than to calculate an increment Δx = 1/N, where N is the number of samples. The first sample value x₀ is set to Δx/2; subsequent values are calculated as x_k = x_k-1 + Δx until x_k threatens to exceed unity. With driver values generated in this manner, the graphs of samples (bottom row of Figure 1) come to resemble two essential functions describing the Transform unit's underlying statistical distribution: The time-series graph of samples comes to resemble the distribution's quantile function; for a discrete uniform distribution this is an ascending step function, where the run of each step indicates a fixed probability density and the rise is fixed at one unit. The histogram of sample values comes to resemble the distribution's probability density function, which for a discrete uniform distribution is a succession of equal-length bars.

For the ideally uniform driver values plotted in the third row of graphs, the average sample value is 4.5 and the standard deviation is 2.872. The interval from 4.5-2.872 to 4.5+2.872 is 2*2.872/9 = 0.64 = 64% of the full application range from 0 to 9; since sequence is uniform and the transform passes this uniformity along, we can assert that 64% of samples fall within the green-shaded part of the graph.

/**
 * The {@link DiscreteUniform} class implements a {@link Transform}
 * which adapts the driver range of real numbers from zero to unity to
 * an application range of integers from 0 (inclusive) to {@link itemCount}
 * (not inclusive).  Whatever distribution characterizes the driver values
 * passes through except for being scaled to the range bounds, then
 * truncated to the next lower integer.
 * @author Charles Ames
 */
public class DiscreteUniform
extends TransformBase<Integer> implements Transform.Discrete {
   /**
    * The number of values.
    */
   private int itemCount;
   /**
    * Constructor for {@link DiscreteUniform} instances.
    * @param container An entity which contains this transform.
    */
   public DiscreteUniform(WriteableEntity container) {
      super(container);
      itemCount = Integer.MIN_VALUE;
   }
   /**
    * Getter for {@link #itemCount}.
    * @return The assigned {@link #itemCount} value.
    */
   public int itemCount() {
      if (Integer.MIN_VALUE == itemCount)
         throw new UninitializedException("Item count not initialized");
      return itemCount;
   }
   /**
    * Setter for {@link #itemCount}.
    * @param itemCount The intended {@link #itemCount} value.
    */
   public void setItemCount(int itemCount) {
      checkItemCount(itemCount);
      this.itemCount = itemCount;
   }
   /**
    * Check if the indicated value is suitable for {@link #itemCount}.
    * @param itemCount The indicated value.
    */
   public void checkItemCount(int itemCount) {
      if (0 >= itemCount)
         throw new IllegalArgumentException("Invalid itemCount: " + itemCount);
   }
   @Override
   public Integer minGraphValue(double tail) {
      return minRange();
   }
   @Override
   public Integer maxGraphValue(double tail) {
      return maxRange();
   }
   @Override
   public double minGraphValue() {
      return minRange();
   }
   @Override
   public double maxGraphValue() {
      return maxRange();
   }
   @Override
   public Integer minRange() {
      return 0;
   }
   @Override
   public Integer maxRange() {
      return itemCount - 1;
   }
   @Override
   public Integer convert(double driver) {
      Driver.checkDriverValue(driver);
      int index = (int) Math.floor(driver * itemCount);
      return index;
   }
}

Comments

1. The present text is adapted from my Leonardo Music Journal article from 1991, "A Catalog of Statistical Distributions". The heading is "Discrete Uniform", p. 58.