Details
-
Task
-
Status: Open
-
Minor
-
Resolution: Unresolved
-
1.0
-
None
-
None
-
Easy
Description
The default inverse probability implementation for the discrete distributions uses a simple bisection search within an initial bracket. Bracketing is based on the mean and variance of the distribution and the input p-value.
The worst case scenario is a bracket between Integer min and max value (range 2^32 -1). A bisection search would require 32 iterations to find the value x for input probability p.
// Range [a, b] max = log2(b - a)
The following distributions are currently in the library:
| Distribution | a | b | Notes |
|---|---|---|---|
| Binomial(n, p) | 0 | n | |
| Geometric(p) | 0 | infinity | Inverted using a formula |
| Hypergeometric(N, K, n) | max(0, n+K-N) | min(n, k) | |
| Pascal(n, p) | 0 | infinity | Negative binomial distribution |
| Poisson(mu) | 0 | infinity | |
| Uniform(a, b) | a | b | Inverted using a formula |
| Zipf(N, s) | 1 | N |
For several of the distributions the range is limited by the parameters. Notable exceptions are the Pascal and Poisson distribution. An investigation should be made to determine the number of iterations required for inversion and whether this can be improved.