Function malachite_base::num::random::geometric::geometric_random_unsigneds
source · [−]pub fn geometric_random_unsigneds<T: PrimitiveUnsigned>(
seed: Seed,
um_numerator: u64,
um_denominator: u64
) -> GeometricRandomNaturalValues<T>ⓘNotable traits for GeometricRandomNaturalValues<T>impl<T: PrimitiveInt> Iterator for GeometricRandomNaturalValues<T> type Item = T;
Expand description
Generates random unsigned integers from a truncated geometric distribution.
With this distribution, the probability of a value being generated decreases as the value
increases. The probabilities $P(0), P(1), P(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 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 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 T::MAX
, which is usually the case, 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 zero. 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 $[0, 2^W)$, where $W$ is the width of the type. 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 um_numerator
or um_denominator
are zero, or, if after being reduced to lowest
terms, their sum is greater than or equal to $2^{64}$.
Examples
use malachite_base::iterators::prefix_to_string;
use malachite_base::num::random::geometric::geometric_random_unsigneds;
use malachite_base::random::EXAMPLE_SEED;
assert_eq!(
prefix_to_string(geometric_random_unsigneds::<u64>(EXAMPLE_SEED, 1, 1), 10),
"[1, 0, 0, 3, 4, 4, 1, 0, 0, 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} - 1$, or $p = \frac{1}{m_u + 1}$.
The probability mass function of this distribution is $$ P(n) = \begin{cases} \frac{(1-p)^np}{1-(1-p)^{2^W}} & \text{if} \quad 0 \leq n < 2^W, \\ 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) = (1-p)^np. $$