Ndrand NPM | npm.io

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 $\left\{x_{n-1},y_{n-1}\right\}$ and $\left\{x_n,y_n\right\}$ form a trapezoid like so.

trapezoid

Where the height of two sides are $y_{n-1}$ and $y_n$ respectively and the width is $x_n-x_{n-1}$

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

$A=\left(\frac{y_{n-1}+y_n}{2}\right)\left(x_n-x_{n-1}\right)$

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 $x_{pa}$ 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 $\left\{x_{n-1},y_{n-1}\right\}$ and $\left\{x_n,y_n\right\}$ where the cumDist of $\left\{x_{n-1},y_{n-1}\right\}$ is less than udr and the cumDist of $\left\{x_n,y_n\right\}$ 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 $\left\{x_{n-1},y_{n-1}\right\}$ pair to obtain the $A_{pa}$ . This is the area of the trapezoid formed by the pairs $\left\{x_{n-1},y_{n-1}\right\}$ and $\left\{x_{pa},y_{pa}\right\}$ in the figure below.

partial trapezoid

Given $A_{pa}$ we can calculate $x_{pv}$ using the the previous equation for the area of a trapezoid like so.

$A_{pa}=\left(\frac{y_{n-1}+y_{pa}}{2}\right)\left(x_{pa}-x_{n-1}\right)$ where $y_{pa}=\left(\frac{y_n-y_{n-1}}{x_n-x_{n-1}}\right)\left(x_{pa}-x_{n-1}\right)+y_{n-1}$

substituting $m=\left(\frac{y_n-y_{n-1}}{x_n-x_{n-1}}\right)$ we can simplify this as

$A_{pa}=\left(\frac{y_{n-1}+\left(m\left(x_{pa}-x_{n-1}\right)+y_{n-1}\right)}{2}\right)\left(x_{pa}-x_{n-1}\right)$

$A_{pa}=\left(\frac{m}{2}x_{pa}-\frac{m}{2}x_{n-1}+y_{n-1}\right)\left(x_{pa}-x_{n-1}\right)$

$A_{pa}=\frac{m}{2}x_{pa}^2-mx_{n-1}x_{pa}+y_{n-1}x_{pa}+\frac{m}{2}x_{n-1}^2-y_{n-1}x_{n-1}$

$0=\frac{m}{2}x_{pa}^2+\left(y_{n-1}-mx_{n-1}\right)x_{pa}+\left(\frac{m}{2}x_{n-1}^2-y_{n-1}x_{n-1}-A_{pa}\right)$

which is a quadratic equation of the form

$0=ax^2+bx+c$

where

$a=\frac{m}{2}$

$b=y_{n-1}-mx_{n-1}$

$c=\frac{m}{2}x_{n-1}^2-y_{n-1}x_{n-1}-A_{pa}$

thus we can solve for $x_{pa}$ using the quadratic equation

$x_{pa}=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$

The term $\frac{-b}{2a}$ is called the axis of symetry (aos) whereas $\frac{\sqrt{b^2-4ac}}{2a}$ 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 $x_{n-1}$ and $x_n$

random nonuniform distribution

@everything-registry/sub-chunk-2252

1.0.0

7 years ago