[FoRK] low probability bits

Stephen Williams sdw at lig.net
Mon Feb 23 00:35:51 PST 2009


Damien Morton wrote:
> 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.
>   
Create an array with number of bits equal to N+M where N / M is an 
accurate enough rational approximation of the desired probability.  Make 
N bits randomly 1's.  Sample B bits from the random stream where B is 
math.ceil(math.log(N+M, 2)) bits.  J=B%(N+M), ProbOne = oneArray[J].  
Still getting bits one at a time, however you can make use of all of the 
random bits you have.

> 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.
>   

That could work, although it seems you will likely overestimate the 
probability of a bit being 1 for low probabilities.  For instance, with 
Pr(.01), there are some groups of 100 bits that will have no 1 bits, 
given a real random source.  I suppose probability strictness is an 
important parameter.

Assuming that fixed, perhaps ideal percentages of 1 bits is desired, 
and/or assuming that randomness is expensive, you could create a 
black/white N+M array as above, then use random information to scramble it.

sdw



More information about the FoRK mailing list