Function malachite_base::num::random::geometric::geometric_random_nonzero_signeds

pub fn geometric_random_nonzero_signeds<T: PrimitiveSigned>(
    seed: Seed, 
    abs_um_numerator: u64, 
    abs_um_denominator: u64
) -> GeometricRandomNonzeroSigneds<T>

Generates random nonzero signed integers from a modified geometric distribution.

This distribution can be derived from a truncated geometric distribution by mirroring it, producing a truncated double geometric distribution. Zero is excluded.

With this distribution, the probability of a value being generated decreases as its absolute value increases. The probabilities $P(\pm 1), P(\pm 2), P(\pm 3), \ldots$ decrease in a geometric sequence; that’s where the “geometric” comes from. Values below T::MIN or above T::MAX 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 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 T::MAX, which is usually the case, 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 one. 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 $[-2^{W-1}, 2^{W-1}) \setminus \{0\}$, where $W$ is the width of the type`. Then we have $$ P(n) \neq 0 \leftrightarrow n \in S $$ $$ P(1) = P(-1) $$ Whenever $n > 0$ and $n, n + 1 \in S$, $$ \frac{P(n)}{P(n+1)} = \frac{m_u}{m_u - 1}, $$ and whenever $n < 0$ and $n, n - 1 \in S$, $$ \frac{P(n)}{P(n-1)} = \frac{m_u}{m_u - 1}. $$

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$ = abs_um_numerator + abs_um_denominator.

Panics

Panics if abs_um_denominator is zero or if abs_um_numerator <= abs_um_denominator.

Examples

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

assert_eq!(
    prefix_to_string(geometric_random_nonzero_signeds::<i64>(EXAMPLE_SEED, 2, 1), 10),
    "[-2, -2, -2, 2, -3, 2, -1, -1, -1, 1, ...]"
)

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}$, or $p = \frac{1}{m_u}$.

The probability mass function of this distribution is $$ P(n) = \begin{cases} \frac{(1-p)^{|n|}p}{(1-p)^{2^{W-1}}(p-2)-2p+2} & \text{if} \quad -2^{W-1} \leq n < 0 \ \mathrm{or} \ 0 < n < -2^{W-1}, \\ 0 & \text{otherwise}, \end{cases} $$ where $W$ is the width of the type.

It’s also useful to note that $$ \lim_{W \to \infty} P(n) = \begin{cases} \frac{(1-p)^{|n|}p}{2-2p} & \text{if} \quad n \neq 0, \\ 0 & \text{otherwise}. \end{cases} $$