Function malachite_base::num::random::geometric::geometric_random_signed_range

pub fn geometric_random_signed_range<T: PrimitiveSigned>(
    seed: Seed, 
    a: T, 
    b: T, 
    abs_um_numerator: u64, 
    abs_um_denominator: u64
) -> GeometricRandomSignedRange<T>

Generates random signed integers from a modified geometric distribution over the half-open interval $[a, b)$.

With this distribution, the probability of a value being generated decreases as its absolute value increases. The probabilities $P(n), P(n + \operatorname{sgn}(n)), P(n + 2\operatorname{sgn}(n)), \ldots$, where $n, n + \operatorname{sgn}(n), n + 2\operatorname{sgn}(n), \ldots \in [a, b) \setminus \{0\}$, decrease in a geometric sequence; that’s where the “geometric” comes from.

The form of the distribution depends on the range. If $a \geq 0$, the distribution is highest at $a$ and is truncated at $b$. If $b \leq 1$, the distribution is reflected: it is highest at $b - 1$ and is truncated at $a$. Otherwise, the interval includes both positive and negative values. In that case the distribution is doubled: it is highest at zero and is truncated at $a$ and $b$.

The probabilities can drop more quickly or more slowly depending on a parameter $m_u$, called the unadjusted mean. It is equal to abs_um_numerator / abs_um_denominator. The unadjusted mean is what the mean of the absolute values of the generated values 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 of the absolute values. 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 abs_um_numerator + abs_um_denominator.

Here is a more precise characterization of this distribution. Let its support $S \subset \Z$ equal $[a, b)$. Let $c = \min_{n\in S}|n|$. Geometric distributions are typically parametrized by a parameter $p$. The relationship between $p$ and $m_u$ is $m_u = \frac{1}{p} + c - 1$, or $p = \frac{1}{m_u - c + 1}$. Then we have $$ P(n) \neq 0 \leftrightarrow n \in S $$ If $0, 1 \in S$, then $$ \frac{P(0)}{P(1)} = \frac{m_u + 1}{m_u}. $$ If $-1, 0 \in S$, then $$ \frac{P(0)}{P(-1)} = \frac{m_u + 1}{m_u}. $$ and whenever $n, n + \operatorname{sgn}(n) \in S \setminus \{0\}$, $$ \frac{P(n)}{P(n+\operatorname{sgn}(n))} = \frac{m_u + 1}{m_u}. $$

As a corollary, $P(n) = P(-n)$ whenever $n, -n \in S$.

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_signed_range;
use malachite_base::random::EXAMPLE_SEED;

assert_eq!(
    prefix_to_string(geometric_random_signed_range::<i8>(EXAMPLE_SEED, -100, 100, 30, 1), 10),
    "[-32, -31, -88, 52, -40, 64, -36, -1, -7, 46, ...]"
)

Further details

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