3 ms·

Nonsense. It requires roughly 1+log(10) bits in expectation and has a geometric tail.

• FabHK 7y ago
  Eh? 4 bits minimum to get a uniform 1-16, and each bit requires requires 2 numbers that are not identical. (Ah yeah, I thought that in turn requires a bit more than 4 numbers, but it requires only a bit more than 2 numbers (probability that numbers coincide is not 1/2, as with bits, but 1/10, or a bit more than that due to non-uniformity)). Thus, I recant "around 20, 40, 60 or more" and replace it by "around 9, 18, 27 or more" numbers. Probability that you have to reject any resulting hex digit is obviously 3/8.
  • frankmcsherry 7y ago
    Rejection sampling isn't the best way to go. With b bits you are subdividing the (0,1) interval into 2^b regions, and only need more bits if one of the 9 multiples of 0.1 land in the interval you've picked. As b increases this probability drops exponentially. It's a fair point that the number of "numbers" depends on how low the entropy of the source is, but in the link the probability of collision wasn't massive.
    • FabHK 7y ago
      But the original post described rejection sampling (once you got your bits from the larger/smaller trick).
      • frankmcsherry 7y ago
        Absolutely! I read the von Neumann extractor and presumed too much. For fun, you can reduce the numbers asked by getting a batch of k people, and if all numbers are dissimilar you get a draw from k! The OP is silly though; if you know the distribution there are way better techniques. They don't seem to worry about how they measure it.