1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements.  See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License.  You may obtain a copy of the License at
8  *
9  *      http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 package org.apache.commons.math3.distribution;
18 
19 import org.apache.commons.math3.exception.NotStrictlyPositiveException;
20 import org.apache.commons.math3.exception.OutOfRangeException;
21 import org.apache.commons.math3.exception.util.LocalizedFormats;
22 import org.apache.commons.math3.random.RandomGenerator;
23 import org.apache.commons.math3.random.Well19937c;
24 import org.apache.commons.math3.util.CombinatoricsUtils;
25 import org.apache.commons.math3.util.FastMath;
26 import org.apache.commons.math3.util.ResizableDoubleArray;
27 
28 /**
29  * Implementation of the exponential distribution.
30  *
31  * @see <a href="http://en.wikipedia.org/wiki/Exponential_distribution">Exponential distribution
32  *     (Wikipedia)</a>
33  * @see <a href="http://mathworld.wolfram.com/ExponentialDistribution.html">Exponential distribution
34  *     (MathWorld)</a>
35  */
36 public class ExponentialDistribution extends AbstractRealDistribution {
37     /**
38      * Default inverse cumulative probability accuracy.
39      *
40      * @since 2.1
41      */
42     public static final double DEFAULT_INVERSE_ABSOLUTE_ACCURACY = 1e-9;
43 
44     /** Serializable version identifier */
45     private static final long serialVersionUID = 2401296428283614780L;
46 
47     /**
48      * Used when generating Exponential samples. Table containing the constants q_i = sum_{j=1}^i
49      * (ln 2)^j/j! = ln 2 + (ln 2)^2/2 + ... + (ln 2)^i/i! until the largest representable fraction
50      * below 1 is exceeded.
51      *
52      * <p>Note that 1 = 2 - 1 = exp(ln 2) - 1 = sum_{n=1}^infty (ln 2)^n / n! thus q_i -> 1 as i ->
53      * +inf, so the higher i, the closer to one we get (the series is not alternating).
54      *
55      * <p>By trying, n = 16 in Java is enough to reach 1.0.
56      */
57     private static final double[] EXPONENTIAL_SA_QI;
58 
59     /** The mean of this distribution. */
60     private final double mean;
61 
62     /** The logarithm of the mean, stored to reduce computing time. * */
63     private final double logMean;
64 
65     /** Inverse cumulative probability accuracy. */
66     private final double solverAbsoluteAccuracy;
67 
68     /** Initialize tables. */
69     static {
70         /** Filling EXPONENTIAL_SA_QI table. Note that we don't want qi = 0 in the table. */
71         final double LN2 = FastMath.log(2);
72         double qi = 0;
73         int i = 1;
74 
75         /**
76          * ArithmeticUtils provides factorials up to 20, so let's use that limit together with
77          * Precision.EPSILON to generate the following code (a priori, we know that there will be 16
78          * elements, but it is better to not hardcode it).
79          */
80         final ResizableDoubleArray ra = new ResizableDoubleArray(20);
81 
82         while (qi < 1) {
83             qi += FastMath.pow(LN2, i) / CombinatoricsUtils.factorial(i);
84             ra.addElement(qi);
85             ++i;
86         }
87 
88         EXPONENTIAL_SA_QI = ra.getElements();
89     }
90 
91     /**
92      * Create an exponential distribution with the given mean.
93      *
94      * <p><b>Note:</b> this constructor will implicitly create an instance of {@link Well19937c} as
95      * random generator to be used for sampling only (see {@link #sample()} and {@link
96      * #sample(int)}). In case no sampling is needed for the created distribution, it is advised to
97      * pass {@code null} as random generator via the appropriate constructors to avoid the
98      * additional initialisation overhead.
99      *
100      * @param mean mean of this distribution.
101      */
ExponentialDistribution(double mean)102     public ExponentialDistribution(double mean) {
103         this(mean, DEFAULT_INVERSE_ABSOLUTE_ACCURACY);
104     }
105 
106     /**
107      * Create an exponential distribution with the given mean.
108      *
109      * <p><b>Note:</b> this constructor will implicitly create an instance of {@link Well19937c} as
110      * random generator to be used for sampling only (see {@link #sample()} and {@link
111      * #sample(int)}). In case no sampling is needed for the created distribution, it is advised to
112      * pass {@code null} as random generator via the appropriate constructors to avoid the
113      * additional initialisation overhead.
114      *
115      * @param mean Mean of this distribution.
116      * @param inverseCumAccuracy Maximum absolute error in inverse cumulative probability estimates
117      *     (defaults to {@link #DEFAULT_INVERSE_ABSOLUTE_ACCURACY}).
118      * @throws NotStrictlyPositiveException if {@code mean <= 0}.
119      * @since 2.1
120      */
ExponentialDistribution(double mean, double inverseCumAccuracy)121     public ExponentialDistribution(double mean, double inverseCumAccuracy) {
122         this(new Well19937c(), mean, inverseCumAccuracy);
123     }
124 
125     /**
126      * Creates an exponential distribution.
127      *
128      * @param rng Random number generator.
129      * @param mean Mean of this distribution.
130      * @throws NotStrictlyPositiveException if {@code mean <= 0}.
131      * @since 3.3
132      */
ExponentialDistribution(RandomGenerator rng, double mean)133     public ExponentialDistribution(RandomGenerator rng, double mean)
134             throws NotStrictlyPositiveException {
135         this(rng, mean, DEFAULT_INVERSE_ABSOLUTE_ACCURACY);
136     }
137 
138     /**
139      * Creates an exponential distribution.
140      *
141      * @param rng Random number generator.
142      * @param mean Mean of this distribution.
143      * @param inverseCumAccuracy Maximum absolute error in inverse cumulative probability estimates
144      *     (defaults to {@link #DEFAULT_INVERSE_ABSOLUTE_ACCURACY}).
145      * @throws NotStrictlyPositiveException if {@code mean <= 0}.
146      * @since 3.1
147      */
ExponentialDistribution(RandomGenerator rng, double mean, double inverseCumAccuracy)148     public ExponentialDistribution(RandomGenerator rng, double mean, double inverseCumAccuracy)
149             throws NotStrictlyPositiveException {
150         super(rng);
151 
152         if (mean <= 0) {
153             throw new NotStrictlyPositiveException(LocalizedFormats.MEAN, mean);
154         }
155         this.mean = mean;
156         logMean = FastMath.log(mean);
157         solverAbsoluteAccuracy = inverseCumAccuracy;
158     }
159 
160     /**
161      * Access the mean.
162      *
163      * @return the mean.
164      */
getMean()165     public double getMean() {
166         return mean;
167     }
168 
169     /** {@inheritDoc} */
density(double x)170     public double density(double x) {
171         final double logDensity = logDensity(x);
172         return logDensity == Double.NEGATIVE_INFINITY ? 0 : FastMath.exp(logDensity);
173     }
174 
175     /** {@inheritDoc} * */
176     @Override
logDensity(double x)177     public double logDensity(double x) {
178         if (x < 0) {
179             return Double.NEGATIVE_INFINITY;
180         }
181         return -x / mean - logMean;
182     }
183 
184     /**
185      * {@inheritDoc}
186      *
187      * <p>The implementation of this method is based on:
188      *
189      * <ul>
190      *   <li><a href="http://mathworld.wolfram.com/ExponentialDistribution.html">Exponential
191      *       Distribution</a>, equation (1).
192      * </ul>
193      */
cumulativeProbability(double x)194     public double cumulativeProbability(double x) {
195         double ret;
196         if (x <= 0.0) {
197             ret = 0.0;
198         } else {
199             ret = 1.0 - FastMath.exp(-x / mean);
200         }
201         return ret;
202     }
203 
204     /**
205      * {@inheritDoc}
206      *
207      * <p>Returns {@code 0} when {@code p= = 0} and {@code Double.POSITIVE_INFINITY} when {@code p
208      * == 1}.
209      */
210     @Override
inverseCumulativeProbability(double p)211     public double inverseCumulativeProbability(double p) throws OutOfRangeException {
212         double ret;
213 
214         if (p < 0.0 || p > 1.0) {
215             throw new OutOfRangeException(p, 0.0, 1.0);
216         } else if (p == 1.0) {
217             ret = Double.POSITIVE_INFINITY;
218         } else {
219             ret = -mean * FastMath.log(1.0 - p);
220         }
221 
222         return ret;
223     }
224 
225     /**
226      * {@inheritDoc}
227      *
228      * <p><strong>Algorithm Description</strong>: this implementation uses the <a
229      * href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html">Inversion Method</a> to
230      * generate exponentially distributed random values from uniform deviates.
231      *
232      * @return a random value.
233      * @since 2.2
234      */
235     @Override
sample()236     public double sample() {
237         // Step 1:
238         double a = 0;
239         double u = random.nextDouble();
240 
241         // Step 2 and 3:
242         while (u < 0.5) {
243             a += EXPONENTIAL_SA_QI[0];
244             u *= 2;
245         }
246 
247         // Step 4 (now u >= 0.5):
248         u += u - 1;
249 
250         // Step 5:
251         if (u <= EXPONENTIAL_SA_QI[0]) {
252             return mean * (a + u);
253         }
254 
255         // Step 6:
256         int i = 0; // Should be 1, be we iterate before it in while using 0
257         double u2 = random.nextDouble();
258         double umin = u2;
259 
260         // Step 7 and 8:
261         do {
262             ++i;
263             u2 = random.nextDouble();
264 
265             if (u2 < umin) {
266                 umin = u2;
267             }
268 
269             // Step 8:
270         } while (u > EXPONENTIAL_SA_QI[i]); // Ensured to exit since EXPONENTIAL_SA_QI[MAX] = 1
271 
272         return mean * (a + umin * EXPONENTIAL_SA_QI[0]);
273     }
274 
275     /** {@inheritDoc} */
276     @Override
getSolverAbsoluteAccuracy()277     protected double getSolverAbsoluteAccuracy() {
278         return solverAbsoluteAccuracy;
279     }
280 
281     /**
282      * {@inheritDoc}
283      *
284      * <p>For mean parameter {@code k}, the mean is {@code k}.
285      */
getNumericalMean()286     public double getNumericalMean() {
287         return getMean();
288     }
289 
290     /**
291      * {@inheritDoc}
292      *
293      * <p>For mean parameter {@code k}, the variance is {@code k^2}.
294      */
getNumericalVariance()295     public double getNumericalVariance() {
296         final double m = getMean();
297         return m * m;
298     }
299 
300     /**
301      * {@inheritDoc}
302      *
303      * <p>The lower bound of the support is always 0 no matter the mean parameter.
304      *
305      * @return lower bound of the support (always 0)
306      */
getSupportLowerBound()307     public double getSupportLowerBound() {
308         return 0;
309     }
310 
311     /**
312      * {@inheritDoc}
313      *
314      * <p>The upper bound of the support is always positive infinity no matter the mean parameter.
315      *
316      * @return upper bound of the support (always Double.POSITIVE_INFINITY)
317      */
getSupportUpperBound()318     public double getSupportUpperBound() {
319         return Double.POSITIVE_INFINITY;
320     }
321 
322     /** {@inheritDoc} */
isSupportLowerBoundInclusive()323     public boolean isSupportLowerBoundInclusive() {
324         return true;
325     }
326 
327     /** {@inheritDoc} */
isSupportUpperBoundInclusive()328     public boolean isSupportUpperBoundInclusive() {
329         return false;
330     }
331 
332     /**
333      * {@inheritDoc}
334      *
335      * <p>The support of this distribution is connected.
336      *
337      * @return {@code true}
338      */
isSupportConnected()339     public boolean isSupportConnected() {
340         return true;
341     }
342 }
343