001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math4.distribution;
018
019import java.io.Serializable;
020
021import org.apache.commons.statistics.distribution.DiscreteDistribution;
022import org.apache.commons.math4.exception.MathInternalError;
023import org.apache.commons.math4.exception.NumberIsTooLargeException;
024import org.apache.commons.math4.exception.OutOfRangeException;
025import org.apache.commons.math4.exception.util.LocalizedFormats;
026import org.apache.commons.rng.UniformRandomProvider;
027import org.apache.commons.rng.sampling.distribution.InverseTransformDiscreteSampler;
028import org.apache.commons.rng.sampling.distribution.DiscreteInverseCumulativeProbabilityFunction;
029import org.apache.commons.rng.sampling.distribution.DiscreteSampler;
030import org.apache.commons.math4.util.FastMath;
031
032/**
033 * Base class for integer-valued discrete distributions.  Default
034 * implementations are provided for some of the methods that do not vary
035 * from distribution to distribution.
036 *
037 */
038public abstract class AbstractIntegerDistribution implements DiscreteDistribution, Serializable {
039    /** Serializable version identifier */
040    private static final long serialVersionUID = 20160318L;
041
042    /**
043     * {@inheritDoc}
044     *
045     * The default implementation uses the identity
046     * <p>{@code P(x0 < X <= x1) = P(X <= x1) - P(X <= x0)}</p>
047     *
048     * @since 4.0, was previously named cumulativeProbability
049     */
050    @Override
051    public double probability(int x0, int x1) throws NumberIsTooLargeException {
052        if (x1 < x0) {
053            throw new NumberIsTooLargeException(LocalizedFormats.LOWER_ENDPOINT_ABOVE_UPPER_ENDPOINT,
054                    x0, x1, true);
055        }
056        return cumulativeProbability(x1) - cumulativeProbability(x0);
057    }
058
059    /**
060     * {@inheritDoc}
061     *
062     * The default implementation returns
063     * <ul>
064     * <li>{@link #getSupportLowerBound()} for {@code p = 0},</li>
065     * <li>{@link #getSupportUpperBound()} for {@code p = 1}, and</li>
066     * <li>{@link #solveInverseCumulativeProbability(double, int, int)} for
067     *     {@code 0 < p < 1}.</li>
068     * </ul>
069     */
070    @Override
071    public int inverseCumulativeProbability(final double p) throws OutOfRangeException {
072        if (p < 0.0 || p > 1.0) {
073            throw new OutOfRangeException(p, 0, 1);
074        }
075
076        int lower = getSupportLowerBound();
077        if (p == 0.0) {
078            return lower;
079        }
080        if (lower == Integer.MIN_VALUE) {
081            if (checkedCumulativeProbability(lower) >= p) {
082                return lower;
083            }
084        } else {
085            lower -= 1; // this ensures cumulativeProbability(lower) < p, which
086                        // is important for the solving step
087        }
088
089        int upper = getSupportUpperBound();
090        if (p == 1.0) {
091            return upper;
092        }
093
094        // use the one-sided Chebyshev inequality to narrow the bracket
095        // cf. AbstractRealDistribution.inverseCumulativeProbability(double)
096        final double mu = getMean();
097        final double sigma = FastMath.sqrt(getVariance());
098        final boolean chebyshevApplies = !(Double.isInfinite(mu) || Double.isNaN(mu) ||
099                Double.isInfinite(sigma) || Double.isNaN(sigma) || sigma == 0.0);
100        if (chebyshevApplies) {
101            double k = FastMath.sqrt((1.0 - p) / p);
102            double tmp = mu - k * sigma;
103            if (tmp > lower) {
104                lower = ((int) FastMath.ceil(tmp)) - 1;
105            }
106            k = 1.0 / k;
107            tmp = mu + k * sigma;
108            if (tmp < upper) {
109                upper = ((int) FastMath.ceil(tmp)) - 1;
110            }
111        }
112
113        return solveInverseCumulativeProbability(p, lower, upper);
114    }
115
116    /**
117     * This is a utility function used by {@link
118     * #inverseCumulativeProbability(double)}. It assumes {@code 0 < p < 1} and
119     * that the inverse cumulative probability lies in the bracket {@code
120     * (lower, upper]}. The implementation does simple bisection to find the
121     * smallest {@code p}-quantile {@code inf{x in Z | P(X<=x) >= p}}.
122     *
123     * @param p the cumulative probability
124     * @param lower a value satisfying {@code cumulativeProbability(lower) < p}
125     * @param upper a value satisfying {@code p <= cumulativeProbability(upper)}
126     * @return the smallest {@code p}-quantile of this distribution
127     */
128    protected int solveInverseCumulativeProbability(final double p, int lower, int upper) {
129        while (lower + 1 < upper) {
130            int xm = (lower + upper) / 2;
131            if (xm < lower || xm > upper) {
132                /*
133                 * Overflow.
134                 * There will never be an overflow in both calculation methods
135                 * for xm at the same time
136                 */
137                xm = lower + (upper - lower) / 2;
138            }
139
140            double pm = checkedCumulativeProbability(xm);
141            if (pm >= p) {
142                upper = xm;
143            } else {
144                lower = xm;
145            }
146        }
147        return upper;
148    }
149
150    /**
151     * Computes the cumulative probability function and checks for {@code NaN}
152     * values returned. Throws {@code MathInternalError} if the value is
153     * {@code NaN}. Rethrows any exception encountered evaluating the cumulative
154     * probability function. Throws {@code MathInternalError} if the cumulative
155     * probability function returns {@code NaN}.
156     *
157     * @param argument input value
158     * @return the cumulative probability
159     * @throws MathInternalError if the cumulative probability is {@code NaN}
160     */
161    private double checkedCumulativeProbability(int argument)
162        throws MathInternalError {
163        final double result = cumulativeProbability(argument);
164        if (Double.isNaN(result)) {
165            throw new MathInternalError(LocalizedFormats
166                    .DISCRETE_CUMULATIVE_PROBABILITY_RETURNED_NAN, argument);
167        }
168        return result;
169    }
170
171    /**
172     * {@inheritDoc}
173     * <p>
174     * The default implementation simply computes the logarithm of {@code probability(x)}.
175     */
176    @Override
177    public double logProbability(int x) {
178        return FastMath.log(probability(x));
179    }
180
181    /**
182     * Utility function for allocating an array and filling it with {@code n}
183     * samples generated by the given {@code sampler}.
184     *
185     * @param n Number of samples.
186     * @param sampler Sampler.
187     * @return an array of size {@code n}.
188     */
189    public static int[] sample(int n,
190                               DiscreteDistribution.Sampler sampler) {
191        final int[] samples = new int[n];
192        for (int i = 0; i < n; i++) {
193            samples[i] = sampler.sample();
194        }
195        return samples;
196    }
197
198    /**{@inheritDoc} */
199    @Override
200    public DiscreteDistribution.Sampler createSampler(final UniformRandomProvider rng) {
201        return new DiscreteDistribution.Sampler() {
202            /**
203             * Inversion method distribution sampler.
204             */
205            private final DiscreteSampler sampler =
206                new InverseTransformDiscreteSampler(rng, createICPF());
207
208            /** {@inheritDoc} */
209            @Override
210            public int sample() {
211                return sampler.sample();
212            }
213        };
214    }
215
216    /**
217     * @return an instance for use by {@link #createSampler(UniformRandomProvider)}
218     */
219    private DiscreteInverseCumulativeProbabilityFunction createICPF() {
220        return new DiscreteInverseCumulativeProbabilityFunction() {
221            /** {@inheritDoc} */
222            @Override
223            public int inverseCumulativeProbability(double p) {
224                return AbstractIntegerDistribution.this.inverseCumulativeProbability(p);
225            }
226        };
227    }
228}