undefined | Better HN

0 pointsfrankmcsherry6y ago0 comments

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

0 comments

3 comments · 1 top-level

FabHK6y ago· 2 in thread

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.

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

FabHK6y ago

But the original post described rejection sampling (once you got your bits from the larger/smaller trick).

1 more reply

j / k navigate · click thread line to collapse