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?


2 Answers 2


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?

  • $\begingroup$ Hi Paul! Many thanks for your answer ! My scenario is somewhat very-high-speed and hardware-contrived :-) More to come ... $\endgroup$ Mar 24, 2013 at 10:59
  • $\begingroup$ What did this become in the end? $\endgroup$ Apr 11, 2021 at 1:45
  • $\begingroup$ 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! $\endgroup$ Apr 17, 2021 at 12:20
  • $\begingroup$ Fair enough, it has been eight years :) $\endgroup$ 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.

  • $\begingroup$ 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! $\endgroup$ Feb 27, 2013 at 19:20
  • $\begingroup$ If you're worried about floating point behaviour, pass in a rational rather than a float! $\endgroup$ Mar 22, 2013 at 8:48
  • 2
    $\begingroup$ @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!") $\endgroup$
    – poncho
    Mar 22, 2013 at 14:58
  • $\begingroup$ 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. $\endgroup$ Mar 22, 2013 at 22:21
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Mar 23, 2013 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.