How to generate a random integer in the range [0, n] from a stream of random bits without losing bits?

Question

I have a stream of (uniform) random bits from which I would like to generate random integers uniformly in the range [0, n] without bit loss. (I consider wasted bits that exceed the floor (log_2 (n)) + 1, based on the assumption that no more than that can always be used.) For example, if n = 5, then the search algorithm I should use is no more than three bits . How can I do that?

Answer 1

This is equivalent to detecting a two-way function between two sets of different (final) power. It's impossible.

Answer 2

Although your question description shows a fixed number of bits per random number generated by your header, no. So I'm going to add here that on average you can create a random number with the number of bits that you specify plus half-bit. The algorithm below takes a variable number of bits for values ​​of n not divisible by 2, but the average bit that it will consume is floor (log_2 (n)) + 1.5 .

Standard implementations of a function to generate an integer in a range use% (modulo) on a large random number. This discards the bits and will not produce a mathematically accurate random distribution unless it is reused for some values ​​of a large random number. The following algorithm creates a true random distribution and will not be an empty bit. (Or rather, I don’t see an obvious way to reduce the number of bits that it consumes. Perhaps some kind of entropy can be restored from "too large" attachments.)

# Generate a number from 0 to n inclusive without wasting bits. function RandomInteger(n) if n <= 0 error else i = Floor(Log2(n)) x = i r = 0 while x >= 0 r = r + (2 ^ x) * NextRandomBit() if r > n # Selected number too large so begin again. x = ir = 0 else # Still in range. Calculate the next bit. x = x - 1 return r 

The algorithm above is written for clarity, not speed. This would be very fast if rewritten to process several bits at once.

Answer 3

It seems you could just take the bit x = ceil (log_2 (n)) at a time, and just use them as your random numbers. The problem you will encounter is that if the number you get is more than your limit (for example, 5), then you will want to do the magic to get it less than 5, but evenly. In this case, it is logical to assume that you just take a few more bits, but since you indicated that we cannot spend bits, then we need to be more creative. I would recommend a right or left turn, but this will not always lead you out of the situation. (Consider a row of 111 when you need n = 5). We could make up x rotate to see if one of the rotations falls into the correct range, or we could just flip all the bits and add 1 (two additions). I believe this will make it homogeneous.

So, for example, if you had the following line (the rightmost bit is the first one you get):

101001111010010101

And you use n = 5, then ceil (log2 (n)) = 3, so you will use three bits at a time, and the following results will be (at each step):

 t=0 : 101 = 5 t=1: 010 = 2 t=2: 010 = 2 t=3: 111 = 7 -> too large, rotates won't work, so we use 2 complement: 001 = 1 t=4: 001 = 1 t=5: 101 = 5 

Answer 4

First, find out the number of possible values ​​that you want to generate. In the case of integers in the range 0..5, these are 6 values. They can be represented in the ceil (log (6) / log (2)) bits.

 // in C++ std::bitset< 3 > bits; // fill the bitset // interpret as a number long value = bits.to_ulong(); 

Then find the conversion from n-bits to the final presentation format: it needs to be scaled from the range [0..2 ^N ] to the range [from, to]:

 double out_from=-1, out_to=5; double in_from=0, in_to = std::bitset<3>().flip().to_ulong(); double factor = (out_to-out_from)/(in_to-in_from) double constant = out_from - in_from; double rescaled = in_value * scale + constant; long out = floor( rescaled );