Module malachite_base::num::random::striped

Expand description

Iterators that generate primitive integers that tend to have long runs of binary 0s and 1s.

Integers with long runs of 0s and 1s are good for testing; they’re more likely to result in carries and borrows than uniformly random integers. This idea was inspired by GMP’s mpz_rrandomb function, although striped integer generators are more general: they can also produce integers with runs that are shorter than average, so that they tend to contain alternating bits like $1010101$.

Let the average length of a run of 0s and 1s be $m$. The functions in this module allow the user to specify a rational $m$ through the parameters m_numerator and m_denominator. Since any binary sequence has an average run length of at least 1, $m$ must be at least 1; but if it is exactly 1 then the sequence is strictly alternating and no longer random, so 1 is not allowed either. if $m$ is between 1 and 2, the sequence is less likely to have two equal adjacent bits than a uniformly random sequence. If $m$ is 2, the sequence is uniformly random. If $m$ is greater than 2 (the most useful case), the sequence tends to have long runs of 0s and 1s.

Details

A random striped sequence with parameter $m \geq 1$ is an infinite sequence of bits, defined as follows. The first bit is 0 or 1 with equal probability. Every subsequent bit has a $1/m$ probability of being different than the preceding bit. Notice that every sequence has an equal probability as its negation. Also, if $m > 1$, any sequence has a nonzero probability of occurring.

$m=1$ is disallowed. If it were allowed, the sequence would be either $01010101010101010101\ldots$ or $10101010101010101010\ldots$.
If $1<m<2$, the sequence tends to alternate between 0 and 1 more often than a uniformly random sequence. A sample sequence with $m=33/32$ is $1010101010101010101010110101010101010101\ldots$.
If $m=2$, the sequence is uniformly random. A sample sequence with $m=2$ is $1100110001101010100101101001000001100001\ldots$.
If $m>2$, the sequence tends to have longer runs of 0s and 1s than a uniformly random sequence. A sample sequence with $m=32$ is $1111111111111111110000000011111111111111\ldots$.

An alternative way to generate a striped sequence is to start with 0 or 1 with equal probability and then determine the length of each block of equal bits using a geometric distribution with mean $m$. In practice, this isn’t any more efficient than the naive algorithm.

We can generate a random striped unsigned integer of type T by taking the first $W$ bits of a striped sequence. Fixing the parameter $m$ defines a distribution over Ts. A few things can be said about the probability $P_m(n)$ of an unsigned integer $n$ of width $W$ being generated:

$P_m(n) = P_m(\lnot n)$
$P_m(0) = P_m(2^W-1) = \frac{1}{2} \left ( 1-\frac{1}{m} \right )^{W-1}$. If $m>2$, this is the maximum probability achieved; if $m<2$, the minimum.
$P_m(\lfloor 2^W/3 \rfloor) = P_m(\lfloor 2^{W+1}/3 \rfloor) = 1/(2m^{W-1})$. If $m>2$, this is the minimum probability achieved; if $m<2$, the maximum.
Because of these distributions’ symmetry, their mean is $(2^W-1)/2$ and their skewness is 0. It’s hard to say anything about their standard deviations or excess kurtoses, although these can be computed quickly for specific values of $m$ when $W$ is 8 or 16.

We can similarly generate random striped signed integers of width $W$. The sign bit is chosen uniformly, and the remaining $W-1$ are taken from a striped sequence.

To generate striped integers from a range, the integers are constructed one bit at a time. Some bits are forced; they must be 0 or 1 in order for the final integer to be within the specified range. If a bit is not forced, it is different from the preceding bit with probability $1/m$.