Package org.jgrapht.alg.util

Class AliasMethodSampler

java.lang.Object

org.jgrapht.alg.util.AliasMethodSampler

public class AliasMethodSampler
extends Object

The alias method for sampling from a discrete probability distribution.

The implementation is described in the paper: Michael D. Vose. A Linear Algorithm for Generating Random Numbers with a Given Distribution. IEEE Transactions on Software Engineering, 17(9):972--975, 1991.

Initialization takes $O(n)$ where $n$ is the number of items. Sampling takes $O(1)$.

Author:

Dimitrios Michail

Constructor Summary

Constructors

Constructor	Description
AliasMethodSampler(double[] p)	Constructor
AliasMethodSampler(double[] p, long seed)	Constructor
AliasMethodSampler(double[] p, Random rng)	Constructor
AliasMethodSampler(double[] p, Random rng, double epsilon)	Constructor

Method Summary

Modifier and Type	Method	Description
int	next()	Sample a value from the distribution.

Methods inherited from class java.lang.Object

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

Constructor Detail

AliasMethodSampler

public AliasMethodSampler(double[] p)

Constructor

Parameters:

p - the probability distribution where position i of the array is $Prob(X=i)$

Throws:

IllegalArgumentException - in case of a non-valid probability distribution

AliasMethodSampler

public AliasMethodSampler(double[] p,
                          long seed)

Constructor

Parameters:

p - the probability distribution where position $i$ of the array is $Prob(X=i)$

seed - seed to use for the random number generator

AliasMethodSampler

public AliasMethodSampler(double[] p,
                          Random rng)

Constructor

Parameters:

p - the probability distribution where position $i$ of the array is $Prob(X=i)$

rng - the random number generator

Throws:

IllegalArgumentException - in case of a non-valid probability distribution

AliasMethodSampler

public AliasMethodSampler(double[] p,
                          Random rng,
                          double epsilon)

Constructor

Parameters:

p - the probability distribution where position $i$ of the array is $Prob(X=i)$

rng - the random number generator

epsilon - tolerance used when comparing floating-point values

Throws:

IllegalArgumentException - in case of a non-valid probability distribution

Method Detail

next

public int next()

Sample a value from the distribution.

Returns:

a sample from the distribution