Package org.evoludo.math

Class RNGDistribution.Gillespie

Object

RNGDistribution

Gillespie

Enclosing class:

RNGDistribution

public static class RNGDistribution.Gillespie
extends RNGDistribution

Gillespie algorithm for selecting integers with support {0,1,2,3,..., n} but with different weights.

Note: if multiple random number are drawn using the same distribution of weights, optimizations are posssible that require expensive initialization but then drawing the random number is significantly cheaper.

For an excellent overview, see Keith Schwarz' website Darts, Dice, and Coins: Sampling from a Discrete Distribution. Of particular interest is Vose's Alias Method, which is also what's implemented in NetLogo

See Also:

• Wikipedia: Gillespie algorithm

Nested Class Summary

Nested classes/interfaces inherited from class RNGDistribution

RNGDistribution.Binomial, RNGDistribution.Exponential, RNGDistribution.Geometric, RNGDistribution.Gillespie, RNGDistribution.Normal, RNGDistribution.TestCommand, RNGDistribution.Uniform

Field Summary

Fields

Modifier and Type	Field	Description
static final int	THRESHOLD_SIZE	The threshold for switching between the standard and the optimized version of the Gillespie algorithm.

Fields inherited from class RNGDistribution

rng, seed, seedSet, testSamples

Constructor Summary

Constructors

Constructor	Description
Gillespie()	Creates a weighted distribution over intergers using the Gillespie algorithm and a new instance of MersenneTwister.
Gillespie(MersenneTwister rng)	Creates a weighted distribution over intergers using the Gillespie algorithm using the random number generator rng.

Method Summary

Modifier and Type	Method	Description
RNGDistribution.Gillespie	clone()	Clone this RNGDistribution to ensure both objects return identical sequences of random numbers.
int	next(double[] weights)	Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.
int	next(int[] weights)	Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.
int	nextMax(double[] weights, double max)	Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.
int	nextMax(int[] weights, int max)	Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.
int	nextSum(double[] weights, double sum)	Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.
int	nextSum(int[] weights, int sum)	Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.
static void	test(MersenneTwister rng, Logger logger, MersenneTwister.Chronometer clock)	Test Gillespie algorithm for random weight distribution.

Methods inherited from class RNGDistribution

clearRNGSeed, clone, getRNG, getRNGSeed, isRNGSeedSet, nextBoolean, nextByte, nextBytes, nextDouble, nextGaussian, nextInt, nextInt, random01, random01d, random0n, random0N, setRNG, setRNGSeed, setRNGSeed

Methods inherited from class Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

THRESHOLD_SIZE

public static final int THRESHOLD_SIZE

The threshold for switching between the standard and the optimized version of the Gillespie algorithm.

See Also:

• Constant Field Values

Constructor Details

Gillespie

public Gillespie()

Creates a weighted distribution over intergers using the Gillespie algorithm and a new instance of MersenneTwister.

Gillespie

public Gillespie(MersenneTwister rng)
          throws IllegalArgumentException

Creates a weighted distribution over intergers using the Gillespie algorithm using the random number generator rng.

Parameters:

rng - random number generator

Throws:

IllegalArgumentException

Method Details

next

public int next(int[] weights)

Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights.

Note: if the sum of weights or the maximum weight is known, consider using the methods #nextSum(double[], double) or #nextMax(double[], double), instead.

Parameters:

weights - the array of weights of the discrete distribution

Returns:

the random integer

nextSum

public int nextSum(int[] weights,
 int sum)

Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights. Given the sum of weights sum the Gillespie algorithm picks a uniformly distributed random number in [0, sum) and then walks through the array of weights until the cumulative sum exceeds the random number. The index of the weight that exceeds the random number is returned.

Note: this is the standard, non-optimized version of the Gillespie algorithm and is most likely best for small supports.

Parameters:

weights - the array of weights of the discrete distribution

sum - the sum of all weights

Returns:

the random integer

nextMax

public int nextMax(int[] weights,
 int max)

Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights. Given the maximum weight max, the drawing of weighted random numbers can be optmized by simplifying bookkeeping at the expense of drawing more random numbers.

Notes:

1. The optimization is most effective for large supports but can be hampered by heavily skewed weight distributions.
2. For small supports the standard version of the Gillespie algorithm is likely faster.
3. For skewed weights consider sorting the weights in descending order.
4. max can be bigger than the actual maximum but the optimization becomes less efficient.

Parameters:

weights - the array of weights of the discrete distribution

max - the maximum weight in the array

Returns:

the random integer

See Also:

• Lipowski, A. & Lipowska, D. (2011) Roulette-wheel selection via stochastic acceptance

next

public int next(double[] weights)

Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights. Optimized sampling is used above the threshold of weights.length > 350.

Note: if the sum of weights or the maximum weight is known, consider using the methods #nextSum(double[], double) or #nextMax(double[], double), instead.

Parameters:

weights - the array of weights of the discrete distribution

Returns:

the random integer

nextSum

public int nextSum(double[] weights,
 double sum)

Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights. Given the sum of weights sum the Gillespie algorithm picks a uniformly distributed random number in [0, sum) and then walks through the array of weights until the cumulative sum exceeds the random number. The index of the weight that exceeds the random number is returned.

Note: this is the standard, non-optimized version of the Gillespie algorithm and is most likely best for small supports.

Parameters:

weights - the array of weights of the discrete distribution

sum - the sum of all weights

Returns:

the random integer

nextMax

public int nextMax(double[] weights,
 double max)

Return a random integer with support [0, weights.length) from the discrete distribution of weights defined by the double[] array weights. Given the maximum weight max, the drawing of weighted random numbers can be optmized by simplifying bookkeeping at the expense of drawing more random numbers.

Notes:

1. The optimization is most effective for large supports but can be hampered by heavily skewed weight distributions.
2. For small supports the standard version of the Gillespie algorithm is likely faster. The threshold appears to be at around 350 elements.
3. For skewed weights consider sorting the weights in descending order.
4. max can be bigger than the actual maximum but the optimization becomes less efficient.

Parameters:

weights - the array of weights of the discrete distribution

max - the maximum weight in the array

Returns:

the random integer

See Also:

• Lipowski, A. & Lipowska, D. (2011) Roulette-wheel selection via stochastic acceptance

clone

public RNGDistribution.Gillespie clone()

Description copied from class: RNGDistribution

Clone this RNGDistribution to ensure both objects return identical sequences of random numbers.

IMPORTANT:

1. overrides clone() in Object but conflicts with GWT's aversion to clone()ing...
2. remove @SuppressWarnings("all") to ensure that no other issues crept in when modifying method.

Specified by:

clone in class RNGDistribution

Returns:

clone of RNGDistribution

test

public static void test(MersenneTwister rng,
 Logger logger,
 MersenneTwister.Chronometer clock)

Test Gillespie algorithm for random weight distribution.

The test samples the distribution and bins the random numbers. This sample distribution is compared to the theoretical expectation. The mean deviation is the mean difference between the actual number of events in each bin and their expected number. For a perfect match the mean deviation is 0. The test passes if the mean deviation lies within one standard error from 0. This is more stringent than the traditional 95% confidence interval.

Parameters:

rng - the random number generator

logger - the logger for reporting results

clock - the stop watch