Walker-Sample
Small node.js library for sampling discrete probability distribution using the Walker alias method in O(1) time.
Install
$ npm install walker-sample
Usage
The top level export of walker-sample
is a function that constructs a table to allow O(1) sampling:
const walker = ; // Create table with weightsconst sampler = ;
The function takes a list of weight, value pairs. The weights must be greater than zero and positive, but the weights themselves can be any integer or floating point value. Passing in a weight less than or equal to zero throws an exception.
The table above will produces 'a'
10% of the time, 'b'
30%, 'c'
20%, and 'd'
40% of the time. Weights are relative, so we get the same behavior with:
const sampler = ;
or with:
const sampler = ;
Sampling
sampler
is just a function that can be sampled in O(1) time:
sampler() === 'd';
The default behavior uses Math.random
for sampling. The sample function can also take a custom random number generator if predictable samples are needed. This is useful for testing.
const r = 05; === 'a'; === 'a';...// still 'a' === 'a';
If you want to use the same random number generator for all samples, use .bind
const biasedSampler = sampler; === 'a';
The random number generator must be a function that takes no arguments and produces a number between [0, 1]. This random number generator will be invoked twice for each sample.