ceph/src/boost/libs/math/include/boost/math/distributions/geometric.hpp

   1 // boost\math\distributions\geometric.hpp
   2
   3 // Copyright John Maddock 2010.
   4 // Copyright Paul A. Bristow 2010.
   5
   6 // Use, modification and distribution are subject to the
   7 // Boost Software License, Version 1.0.
   8 // (See accompanying file LICENSE_1_0.txt
   9 // or copy at http://www.boost.org/LICENSE_1_0.txt)
  10
  11 // geometric distribution is a discrete probability distribution.
  12 // It expresses the probability distribution of the number (k) of
  13 // events, occurrences, failures or arrivals before the first success.
  14 // supported on the set {0, 1, 2, 3...}
  15
  16 // Note that the set includes zero (unlike some definitions that start at one).
  17
  18 // The random variate k is the number of events, occurrences or arrivals.
  19 // k argument may be integral, signed, or unsigned, or floating point.
  20 // If necessary, it has already been promoted from an integral type.
  21
  22 // Note that the geometric distribution
  23 // (like others including the binomial, geometric & Bernoulli)
  24 // is strictly defined as a discrete function:
  25 // only integral values of k are envisaged.
  26 // However because the method of calculation uses a continuous gamma function,
  27 // it is convenient to treat it as if a continous function,
  28 // and permit non-integral values of k.
  29 // To enforce the strict mathematical model, users should use floor or ceil functions
  30 // on k outside this function to ensure that k is integral.
  31
  32 // See http://en.wikipedia.org/wiki/geometric_distribution
  33 // http://documents.wolfram.com/v5/Add-onsLinks/StandardPackages/Statistics/DiscreteDistributions.html
  34 // http://mathworld.wolfram.com/GeometricDistribution.html
  35
  36 #ifndef BOOST_MATH_SPECIAL_GEOMETRIC_HPP
  37 #define BOOST_MATH_SPECIAL_GEOMETRIC_HPP
  38
  39 #include <boost/math/distributions/fwd.hpp>
  40 #include <boost/math/special_functions/beta.hpp> // for ibeta(a, b, x) == Ix(a, b).
  41 #include <boost/math/distributions/complement.hpp> // complement.
  42 #include <boost/math/distributions/detail/common_error_handling.hpp> // error checks domain_error & logic_error.
  43 #include <boost/math/special_functions/fpclassify.hpp> // isnan.
  44 #include <boost/math/tools/roots.hpp> // for root finding.
  45 #include <boost/math/distributions/detail/inv_discrete_quantile.hpp>
  46
  47 #include <boost/type_traits/is_floating_point.hpp>
  48 #include <boost/type_traits/is_integral.hpp>
  49 #include <boost/type_traits/is_same.hpp>
  50 #include <boost/mpl/if.hpp>
  51
  52 #include <limits> // using std::numeric_limits;
  53 #include <utility>
  54
  55 #if defined (BOOST_MSVC)
  56 #  pragma warning(push)
  57 // This believed not now necessary, so commented out.
  58 //#  pragma warning(disable: 4702) // unreachable code.
  59 // in domain_error_imp in error_handling.
  60 #endif
  61
  62 namespace boost
  63 {
  64   namespace math
  65   {
  66     namespace geometric_detail
  67     {
  68       // Common error checking routines for geometric distribution function:
  69       template <class RealType, class Policy>
  70       inline bool check_success_fraction(const char* function, const RealType& p, RealType* result, const Policy& pol)
  71       {
  72         if( !(boost::math::isfinite)(p) || (p < 0) || (p > 1) )
  73         {
  74           *result = policies::raise_domain_error<RealType>(
  75             function,
  76             "Success fraction argument is %1%, but must be >= 0 and <= 1 !", p, pol);
  77           return false;
  78         }
  79         return true;
  80       }
  81
  82       template <class RealType, class Policy>
  83       inline bool check_dist(const char* function, const RealType& p, RealType* result, const Policy& pol)
  84       {
  85         return check_success_fraction(function, p, result, pol);
  86       }
  87
  88       template <class RealType, class Policy>
  89       inline bool check_dist_and_k(const char* function,  const RealType& p, RealType k, RealType* result, const Policy& pol)
  90       {
  91         if(check_dist(function, p, result, pol) == false)
  92         {
  93           return false;
  94         }
  95         if( !(boost::math::isfinite)(k) || (k < 0) )
  96         { // Check k failures.
  97           *result = policies::raise_domain_error<RealType>(
  98             function,
  99             "Number of failures argument is %1%, but must be >= 0 !", k, pol);
 100           return false;
 101         }
 102         return true;
 103       } // Check_dist_and_k
 104
 105       template <class RealType, class Policy>
 106       inline bool check_dist_and_prob(const char* function, RealType p, RealType prob, RealType* result, const Policy& pol)
 107       {
 108         if((check_dist(function, p, result, pol) && detail::check_probability(function, prob, result, pol)) == false)
 109         {
 110           return false;
 111         }
 112         return true;
 113       } // check_dist_and_prob
 114     } //  namespace geometric_detail
 115
 116     template <class RealType = double, class Policy = policies::policy<> >
 117     class geometric_distribution
 118     {
 119     public:
 120       typedef RealType value_type;
 121       typedef Policy policy_type;
 122
 123       geometric_distribution(RealType p) : m_p(p)
 124       { // Constructor stores success_fraction p.
 125         RealType result;
 126         geometric_detail::check_dist(
 127           "geometric_distribution<%1%>::geometric_distribution",
 128           m_p, // Check success_fraction 0 <= p <= 1.
 129           &result, Policy());
 130       } // geometric_distribution constructor.
 131
 132       // Private data getter class member functions.
 133       RealType success_fraction() const
 134       { // Probability of success as fraction in range 0 to 1.
 135         return m_p;
 136       }
 137       RealType successes() const
 138       { // Total number of successes r = 1 (for compatibility with negative binomial?).
 139         return 1;
 140       }
 141
 142       // Parameter estimation.
 143       // (These are copies of negative_binomial distribution with successes = 1).
 144       static RealType find_lower_bound_on_p(
 145         RealType trials,
 146         RealType alpha) // alpha 0.05 equivalent to 95% for one-sided test.
 147       {
 148         static const char* function = "boost::math::geometric<%1%>::find_lower_bound_on_p";
 149         RealType result = 0;  // of error checks.
 150         RealType successes = 1;
 151         RealType failures = trials - successes;
 152         if(false == detail::check_probability(function, alpha, &result, Policy())
 153           && geometric_detail::check_dist_and_k(
 154           function, RealType(0), failures, &result, Policy()))
 155         {
 156           return result;
 157         }
 158         // Use complement ibeta_inv function for lower bound.
 159         // This is adapted from the corresponding binomial formula
 160         // here: http://www.itl.nist.gov/div898/handbook/prc/section2/prc241.htm
 161         // This is a Clopper-Pearson interval, and may be overly conservative,
 162         // see also "A Simple Improved Inferential Method for Some
 163         // Discrete Distributions" Yong CAI and K. KRISHNAMOORTHY
 164         // http://www.ucs.louisiana.edu/~kxk4695/Discrete_new.pdf
 165         //
 166         return ibeta_inv(successes, failures + 1, alpha, static_cast<RealType*>(0), Policy());
 167       } // find_lower_bound_on_p
 168
 169       static RealType find_upper_bound_on_p(
 170         RealType trials,
 171         RealType alpha) // alpha 0.05 equivalent to 95% for one-sided test.
 172       {
 173         static const char* function = "boost::math::geometric<%1%>::find_upper_bound_on_p";
 174         RealType result = 0;  // of error checks.
 175         RealType successes = 1;
 176         RealType failures = trials - successes;
 177         if(false == geometric_detail::check_dist_and_k(
 178           function, RealType(0), failures, &result, Policy())
 179           && detail::check_probability(function, alpha, &result, Policy()))
 180         {
 181           return result;
 182         }
 183         if(failures == 0)
 184         {
 185            return 1;
 186         }// Use complement ibetac_inv function for upper bound.
 187         // Note adjusted failures value: *not* failures+1 as usual.
 188         // This is adapted from the corresponding binomial formula
 189         // here: http://www.itl.nist.gov/div898/handbook/prc/section2/prc241.htm
 190         // This is a Clopper-Pearson interval, and may be overly conservative,
 191         // see also "A Simple Improved Inferential Method for Some
 192         // Discrete Distributions" Yong CAI and K. Krishnamoorthy
 193         // http://www.ucs.louisiana.edu/~kxk4695/Discrete_new.pdf
 194         //
 195         return ibetac_inv(successes, failures, alpha, static_cast<RealType*>(0), Policy());
 196       } // find_upper_bound_on_p
 197
 198       // Estimate number of trials :
 199       // "How many trials do I need to be P% sure of seeing k or fewer failures?"
 200
 201       static RealType find_minimum_number_of_trials(
 202         RealType k,     // number of failures (k >= 0).
 203         RealType p,     // success fraction 0 <= p <= 1.
 204         RealType alpha) // risk level threshold 0 <= alpha <= 1.
 205       {
 206         static const char* function = "boost::math::geometric<%1%>::find_minimum_number_of_trials";
 207         // Error checks:
 208         RealType result = 0;
 209         if(false == geometric_detail::check_dist_and_k(
 210           function, p, k, &result, Policy())
 211           && detail::check_probability(function, alpha, &result, Policy()))
 212         {
 213           return result;
 214         }
 215         result = ibeta_inva(k + 1, p, alpha, Policy());  // returns n - k
 216         return result + k;
 217       } // RealType find_number_of_failures
 218
 219       static RealType find_maximum_number_of_trials(
 220         RealType k,     // number of failures (k >= 0).
 221         RealType p,     // success fraction 0 <= p <= 1.
 222         RealType alpha) // risk level threshold 0 <= alpha <= 1.
 223       {
 224         static const char* function = "boost::math::geometric<%1%>::find_maximum_number_of_trials";
 225         // Error checks:
 226         RealType result = 0;
 227         if(false == geometric_detail::check_dist_and_k(
 228           function, p, k, &result, Policy())
 229           &&  detail::check_probability(function, alpha, &result, Policy()))
 230         {
 231           return result;
 232         }
 233         result = ibetac_inva(k + 1, p, alpha, Policy());  // returns n - k
 234         return result + k;
 235       } // RealType find_number_of_trials complemented
 236
 237     private:
 238       //RealType m_r; // successes fixed at unity.
 239       RealType m_p; // success_fraction
 240     }; // template <class RealType, class Policy> class geometric_distribution
 241
 242     typedef geometric_distribution<double> geometric; // Reserved name of type double.
 243
 244     template <class RealType, class Policy>
 245     inline const std::pair<RealType, RealType> range(const geometric_distribution<RealType, Policy>& /* dist */)
 246     { // Range of permissible values for random variable k.
 247        using boost::math::tools::max_value;
 248        return std::pair<RealType, RealType>(static_cast<RealType>(0), max_value<RealType>()); // max_integer?
 249     }
 250
 251     template <class RealType, class Policy>
 252     inline const std::pair<RealType, RealType> support(const geometric_distribution<RealType, Policy>& /* dist */)
 253     { // Range of supported values for random variable k.
 254        // This is range where cdf rises from 0 to 1, and outside it, the pdf is zero.
 255        using boost::math::tools::max_value;
 256        return std::pair<RealType, RealType>(static_cast<RealType>(0),  max_value<RealType>()); // max_integer?
 257     }
 258
 259     template <class RealType, class Policy>
 260     inline RealType mean(const geometric_distribution<RealType, Policy>& dist)
 261     { // Mean of geometric distribution = (1-p)/p.
 262       return (1 - dist.success_fraction() ) / dist.success_fraction();
 263     } // mean
 264
 265     // median implemented via quantile(half) in derived accessors.
 266
 267     template <class RealType, class Policy>
 268     inline RealType mode(const geometric_distribution<RealType, Policy>&)
 269     { // Mode of geometric distribution = zero.
 270       BOOST_MATH_STD_USING // ADL of std functions.
 271       return 0;
 272     } // mode
 273
 274     template <class RealType, class Policy>
 275     inline RealType variance(const geometric_distribution<RealType, Policy>& dist)
 276     { // Variance of Binomial distribution = (1-p) / p^2.
 277       return  (1 - dist.success_fraction())
 278         / (dist.success_fraction() * dist.success_fraction());
 279     } // variance
 280
 281     template <class RealType, class Policy>
 282     inline RealType skewness(const geometric_distribution<RealType, Policy>& dist)
 283     { // skewness of geometric distribution = 2-p / (sqrt(r(1-p))
 284       BOOST_MATH_STD_USING // ADL of std functions.
 285       RealType p = dist.success_fraction();
 286       return (2 - p) / sqrt(1 - p);
 287     } // skewness
 288
 289     template <class RealType, class Policy>
 290     inline RealType kurtosis(const geometric_distribution<RealType, Policy>& dist)
 291     { // kurtosis of geometric distribution
 292       // http://en.wikipedia.org/wiki/geometric is kurtosis_excess so add 3
 293       RealType p = dist.success_fraction();
 294       return 3 + (p*p - 6*p + 6) / (1 - p);
 295     } // kurtosis
 296
 297      template <class RealType, class Policy>
 298     inline RealType kurtosis_excess(const geometric_distribution<RealType, Policy>& dist)
 299     { // kurtosis excess of geometric distribution
 300       // http://mathworld.wolfram.com/Kurtosis.html table of kurtosis_excess
 301       RealType p = dist.success_fraction();
 302       return (p*p - 6*p + 6) / (1 - p);
 303     } // kurtosis_excess
 304
 305     // RealType standard_deviation(const geometric_distribution<RealType, Policy>& dist)
 306     // standard_deviation provided by derived accessors.
 307     // RealType hazard(const geometric_distribution<RealType, Policy>& dist)
 308     // hazard of geometric distribution provided by derived accessors.
 309     // RealType chf(const geometric_distribution<RealType, Policy>& dist)
 310     // chf of geometric distribution provided by derived accessors.
 311
 312     template <class RealType, class Policy>
 313     inline RealType pdf(const geometric_distribution<RealType, Policy>& dist, const RealType& k)
 314     { // Probability Density/Mass Function.
 315       BOOST_FPU_EXCEPTION_GUARD
 316       BOOST_MATH_STD_USING  // For ADL of math functions.
 317       static const char* function = "boost::math::pdf(const geometric_distribution<%1%>&, %1%)";
 318
 319       RealType p = dist.success_fraction();
 320       RealType result = 0;
 321       if(false == geometric_detail::check_dist_and_k(
 322         function,
 323         p,
 324         k,
 325         &result, Policy()))
 326       {
 327         return result;
 328       }
 329       if (k == 0)
 330       {
 331         return p; // success_fraction
 332       }
 333       RealType q = 1 - p;  // Inaccurate for small p?
 334       // So try to avoid inaccuracy for large or small p.
 335       // but has little effect > last significant bit.
 336       //cout << "p *  pow(q, k) " << result << endl; // seems best whatever p
 337       //cout << "exp(p * k * log1p(-p)) " << p * exp(k * log1p(-p)) << endl;
 338       //if (p < 0.5)
 339       //{
 340       //  result = p *  pow(q, k);
 341       //}
 342       //else
 343       //{
 344       //  result = p * exp(k * log1p(-p));
 345       //}
 346       result = p * pow(q, k);
 347       return result;
 348     } // geometric_pdf
 349
 350     template <class RealType, class Policy>
 351     inline RealType cdf(const geometric_distribution<RealType, Policy>& dist, const RealType& k)
 352     { // Cumulative Distribution Function of geometric.
 353       static const char* function = "boost::math::cdf(const geometric_distribution<%1%>&, %1%)";
 354
 355       // k argument may be integral, signed, or unsigned, or floating point.
 356       // If necessary, it has already been promoted from an integral type.
 357       RealType p = dist.success_fraction();
 358       // Error check:
 359       RealType result = 0;
 360       if(false == geometric_detail::check_dist_and_k(
 361         function,
 362         p,
 363         k,
 364         &result, Policy()))
 365       {
 366         return result;
 367       }
 368       if(k == 0)
 369       {
 370         return p; // success_fraction
 371       }
 372       //RealType q = 1 - p;  // Bad for small p
 373       //RealType probability = 1 - std::pow(q, k+1);
 374
 375       RealType z = boost::math::log1p(-p, Policy()) * (k + 1);
 376       RealType probability = -boost::math::expm1(z, Policy());
 377
 378       return probability;
 379     } // cdf Cumulative Distribution Function geometric.
 380
 381       template <class RealType, class Policy>
 382       inline RealType cdf(const complemented2_type<geometric_distribution<RealType, Policy>, RealType>& c)
 383       { // Complemented Cumulative Distribution Function geometric.
 384       BOOST_MATH_STD_USING
 385       static const char* function = "boost::math::cdf(const geometric_distribution<%1%>&, %1%)";
 386       // k argument may be integral, signed, or unsigned, or floating point.
 387       // If necessary, it has already been promoted from an integral type.
 388       RealType const& k = c.param;
 389       geometric_distribution<RealType, Policy> const& dist = c.dist;
 390       RealType p = dist.success_fraction();
 391       // Error check:
 392       RealType result = 0;
 393       if(false == geometric_detail::check_dist_and_k(
 394         function,
 395         p,
 396         k,
 397         &result, Policy()))
 398       {
 399         return result;
 400       }
 401       RealType z = boost::math::log1p(-p, Policy()) * (k+1);
 402       RealType probability = exp(z);
 403       return probability;
 404     } // cdf Complemented Cumulative Distribution Function geometric.
 405
 406     template <class RealType, class Policy>
 407     inline RealType quantile(const geometric_distribution<RealType, Policy>& dist, const RealType& x)
 408     { // Quantile, percentile/100 or Percent Point geometric function.
 409       // Return the number of expected failures k for a given probability p.
 410
 411       // Inverse cumulative Distribution Function or Quantile (percentile / 100) of geometric Probability.
 412       // k argument may be integral, signed, or unsigned, or floating point.
 413
 414       static const char* function = "boost::math::quantile(const geometric_distribution<%1%>&, %1%)";
 415       BOOST_MATH_STD_USING // ADL of std functions.
 416
 417       RealType success_fraction = dist.success_fraction();
 418       // Check dist and x.
 419       RealType result = 0;
 420       if(false == geometric_detail::check_dist_and_prob
 421         (function, success_fraction, x, &result, Policy()))
 422       {
 423         return result;
 424       }
 425
 426       // Special cases.
 427       if (x == 1)
 428       {  // Would need +infinity failures for total confidence.
 429         result = policies::raise_overflow_error<RealType>(
 430             function,
 431             "Probability argument is 1, which implies infinite failures !", Policy());
 432         return result;
 433        // usually means return +std::numeric_limits<RealType>::infinity();
 434        // unless #define BOOST_MATH_THROW_ON_OVERFLOW_ERROR
 435       }
 436       if (x == 0)
 437       { // No failures are expected if P = 0.
 438         return 0; // Total trials will be just dist.successes.
 439       }
 440       // if (P <= pow(dist.success_fraction(), 1))
 441       if (x <= success_fraction)
 442       { // p <= pdf(dist, 0) == cdf(dist, 0)
 443         return 0;
 444       }
 445       if (x == 1)
 446       {
 447         return 0;
 448       }
 449
 450       // log(1-x) /log(1-success_fraction) -1; but use log1p in case success_fraction is small
 451       result = boost::math::log1p(-x, Policy()) / boost::math::log1p(-success_fraction, Policy()) - 1;
 452       // Subtract a few epsilons here too?
 453       // to make sure it doesn't slip over, so ceil would be one too many.
 454       return result;
 455     } // RealType quantile(const geometric_distribution dist, p)
 456
 457     template <class RealType, class Policy>
 458     inline RealType quantile(const complemented2_type<geometric_distribution<RealType, Policy>, RealType>& c)
 459     {  // Quantile or Percent Point Binomial function.
 460        // Return the number of expected failures k for a given
 461        // complement of the probability Q = 1 - P.
 462        static const char* function = "boost::math::quantile(const geometric_distribution<%1%>&, %1%)";
 463        BOOST_MATH_STD_USING
 464        // Error checks:
 465        RealType x = c.param;
 466        const geometric_distribution<RealType, Policy>& dist = c.dist;
 467        RealType success_fraction = dist.success_fraction();
 468        RealType result = 0;
 469        if(false == geometric_detail::check_dist_and_prob(
 470           function,
 471           success_fraction,
 472           x,
 473           &result, Policy()))
 474        {
 475           return result;
 476        }
 477
 478        // Special cases:
 479        if(x == 1)
 480        {  // There may actually be no answer to this question,
 481           // since the probability of zero failures may be non-zero,
 482           return 0; // but zero is the best we can do:
 483        }
 484        if (-x <= boost::math::powm1(dist.success_fraction(), dist.successes(), Policy()))
 485        {  // q <= cdf(complement(dist, 0)) == pdf(dist, 0)
 486           return 0; //
 487        }
 488        if(x == 0)
 489        {  // Probability 1 - Q  == 1 so infinite failures to achieve certainty.
 490           // Would need +infinity failures for total confidence.
 491           result = policies::raise_overflow_error<RealType>(
 492              function,
 493              "Probability argument complement is 0, which implies infinite failures !", Policy());
 494           return result;
 495           // usually means return +std::numeric_limits<RealType>::infinity();
 496           // unless #define BOOST_MATH_THROW_ON_OVERFLOW_ERROR
 497        }
 498        // log(x) /log(1-success_fraction) -1; but use log1p in case success_fraction is small
 499        result = log(x) / boost::math::log1p(-success_fraction, Policy()) - 1;
 500       return result;
 501
 502     } // quantile complement
 503
 504  } // namespace math
 505 } // namespace boost
 506
 507 // This include must be at the end, *after* the accessors
 508 // for this distribution have been defined, in order to
 509 // keep compilers that support two-phase lookup happy.
 510 #include <boost/math/distributions/detail/derived_accessors.hpp>
 511
 512 #if defined (BOOST_MSVC)
 513 # pragma warning(pop)
 514 #endif
 515
 516 #endif // BOOST_MATH_SPECIAL_GEOMETRIC_HPP