KempSmallMeanPoissonSampler.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.rng.sampling.distribution;

import org.apache.commons.rng.UniformRandomProvider;

/**
 * Sampler for the <a href="http://mathworld.wolfram.com/PoissonDistribution.html">Poisson
 * distribution</a>.
 *
 * <ul>
 *   <li>
 *     Kemp, A, W, (1981) Efficient Generation of Logarithmically Distributed
 *     Pseudo-Random Variables. Journal of the Royal Statistical Society. Vol. 30, No. 3, pp.
 *     249-253.
 *   </li>
 * </ul>
 *
 * <p>This sampler is suitable for {@code mean < 40}. For large means,
 * {@link LargeMeanPoissonSampler} should be used instead.</p>
 *
 * <p>Note: The algorithm uses a recurrence relation to compute the Poisson probability
 * and a rolling summation for the cumulative probability. When the mean is large the
 * initial probability (Math.exp(-mean)) is zero and an exception is raised by the
 * constructor.</p>
 *
 * <p>Sampling uses 1 call to {@link UniformRandomProvider#nextDouble()}. This method provides
 * an alternative to the {@link SmallMeanPoissonSampler} for slow generators of {@code double}.</p>
 *
 * @see <a href="https://www.jstor.org/stable/2346348">Kemp, A.W. (1981) JRSS Vol. 30, pp.
 * 249-253</a>
 * @since 1.3
 */
public final class KempSmallMeanPoissonSampler
    implements SharedStateDiscreteSampler {
    /** Underlying source of randomness. */
    private final UniformRandomProvider rng;
    /**
     * Pre-compute {@code Math.exp(-mean)}.
     * Note: This is the probability of the Poisson sample {@code p(x=0)}.
     */
    private final double p0;
    /**
     * The mean of the Poisson sample.
     */
    private final double mean;

    /**
     * @param rng Generator of uniformly distributed random numbers.
     * @param p0 Probability of the Poisson sample {@code p(x=0)}.
     * @param mean Mean.
     */
    private KempSmallMeanPoissonSampler(UniformRandomProvider rng,
                                        double p0,
                                        double mean) {
        this.rng = rng;
        this.p0 = p0;
        this.mean = mean;
    }

    /** {@inheritDoc} */
    @Override
    public int sample() {
        // Note on the algorithm:
        // - X is the unknown sample deviate (the output of the algorithm)
        // - x is the current value from the distribution
        // - p is the probability of the current value x, p(X=x)
        // - u is effectively the cumulative probability that the sample X
        //   is equal or above the current value x, p(X>=x)
        // So if p(X>=x) > p(X=x) the sample must be above x, otherwise it is x
        double u = rng.nextDouble();
        int x = 0;
        double p = p0;
        while (u > p) {
            u -= p;
            // Compute the next probability using a recurrence relation.
            // p(x+1) = p(x) * mean / (x+1)
            p *= mean / ++x;
            // The algorithm listed in Kemp (1981) does not check that the rolling probability
            // is positive. This check is added to ensure no errors when the limit of the summation
            // 1 - sum(p(x)) is above 0 due to cumulative error in floating point arithmetic.
            if (p == 0) {
                return x;
            }
        }
        return x;
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return "Kemp Small Mean Poisson deviate [" + rng.toString() + "]";
    }

    /** {@inheritDoc} */
    @Override
    public SharedStateDiscreteSampler withUniformRandomProvider(UniformRandomProvider rng) {
        return new KempSmallMeanPoissonSampler(rng, p0, mean);
    }

    /**
     * Creates a new sampler for the Poisson distribution.
     *
     * @param rng Generator of uniformly distributed random numbers.
     * @param mean Mean of the distribution.
     * @return the sampler
     * @throws IllegalArgumentException if {@code mean <= 0} or
     * {@code Math.exp(-mean) == 0}.
     */
    public static SharedStateDiscreteSampler of(UniformRandomProvider rng,
                                                double mean) {
        InternalUtils.requireStrictlyPositive(mean, "mean");

        final double p0 = Math.exp(-mean);

        // Probability must be positive. As mean increases then p(0) decreases.
        if (p0 > 0) {
            return new KempSmallMeanPoissonSampler(rng, p0, mean);
        }

        // This catches the edge case of a NaN mean
        throw new IllegalArgumentException("No probability for mean: " + mean);
    }
}