# 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?

-
Actually an output bit has only 0.72 bits of entropy. – CodesInChaos Feb 27 '13 at 18:56
Is rejection sampling the only way to get a truly uniform distribution of random numbers? has an elementary but incomplete answer. – Gilles Mar 25 '13 at 12:01

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 ... – cryptopathe Mar 24 '13 at 10:59

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! – cryptopathe Feb 27 '13 at 19:20
If you're worried about floating point behaviour, pass in a rational rather than a float! – Paul Crowley Mar 22 '13 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!") – poncho Mar 22 '13 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. – Paul Crowley Mar 22 '13 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 '13 at 7:38