[FoRK] low probability bits

Damien Morton dmorton at bitfurnace.com
Sun Feb 22 21:38:40 PST 2009


On Mon, Feb 23, 2009 at 12:58 PM, Stephen Williams <sdw at lig.net> wrote:

> What do you mean by low probability bits?
> What do you mean by Pr()?  What scale is .5 on?
>
> You are not being clear.
>
> sdw


Well, normally in a random bitstream, you want Pr(1) to be 0.5, i.e. about
half the bits are 1 and half are 0.

I am looking to generate a bitstream where Pr(1) < 0.5; could be 0.4, could
be 0.03333.

The normal way to do this would be to generate a full random number, test
randFloat() < Pr(1), emit a 1 or 0 as appropriate, and repeat for each bit
you want to emit.

Wondering if anyone has ever come across a random number generator that
generates bitstreams directly - i.e. some combination of simple/efficient
operations that will generate a number with an average proportion of 1 bits
equal to Pr(1), which is less than 0.5.

To save myself from having to go around and generate a full random float for
each bit emitted, I could quantize the probabilities to n bits and use
chunks of n bits for each bit emitted.

For a bitstream of size N, with Pr(1)=p, there is some number of
permutations of p*N 1s and (1-p) 0s - with the number of permutations equal
to P, I would need log2(P) bits to specify that permutation. for Pr(1) <<
0.5, P would be something like N^(p*N), and the bits needed would be
log2(N^(p*N)) ~= O(p*N*log(N)), i think.

i.e. to generate 100 bits where Pr(1) = 0.01, I should only need to generate
a few actual random bits, er, actually, only ~7 random bits in that case :)

Ok, I have it now. I think. The key is to generate bit positions, either as
deltas from the current position, or absolutes into a bucket. Alternatively,
generate permutations of sets of bits with the correct probability.


More information about the FoRK mailing list