3 ms·
I don't see how this works. > The index of that position is a uniform random integer in a range from 1 to the size of the table. Use your favourite method to e
by aqme28 5y ago
I don't see how this works.
> The index of that position is a uniform random integer in a range from 1 to the size of the table. Use your favourite method to extract unbiased bits from that unbiased integer.
Why is that position unbiased and random? If I'm using a coin that produces heads every single time, then I'm always going to land on table position 0, so therefore the table index is biased.
- deleted 5y ago[deleted]
- eru 5y agoWell, if your coin always lands heads, your table will only have a single entry. So you won't extract any bits from it. Von Neumann's method won't extract any randomness from this coin either. Do keep in mind that, crucially, you only build the table _after_ you figured out how many heads or tails you got in this particular instance of 1000 flips. The randomness we extract is not in how _many_ heads or tails we got, but how those heads and tails are shuffled in your sequence. For the math, have a look at https://news.ycombinator.com/item?id=30697559 https://news.ycombinator.com/item?id=30697559
- aqme28 5y agoI misinterpreted your algorithm. So you're creating a table of all permutations given the number of heads and tails you got, and then looking it up in the table. This does feel like a generalization of Von Neumann's method from 2 tosses to 1000
- eru 5y agoYes, you can view it like that. Basically we have 1001 tables, for each amount of heads that are possible. If you are sufficiently clever, you can generalize it to an indefinite stream of tosses, and produce output as you go along. See some of the papers mentioned elsewhere in the comments.