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

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?

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?

• Hi Paul! Many thanks for your answer ! My scenario is somewhat very-high-speed and hardware-contrived :-) More to come ... Mar 24, 2013 at 10:59
• What did this become in the end? Apr 11, 2021 at 1:45
• Frankly, I don't remember the origin of that question. For sure, it occured in the context of the development of the high-performance QKD engine described in iopscience.iop.org/article/10.1088/1367-2630/16/1/013047/meta, and I am pretty sure we did not implement such a "biasing" algorithm, but I cannot remember why we were considering this possibility. Sorry about that! Apr 17, 2021 at 12:20
• Fair enough, it has been eight years :) Apr 18, 2021 at 21:32

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.

• Using a TRNG or a CPRNG for the initial source of randomness is out of scope for my question. Thank you for your proposal. Still, you decimate the initial source by a factor of two, while we could expect to ... expand the throughput in the best case! Feb 27, 2013 at 19:20
• If you're worried about floating point behaviour, pass in a rational rather than a float! Mar 22, 2013 at 8:48
• @PaulCrowley: actually, it would appear to me that this algorithm is extremely FP friendly; with IEEE math, I believe it treats the input bias as a precise rational; the only operation that can get a rounding error is the 'bias = bias-1', and that can happen only if 'bias < 0.5' entering that step, in that case, we output 0, and so the rounding error is irrelevant. (Oh, and "Hi, Paul!") Mar 22, 2013 at 14:58
• Hey :) You're right, the algorithm is FP friendly! But 1/5 can't be represented exactly in FP, which could introduce a small error. Mar 22, 2013 at 22:21
• @Poncho: indeed the algorithm as given in your answer is FP-friendly, and my "improvement" is not one; on the contrary: 2*bias-1 is more (not less, as I mistakenly thought) numerically stable than bias+(bias-1) is. Oups! Fixed my alternative.
– fgrieu
Mar 23, 2013 at 7:38