1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.rng.sampling.distribution;
18
19 import org.apache.commons.math3.distribution.BinomialDistribution;
20 import org.apache.commons.math3.distribution.PoissonDistribution;
21 import org.apache.commons.math3.stat.inference.ChiSquareTest;
22 import org.apache.commons.rng.UniformRandomProvider;
23 import org.apache.commons.rng.sampling.RandomAssert;
24 import org.apache.commons.rng.simple.RandomSource;
25 import org.junit.Assert;
26 import org.junit.Test;
27
28 import java.util.Arrays;
29
30
31
32
33 public class AliasMethodDiscreteSamplerTest {
34 @Test(expected = IllegalArgumentException.class)
35 public void testConstructorThrowsWithNullProbabilites() {
36 createSampler(null);
37 }
38
39 @Test(expected = IllegalArgumentException.class)
40 public void testConstructorThrowsWithZeroLengthProbabilites() {
41 createSampler(new double[0]);
42 }
43
44 @Test(expected = IllegalArgumentException.class)
45 public void testConstructorThrowsWithNegativeProbabilites() {
46 createSampler(new double[] {-1, 0.1, 0.2});
47 }
48
49 @Test(expected = IllegalArgumentException.class)
50 public void testConstructorThrowsWithNaNProbabilites() {
51 createSampler(new double[] {0.1, Double.NaN, 0.2});
52 }
53
54 @Test(expected = IllegalArgumentException.class)
55 public void testConstructorThrowsWithInfiniteProbabilites() {
56 createSampler(new double[] {0.1, Double.POSITIVE_INFINITY, 0.2});
57 }
58
59 @Test(expected = IllegalArgumentException.class)
60 public void testConstructorThrowsWithInfiniteSumProbabilites() {
61 createSampler(new double[] {Double.MAX_VALUE, Double.MAX_VALUE});
62 }
63
64 @Test(expected = IllegalArgumentException.class)
65 public void testConstructorThrowsWithZeroSumProbabilites() {
66 createSampler(new double[4]);
67 }
68
69 @Test
70 public void testToString() {
71 final SharedStateDiscreteSampler sampler = createSampler(new double[] {0.5, 0.5});
72 Assert.assertTrue(sampler.toString().toLowerCase().contains("alias method"));
73 }
74
75
76
77
78
79
80
81 private static SharedStateDiscreteSampler createSampler(double[] probabilities) {
82 final UniformRandomProvider rng = RandomSource.create(RandomSource.SPLIT_MIX_64);
83 return AliasMethodDiscreteSampler.of(rng, probabilities, -1);
84 }
85
86
87
88
89 @Test
90 public void testBinomialSamples() {
91 final int trials = 67;
92 final double probabilityOfSuccess = 0.345;
93 final BinomialDistribution dist = new BinomialDistribution(trials, probabilityOfSuccess);
94 final double[] expected = new double[trials + 1];
95 for (int i = 0; i < expected.length; i++) {
96 expected[i] = dist.probability(i);
97 }
98 checkSamples(expected);
99 }
100
101
102
103
104 @Test
105 public void testPoissonSamples() {
106 final double mean = 3.14;
107 final PoissonDistribution dist = new PoissonDistribution(null, mean,
108 PoissonDistribution.DEFAULT_EPSILON, PoissonDistribution.DEFAULT_MAX_ITERATIONS);
109 final int maxN = dist.inverseCumulativeProbability(1 - 1e-6);
110 double[] expected = new double[maxN];
111 for (int i = 0; i < expected.length; i++) {
112 expected[i] = dist.probability(i);
113 }
114 checkSamples(expected);
115 }
116
117
118
119
120 @Test
121 public void testNonUniformSamplesWithProbabilities() {
122 final double[] expected = {0.1, 0.2, 0.3, 0.1, 0.3 };
123 checkSamples(expected);
124 }
125
126
127
128
129
130 @Test
131 public void testNonUniformSamplesWithProbabilitiesWithDefaultFactoryConstructor() {
132 final double[] expected = {0.1, 0.2, 0.3, 0.1, 0.3 };
133 checkSamples(AliasMethodDiscreteSampler.of(RandomSource.create(RandomSource.SPLIT_MIX_64), expected), expected);
134 }
135
136
137
138
139
140 @Test
141 public void testNonUniformSamplesWithObservations() {
142 final double[] expected = {1, 2, 3, 1, 3 };
143 checkSamples(expected);
144 }
145
146
147
148
149
150 @Test
151 public void testNonUniformSamplesWithProbabilitiesPaddedToPowerOf2() {
152 final double[] expected = {0.1, 0, 0.2, 0.3, 0.1, 0.3, 0, 0 };
153 checkSamples(expected);
154 }
155
156
157
158
159
160 @Test
161 public void testNonUniformSamplesWithObservationsPaddedToPowerOf2() {
162 final double[] expected = {1, 2, 3, 0, 1, 3, 0, 0 };
163 checkSamples(expected);
164 }
165
166
167
168
169
170 @Test
171 public void testNonUniformSamplesWithZeroProbabilities() {
172 final double[] expected = {0.1, 0, 0.2, 0.3, 0.1, 0.3, 0 };
173 checkSamples(expected);
174 }
175
176
177
178
179
180 @Test
181 public void testNonUniformSamplesWithZeroObservations() {
182 final double[] expected = {1, 2, 3, 0, 1, 3, 0 };
183 checkSamples(expected);
184 }
185
186
187
188
189
190 @Test
191 public void testUniformSamplesWithNoObservationLessThanTheMean() {
192 final double[] expected = {2, 2, 2, 2, 2, 2 };
193 checkSamples(expected);
194 }
195
196
197
198
199 @Test
200 public void testLargeTableSize() {
201 double[] expected = {0.1, 0.2, 0.3, 0.1, 0.3 };
202
203 expected = Arrays.copyOf(expected, 1 << 12);
204 checkSamples(expected);
205 }
206
207
208
209
210
211
212 private static void checkSamples(double[] probabilies) {
213 checkSamples(createSampler(probabilies), probabilies);
214 }
215
216
217
218
219
220
221 private static void checkSamples(SharedStateDiscreteSampler sampler, double[] probabilies) {
222 final int numberOfSamples = 10000;
223 final long[] samples = new long[probabilies.length];
224 for (int i = 0; i < numberOfSamples; i++) {
225 samples[sampler.sample()]++;
226 }
227
228
229 int mapSize = 0;
230 for (int i = 0; i < probabilies.length; i++) {
231 if (probabilies[i] != 0) {
232 mapSize++;
233 }
234 }
235
236 double[] expected = new double[mapSize];
237 long[] observed = new long[mapSize];
238 for (int i = 0; i < probabilies.length; i++) {
239 if (probabilies[i] != 0) {
240 --mapSize;
241 expected[mapSize] = probabilies[i];
242 observed[mapSize] = samples[i];
243 } else {
244 Assert.assertEquals("No samples expected from zero probability", 0, samples[i]);
245 }
246 }
247
248 final ChiSquareTest chiSquareTest = new ChiSquareTest();
249
250 Assert.assertFalse(chiSquareTest.chiSquareTest(expected, observed, 0.001));
251 }
252
253
254
255
256 @Test
257 public void testSharedStateSamplerWithPowerOf2TableSize() {
258 testSharedStateSampler(new double[] {0.1, 0.2, 0.3, 0.4});
259 }
260
261
262
263
264 @Test
265 public void testSharedStateSamplerWithNonPowerOf2TableSize() {
266 testSharedStateSampler(new double[] {0.1, 0.2, 0.3});
267 }
268
269
270
271
272
273
274 private static void testSharedStateSampler(double[] probabilities) {
275 final UniformRandomProvider rng1 = RandomSource.create(RandomSource.SPLIT_MIX_64, 0L);
276 final UniformRandomProvider rng2 = RandomSource.create(RandomSource.SPLIT_MIX_64, 0L);
277
278 final SharedStateDiscreteSampler sampler1 =
279 AliasMethodDiscreteSampler.of(rng1, probabilities, -1);
280 final SharedStateDiscreteSampler sampler2 = sampler1.withUniformRandomProvider(rng2);
281 RandomAssert.assertProduceSameSequence(sampler1, sampler2);
282 }
283 }