ndrand

A class used to generate a nonuniform distribution of random numbers.

Usage

var ndr = require('ndrand');

ndr.initialize([
  {x:0,y:0},
  {x:5,y:5},
  {x:10,y:0},
]);

console.log(ndr.random());

Algorithm Initialization

The user initializes the class with an array of x,y pairs describing the desired distribution. Two consecutive pairs and form a trapezoid like so.

Where the height of two sides are and respectively and the width is

The area of the trapeziod is the average of the two heights multiplied by the width and can be written like so.

During initialization, we calculate the area of each trapezoid to obtain the total area of the distribution. Along the way we record the cumulative area (cumArea) at each pair. This represents the area of all trapezoids to the left of the current pair. As such, the cumulative area of the first pair is 0 and the cumulative area of the last pair is the total area of the distribution.

We then go back and using the cumulative area of each pair and total area previously computed, calculate the cumulative distribution (cumDist) of each pair. The distribution represents the percentage of numbers in the distribution to the left of the current pair. Consequently, the cumulative distribution of the first pair is 0 and the cumulative distribution of the last pair is 1.0

Generation Algorithm

Given a uniform distributed random (udr) number from 0-1 we treat this as a percentage of the overall area of the nonuniform distribution curve (ndc) and try to find the value where the ratio of the area of the ndc to left to the total area exactly matches the udr.

We do this by first determining which trapezoid that contains the area we are looking for. This will be the trapezoid formed by the consecutive pairs and where the cumDist of is less than udr and the cumDist of is greater than udr. From there we calculate the target volume by multiplying the udr by the cumArea of the last pair in the ndc and then subtract the cumArea of the pair to obtain the . This is the area of the trapezoid formed by the pairs and in the figure below.

Given we can calculate using the the previous equation for the area of a trapezoid like so.

where

substituting we can simplify this as

which is a quadratic equation of the form

where

thus we can solve for using the quadratic equation

The term is called the axis of symetry (aos) whereas represents the distance (distance) from the aos

The algorithm will add or subtract the distance form the aos to find the value that falls between and