How to efficiently generate a stream of independent, but biased random bits?

Question

Usually, in cryptography, one is interested in debiasing a stream of independent (true) random bits, and several algorithms exist to do this. What about the converse? Let's assume I have a stream of independent and unbiased random bits at my disposal, and that I would like to generate a stream of statistically independent bits, but where $\Pr[B=0] = \frac{1}{5}$, say. How do I do this without sacrificing too much entropy from the initial source? A common algorithm for this precise case would consist in drawing $3$ bits, and interpret them as a number $0 \leq a \leq 7$. If $a=0$, then output $0$, else if $a < 5$, then output $1$, else output nothing. The problem is that I will sacrifice a lot of entropy: with probability $\frac{1}{4}$, I discard 3 bits, and with probability $\frac{3}{4}$, I transform 3 bits of entropy into a single one. Are you aware of a less entropy-hungry method?

Answer 1

If you want an answer that is maximally efficient in consuming a stream of random bits, then you need a decoder for arithmetic encoding. However if you're using a moderately fast CSPRNG, why would you sacrifice extra clock cycles to squeeze all the biased bits you can from each unbiased bit?

Answer 2

If you want a more efficient algorithm, how about:

int biased_bit(double bias) {
    for (;;) {
        bias = 2 * bias;
        if (get_random_bit() == 0) {
            bias = bias - 1;
            if (bias <= 0) return 0;
        } else {
            if (bias >= 1) return 1;
        }
    }
}

Assuming that get_random_bit() returns uniformly distributed, independent random bits, and assuming that $0 \le bias \le 1$, then this returns a 1 with probability $bias$, and 0 with probability $1-bias$. This uses an expected 2 bits input per biased output bit (except for cases where the bias is $a/2^{b}$ for integer $a, b$; in that case, the expected number of bits used is less). In contrast, the technique you stated would take (for $bias = \frac{1}{5}$) an expected 4.8 bits input per biased output bit.

On the other hand, I would disagree with your original premise; you can get unbiased, independently distributed random bits cheaply using an efficient CSPRNG. Yes, a computationally unbounded adversary can distinguish them from random; unless your attacker falls in that category, you can ignore that distinction.