[RNG-69] GeometricSampler

• Type: New Feature
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.3
• Fix Version/s: 1.3
• Component/s: sampling
• Labels: Performance
• Assignee: Alex Herbert
• Reporter: Alex Herbert
• Created: 28/Jan/19 15:32
• Updated: 11/Nov/19 14:25
• Resolved: 05/Nov/19 15:13

Description

Sampling from a Geometric distribution is currently implemented using the InverseTransformDiscreteSampler.

This samples using the inverse cumulative probability function of the Geometric distribution and effectively computes:

// p = probability of success
// precompute
double log1mProbabilityOfSuccess = FastMath.log1p(-p);

// To sample
double u = rng.nextDouble();
Math.max(0, (int) Math.ceil(Math.log1p(-u)/log1mProbabilityOfSuccess-1));

Thus there is a call to Math.log1p for every sample.

It is possible to sample from a Geometric using a related underlying exponential sampler:

Geometric distribution - related distributions

Here the probability of success (p) is converted into a mean for an exponential distribution:

// Use a related exponential distribution:
// λ = −ln(1 − probabilityOfSuccess)
// exponential mean = 1 / λ
final double exponentialMean = 1.0 / (-Math.log1p(-probabilityOfSuccess));
exponentialSampler = new AhrensDieterExponentialSampler(rng, exponentialMean);

// To sample return the floor of the exponential sample
return (int) Math.floor(exponentialSampler.sample());

The AhrensDieterExponentialSampler has been optimised to avoid calling Math.log. It only uses nextDouble. Using this method a geometric sampler can be created that outperforms the inverse sampling method.

I have created a test version of this method. It passes the test for the Geometric distribution when added to the DiscreteSamplersList in the test suite. Here is a performance result using JMH:

Success probability	RNG	Method	Score	Error	Relative Speed
0.1	JDK	GeometricInverseTranformSampler	786086.7	22427.75	1.00
0.1	JDK	GeometricSampler	511206.08	38722.29	0.65
0.1	MWC_256	GeometricInverseTranformSampler	656838.86	3501.26	1.00
0.1	MWC_256	GeometricSampler	358833.81	121652.51	0.55
0.1	SPLIT_MIX_64	GeometricInverseTranformSampler	602642.45	4192.85	1.00
0.1	SPLIT_MIX_64	GeometricSampler	289775.51	7279.83	0.48
0.3	JDK	GeometricInverseTranformSampler	776525.54	3286.05	1.00
0.3	JDK	GeometricSampler	524565.79	39613.82	0.68
0.3	MWC_256	GeometricInverseTranformSampler	638300.02	4217.91	1.00
0.3	MWC_256	GeometricSampler	344942.66	2493.33	0.54
0.3	SPLIT_MIX_64	GeometricInverseTranformSampler	600476.53	10686.48	1.00
0.3	SPLIT_MIX_64	GeometricSampler	300886.79	6718.99	0.50

Performance is roughly half (1/2) the run-time for a fast RNG (SPLIT_MIX_64) and 2/3 the runtime for a slow RNG (JDK).

 

Issue Links

• links to: GitHub Pull Request #19