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.legacy.distribution;
018
019import org.apache.commons.statistics.distribution.DiscreteDistribution;
020import org.apache.commons.math4.legacy.exception.MathInternalError;
021import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException;
022import org.apache.commons.math4.legacy.exception.OutOfRangeException;
023import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
024import org.apache.commons.rng.UniformRandomProvider;
025import org.apache.commons.rng.sampling.distribution.InverseTransformDiscreteSampler;
026import org.apache.commons.math4.core.jdkmath.JdkMath;
027
028/**
029 * Base class for integer-valued discrete distributions.  Default
030 * implementations are provided for some of the methods that do not vary
031 * from distribution to distribution.
032 *
033 */
034public abstract class AbstractIntegerDistribution
035    implements DiscreteDistribution {
036    /**
037     * {@inheritDoc}
038     *
039     * The default implementation uses the identity
040     * <p>{@code P(x0 < X <= x1) = P(X <= x1) - P(X <= x0)}</p>
041     *
042     * @since 4.0, was previously named cumulativeProbability
043     */
044    @Override
045    public double probability(int x0, int x1) throws NumberIsTooLargeException {
046        if (x1 < x0) {
047            throw new NumberIsTooLargeException(LocalizedFormats.LOWER_ENDPOINT_ABOVE_UPPER_ENDPOINT,
048                    x0, x1, true);
049        }
050        return cumulativeProbability(x1) - cumulativeProbability(x0);
051    }
052
053    /**
054     * {@inheritDoc}
055     *
056     * The default implementation returns
057     * <ul>
058     * <li>{@link #getSupportLowerBound()} for {@code p = 0},</li>
059     * <li>{@link #getSupportUpperBound()} for {@code p = 1}, and</li>
060     * <li>{@link #solveInverseCumulativeProbability(double, int, int)} for
061     *     {@code 0 < p < 1}.</li>
062     * </ul>
063     */
064    @Override
065    public int inverseCumulativeProbability(final double p) throws OutOfRangeException {
066        if (p < 0.0 || p > 1.0) {
067            throw new OutOfRangeException(p, 0, 1);
068        }
069
070        int lower = getSupportLowerBound();
071        if (p == 0.0) {
072            return lower;
073        }
074        if (lower == Integer.MIN_VALUE) {
075            if (checkedCumulativeProbability(lower) >= p) {
076                return lower;
077            }
078        } else {
079            lower -= 1; // this ensures cumulativeProbability(lower) < p, which
080                        // is important for the solving step
081        }
082
083        int upper = getSupportUpperBound();
084        if (p == 1.0) {
085            return upper;
086        }
087
088        // use the one-sided Chebyshev inequality to narrow the bracket
089        // cf. AbstractRealDistribution.inverseCumulativeProbability(double)
090        final double mu = getMean();
091        final double sigma = JdkMath.sqrt(getVariance());
092        final boolean chebyshevApplies = !(Double.isInfinite(mu) || Double.isNaN(mu) ||
093                Double.isInfinite(sigma) || Double.isNaN(sigma) || sigma == 0.0);
094        if (chebyshevApplies) {
095            double k = JdkMath.sqrt((1.0 - p) / p);
096            double tmp = mu - k * sigma;
097            if (tmp > lower) {
098                lower = ((int) JdkMath.ceil(tmp)) - 1;
099            }
100            k = 1.0 / k;
101            tmp = mu + k * sigma;
102            if (tmp < upper) {
103                upper = ((int) JdkMath.ceil(tmp)) - 1;
104            }
105        }
106
107        return solveInverseCumulativeProbability(p, lower, upper);
108    }
109
110    /**
111     * This is a utility function used by {@link
112     * #inverseCumulativeProbability(double)}. It assumes {@code 0 < p < 1} and
113     * that the inverse cumulative probability lies in the bracket {@code
114     * (lower, upper]}. The implementation does simple bisection to find the
115     * smallest {@code p}-quantile {@code inf{x in Z | P(X<=x) >= p}}.
116     *
117     * @param p the cumulative probability
118     * @param lower a value satisfying {@code cumulativeProbability(lower) < p}
119     * @param upper a value satisfying {@code p <= cumulativeProbability(upper)}
120     * @return the smallest {@code p}-quantile of this distribution
121     */
122    protected int solveInverseCumulativeProbability(final double p, int lower, int upper) {
123        while (lower + 1 < upper) {
124            int xm = (lower + upper) / 2;
125            if (xm < lower || xm > upper) {
126                /*
127                 * Overflow.
128                 * There will never be an overflow in both calculation methods
129                 * for xm at the same time
130                 */
131                xm = lower + (upper - lower) / 2;
132            }
133
134            double pm = checkedCumulativeProbability(xm);
135            if (pm >= p) {
136                upper = xm;
137            } else {
138                lower = xm;
139            }
140        }
141        return upper;
142    }
143
144    /**
145     * Computes the cumulative probability function and checks for {@code NaN}
146     * values returned. Throws {@code MathInternalError} if the value is
147     * {@code NaN}. Rethrows any exception encountered evaluating the cumulative
148     * probability function. Throws {@code MathInternalError} if the cumulative
149     * probability function returns {@code NaN}.
150     *
151     * @param argument input value
152     * @return the cumulative probability
153     * @throws MathInternalError if the cumulative probability is {@code NaN}
154     */
155    private double checkedCumulativeProbability(int argument)
156        throws MathInternalError {
157        final double result = cumulativeProbability(argument);
158        if (Double.isNaN(result)) {
159            throw new MathInternalError(LocalizedFormats
160                    .DISCRETE_CUMULATIVE_PROBABILITY_RETURNED_NAN, argument);
161        }
162        return result;
163    }
164
165    /**
166     * {@inheritDoc}
167     * <p>
168     * The default implementation simply computes the logarithm of {@code probability(x)}.
169     */
170    @Override
171    public double logProbability(int x) {
172        return JdkMath.log(probability(x));
173    }
174
175    /**
176     * Utility function for allocating an array and filling it with {@code n}
177     * samples generated by the given {@code sampler}.
178     *
179     * @param n Number of samples.
180     * @param sampler Sampler.
181     * @return an array of size {@code n}.
182     */
183    public static int[] sample(int n,
184                               DiscreteDistribution.Sampler sampler) {
185        final int[] samples = new int[n];
186        for (int i = 0; i < n; i++) {
187            samples[i] = sampler.sample();
188        }
189        return samples;
190    }
191
192    /**{@inheritDoc} */
193    @Override
194    public DiscreteDistribution.Sampler createSampler(final UniformRandomProvider rng) {
195        // Inversion method distribution sampler.
196        return InverseTransformDiscreteSampler.of(rng, this::inverseCumulativeProbability)::sample;
197    }
198}