How to create a uniform distribution over multiple n bits?
Assuming I can generate random data bytes, how can I use this to select an item from an array of items n
?
If I have 256 elements, I can generate 1 byte of entropy (8 bits) and then use that to select my element, simply converting it to an integer.
If I have 2 items, I can generate 1 byte, discard 7 bits, and use the remaining bit to select my item.
But what if I have 3 items? 1 bit is too small and 2 is too many. How would I randomly choose 1 of 3 items with equal probability?
source to share
You can generate the correct distribution by simply truncating to the desired range. If you have N elements, just generate ceiling(log(N))=K
random bits. This is inefficient, but still works as long as the K bit is randomly generated.
In your example where you have N = 3, you need at least K = 2 bits, you have the following results [00, 01, 10, 11] with equal probability. To map this to the correct range, simply ignore one of the results, like the last one. Think about it by creating a new joint probability distribution p (x_1, x_2) over two bits, where p (x_1 = 1, x_2 = 1) = 0, while for each of the others it will be 1/3 due to the renormalization ( i.e. (1/4) / (3/4) = 1/3).
source to share