4 ms·

As with so many algorithms, he's trading compute time for memory and pre-compute time. Generating that table is costly, but once you have that table it's pretty

by aqme28 5y ago

As with so many algorithms, he's trading compute time for memory and pre-compute time. Generating that table is costly, but once you have that table it's pretty efficient.

eru 5y ago
Yes. Though in practice you wouldn't want to generate that specific table for 1000 flips. It's far too big.
SilasX 5y ago
You don’t need to store a big table with the table method, though. As long as there’s a pattern to it, you can figure out your position algorithmically. For example, if H=1 and T=0 then you do something like “any result above 11010 is a real heads, others are tails.” Edit: never mind, that’s a different method than OP. (Doesn’t require exactly k heads.) Doesn’t it get the best of both worlds though? Edit2: Double never-mind, the problem assumes you don’t know the level of bias. But I think the OP threw that out as well.
- eru 5y ago
  The method I described it a bit weird and round-about, exactly because it has to work around not knowing the bias. Essentially, it generates a thousand flips, and then carefully extracts the randomness only out of how those flips are shuffled, but now how many heads there are. However, the closer to 500/500 your distribution is, the more entropy the method I describes can extract. Conversely, if you randomly hit 1000 heads and 0 tails, the method can't extract anything, and you'll have to sample again. In contrast, a method that knows the bias and can exploit it, can extract the same number of random bits, no matter what you actually flipped. Eg in the special case of a known unbiased coin, you always get 1000 random bits for 1000 flips. Even if those flips happen to be 1000 heads.
  - SilasX 5y ago
    But the point remains, your method shouldn’t need a full table cached in advance, right? You should be able to use a formula to compute its “effective index”.
    - eru 5y ago
      Yes, definitely. I just didn't mention that, because I thought it was obvious that we agree on that. And instead of computing the "effective index" as an abstract number and then extract bits from that, you can work out directly how to generate the unbiased bits.

by aqme28 5y ago

As with so many algorithms, he's trading compute time for memory and pre-compute time. Generating that table is costly, but once you have that table it's pretty efficient.

eru 5y ago

Yes. Though in practice you wouldn't want to generate that specific table for 1000 flips. It's far too big.

SilasX 5y ago

You don’t need to store a big table with the table method, though. As long as there’s a pattern to it, you can figure out your position algorithmically. For example, if H=1 and T=0 then you do something like “any result above 11010 is a real heads, others are tails.” Edit: never mind, that’s a different method than OP. (Doesn’t require exactly k heads.) Doesn’t it get the best of both worlds though? Edit2: Double never-mind, the problem assumes you don’t know the level of bias. But I think the OP threw that out as well.

eru 5y ago
The method I described it a bit weird and round-about, exactly because it has to work around not knowing the bias. Essentially, it generates a thousand flips, and then carefully extracts the randomness only out of how those flips are shuffled, but now how many heads there are. However, the closer to 500/500 your distribution is, the more entropy the method I describes can extract. Conversely, if you randomly hit 1000 heads and 0 tails, the method can't extract anything, and you'll have to sample again. In contrast, a method that knows the bias and can exploit it, can extract the same number of random bits, no matter what you actually flipped. Eg in the special case of a known unbiased coin, you always get 1000 random bits for 1000 flips. Even if those flips happen to be 1000 heads.
- SilasX 5y ago
  But the point remains, your method shouldn’t need a full table cached in advance, right? You should be able to use a formula to compute its “effective index”.
  - eru 5y ago
    Yes, definitely. I just didn't mention that, because I thought it was obvious that we agree on that. And instead of computing the "effective index" as an abstract number and then extract bits from that, you can work out directly how to generate the unbiased bits.