This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
The following commit(s) were added to refs/heads/master by this push:
new 8abfa517 RNG-196: Introduce default alpha to exclude unobservable
categories
8abfa517 is described below
commit 8abfa51735d6d4371e6c65f63a568cfa63f1b6d5
Author: Alex Herbert <[email protected]>
AuthorDate: Sat Aug 22 09:53:48 2026 +0100
RNG-196: Introduce default alpha to exclude unobservable categories
---
.../FastLoadedDiceRollerDiscreteSampler.java | 31 ++++++++++++++++++----
.../FastLoadedDiceRollerDiscreteSamplerTest.java | 23 ++++++++++++++--
src/changes/changes.xml | 7 +++++
3 files changed, 54 insertions(+), 7 deletions(-)
diff --git
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSampler.java
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSampler.java
index 474a307e..ffeca8ae 100644
---
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSampler.java
+++
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSampler.java
@@ -83,6 +83,16 @@ public abstract class FastLoadedDiceRollerDiscreteSampler
private static final int NO_LABEL = Integer.MAX_VALUE;
/** Name of the sampler. */
private static final String SAMPLER_NAME = "Fast Loaded Dice Roller";
+ /**
+ * Default relative magnitude cutoff (alpha) applied when creating a
sampler from
+ * {@code double} weights. Any weight approximately 2<sup>53</sup> smaller
than the
+ * largest weight is set to zero. This bounds the size of the discrete
distribution
+ * generating (DDG) tree by a function of the number of categories rather
than the
+ * dynamic range of the weights. Categories excluded by this cutoff have a
sampling
+ * probability below 2<sup>-53</sup> (approximately 1e-16) relative to the
most
+ * frequent category.
+ */
+ private static final int DEFAULT_ALPHA = 53;
/**
* Class to handle the edge case of observations in only one category.
@@ -299,9 +309,19 @@ public abstract class FastLoadedDiceRollerDiscreteSampler
* <p>Weights are converted to rational numbers {@code p / q} where {@code
q} is a power of 2.
* The numerators {@code p} are scaled to use a common denominator before
summing.
*
- * <p>All weights are used to create the sampler. Weights with a small
magnitude relative
- * to the largest weight can be excluded using the constructor method with
the
- * relative magnitude parameter {@code alpha} (see {@link
#of(UniformRandomProvider, double[], int)}).
+ * <p>Weights with a small magnitude relative to the largest weight are
excluded using
+ * a default relative magnitude parameter {@code alpha} of 53: any weight
+ * approximately 2<sup>53</sup> smaller than the largest weight is set to
zero.
+ * Categories excluded by this cutoff have a sampling probability below
+ * 2<sup>-53</sup> (approximately 1e-16) relative to the most frequent
category. The
+ * cutoff bounds the construction cost of the sampler by the number of
categories
+ * rather than the dynamic range of the weights. To create an
<em>exact</em> sampler
+ * from the full dynamic range of the weights use the constructor method
with a
+ * non-positive relative magnitude parameter {@code alpha} (see
+ * {@link #of(UniformRandomProvider, double[], int)}); note that the
construction cost
+ * is then a function of the ratio of the largest to the smallest non-zero
weight.
+ *
+ * <p>The default {@code alpha} of 53 was introduced in version 1.8.
*
* @param rng Generator of uniformly distributed random numbers.
* @param weights Weights of the discrete distribution.
@@ -313,7 +333,7 @@ public abstract class FastLoadedDiceRollerDiscreteSampler
*/
public static FastLoadedDiceRollerDiscreteSampler of(UniformRandomProvider
rng,
double[] weights) {
- return of(rng, weights, 0);
+ return of(rng, weights, DEFAULT_ALPHA);
}
/**
@@ -355,7 +375,8 @@ public abstract class FastLoadedDiceRollerDiscreteSampler
* <p><b>Implementation Note</b>
*
* <p>This method creates a sampler with <em>exact</em> samples from the
- * specified probability distribution. It is recommended to use this
method:
+ * specified probability distribution when {@code alpha} does not exclude
weights.
+ * It is recommended to use this method:
* <ul>
* <li>if the weights are computed, for example from a probability mass
function; or</li>
* <li>if the weights sum to an infinite value.</li>
diff --git
a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSamplerTest.java
b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSamplerTest.java
index 440dc30a..fd251388 100644
---
a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSamplerTest.java
+++
b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/FastLoadedDiceRollerDiscreteSamplerTest.java
@@ -46,7 +46,7 @@ class FastLoadedDiceRollerDiscreteSamplerTest {
}
/**
- * Creates the sampler.
+ * Creates the sampler using the default {@code alpha} parameter.
*
* @param weights Weights.
* @return the FLDR sampler
@@ -295,7 +295,9 @@ class FastLoadedDiceRollerDiscreteSamplerTest {
@ParameterizedTest
@MethodSource
void testSamplesWeights(double[] weights) {
- final SharedStateDiscreteSampler sampler = createSampler(weights);
+ // Must use alpha=0 to include all weights
+ final UniformRandomProvider rng = RandomAssert.createRNG();
+ final SharedStateDiscreteSampler sampler =
FastLoadedDiceRollerDiscreteSampler.of(rng, weights, 0);
final int numberOfSamples = 10000;
final long[] samples = new long[weights.length];
sampler.samples(numberOfSamples).forEach(x -> samples[x]++);
@@ -443,6 +445,23 @@ class FastLoadedDiceRollerDiscreteSamplerTest {
Assertions.assertFalse(Arrays.equals(s1, s3), "alpha+1 parameter
should not ignore the small weight");
}
+ /**
+ * Test the weights factory method applies a default relative magnitude
cutoff so
+ * that an extreme weight dynamic range does not amplify the construction
cost of
+ * the discrete distribution generating tree.
+ */
+ @Test
+ void testDefaultAlphaBoundsWeightDynamicRange() {
+ final double[] w1 = {1, 0.5, 0.5, 0};
+ final double[] w2 = {1, 0.5, 0.5, Double.MIN_VALUE};
+ final UniformRandomProvider[] rngs = RandomAssert.createRNG(2);
+ final UniformRandomProvider rng1 = rngs[0];
+ final UniformRandomProvider rng2 = rngs[1];
+ RandomAssert.assertProduceSameSequence(
+ FastLoadedDiceRollerDiscreteSampler.of(rng1, w1),
+ FastLoadedDiceRollerDiscreteSampler.of(rng2, w2));
+ }
+
static Stream<long[]> testSharedStateSampler() {
return Stream.of(
new long[] {42},
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index dc18e076..fb5ec0aa 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -56,6 +56,13 @@ If the output is not quite correct, check for invisible
trailing spaces!
<release version="1.8" date="TBD" description="
New features, updates and bug fixes (requires Java 8).
">
+ <action dev="aherbert" type="update" due-to="Security scan, Alex
Herbert" issue="RNG-196">
+ "FastLoadedDiceRollerDiscreteSampler": Introduce a defaut alpha to
exclude
+ practically unobservable categories with a probability of less than
2^-53
+ relative to the most frequent category. This is a behavioural change.
A full
+ discrete distribution generating (DDG) tree can be created using
alpha=0
+ in the overloaded factory constructor.
+ </action>
<action dev="aherbert" type="update" due-to="Security scan, Alex
Herbert">
"JDKRandom": Fail fast when restoring from a saved state if the
serialized bytes contains a proxy class descriptor.
