Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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?

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
2  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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