Function malachite_base::num::random::geometric::geometric_random_unsigned_inclusive_range

pub fn geometric_random_unsigned_inclusive_range<T: PrimitiveUnsigned>(
    seed: Seed,
    a: T,
    b: T,
    um_numerator: u64,
    um_denominator: u64
) -> GeometricRandomNaturalValues<T> 

Generates random unsigned integers from a truncated geometric distribution over the closed interval $[a, b]$.

With this distribution, the probability of a value being generated decreases as the value increases. The probabilities $P(a), P(a + 1), P(a + 2), \ldots$ decrease in a geometric sequence; that’s where the “geometric” comes from. Unlike a true geometric distribution, this distribution is truncated, meaning that values above $b$ are never generated.

The probabilities can drop more quickly or more slowly depending on a parameter $m_u$, called the unadjusted mean. It is equal to um_numerator / um_denominator. The unadjusted mean is what the mean generated value would be if the distribution were not truncated. If $m_u$ is significantly lower than $b$, then it is very close to the actual mean. The higher $m_u$ is, the more gently the probabilities drop; the lower it is, the more quickly they drop. $m_u$ must be greater than $a$. It may be arbitrarily high, but note that the iteration time increases linearly with um_numerator + um_denominator.

Here is a more precise characterization of this distribution. Let its support $S \subset \Z$ equal $[a, b]$. Then we have $$ P(n) \neq 0 \leftrightarrow n \in S $$

and whenever $n, n + 1 \in S$, $$ \frac{P(n)}{P(n+1)} = \frac{m_u + 1}{m_u}. $$

The output length is infinite.

Expected complexity per iteration

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ = um_numerator + um_denominator.

Panics

Panics if $a \geq b$, if um_numerator or um_denominator are zero, if their ratio is less than or equal to $a$, or if they are too large and manipulating them leads to arithmetic overflow.

Examples

use malachite_base::iterators::prefix_to_string;
use malachite_base::num::random::geometric::geometric_random_unsigned_inclusive_range;
use malachite_base::random::EXAMPLE_SEED;

assert_eq!(
    prefix_to_string(
        geometric_random_unsigned_inclusive_range::<u16>(EXAMPLE_SEED, 1, 6, 3, 1),
        10
    ),
    "[2, 5, 2, 3, 4, 2, 5, 6, 1, 2, ...]"
)

Further details

Geometric distributions are more typically parametrized by a parameter $p$. The relationship between $p$ and $m_u$ is $m_u = \frac{1}{p} + a - 1$, or $p = \frac{1}{m_u - a + 1}$.

The probability mass function of this distribution is $$ P(n) = \begin{cases} \frac{(1-p)^np}{(1-p)^a-(1-p)^{b+1}} & \text{if} \quad a \leq n \leq b, \\ 0 & \text{otherwise}. \end{cases} $$