4 ms·

> Produce a table of all possible sequences of length 1,000 with k heads and 1,000-k tails. This is more efficient than Von Neumann?

dmurray 5y ago
More efficient if coin flips are your scarce resource, less efficient if computation is scarce. But nowhere near as inefficient as it sounds - you don't actually have to materialize the table.
steerablesafe 5y ago
This method generates approximately log_2(sqrt(1/(2*pi*p*(1-p))) - 1000*log_2(p^p * (1-p)^(1-p)) bits of entropy from 1000 coin flips, where "p" is the probablity of flipping heads. Neumann's method generates 1000/(p(1-p)) bits of entropy from 1000 coin flips. The theoretical maximum is -1000*log_2(p^p * (1-p)^(1-p)) but it requires knowing "p" exactly. This method is close to the theoretical maximum. I didn't plug in numbers, or analyise further, but it's far better than Neumann's method. One obvious drawback is that you have to flip the coin a 1000 times to produce the first unbiased random bit, while Neumann's method starts producing bits much earlier.
- eru 5y ago
  > One obvious drawback is that you have to flip the coin a 1000 times to produce the first unbiased random bit, while Neumann's method starts producing bits much earlier. Definitely. Though you could fix that problem relatively easily. I think you might even be able to run von Neumann's method first, but store the coin flips; and then once you've got enough stored, extract a few more bits from the already used flips. Perhaps like this: When you do two flips, you add one of three possible tokens to your list: 'double-heads', 'double-tails' or 'mixed'. Crucially, you only store 'mixed' and not whether it was 'head-tails' or 'tails-heads' because that information was already used to produce the von-Neuman-bit. After your list has 1000 entries, you run an algorithm a bit like what I originally described to extract bits. The complication is that the table you construct has all possibilities of shuffling a fixed number of 'double-heads', 'double-tails' or 'mixed' tokens.
  - steerablesafe 5y ago
    It feels like an awkward middle ground. Like this method has a limited entropy output for the first 2000 coin flips (first 1000 double-heads/double-tails/mixed entries), and then suddenly it adds back a ton of lost entropy. An other commenter linked to some papers for asymptotically optimal entropy generation, I wonder if there is more of a streaming method there. It feels like there has to be, even maybe after a slow start. My naive intuition is that after 1000000 coin flips you have a good idea what p is, and then you can basically do arithmetic coding from there. Of course a theoretically correct method can't do exactly this, but it might asymptotically approach it.
    - eru 5y ago
      Oh, if you want something practical, the approach that Linux's /dev/random takes is probably the one to go. /dev/random being unbiased relies on some assumptions about cryptography; but in practice these assumptions are at least as well-founded as our assumption that our coin flips are independent. Look at some of the papers mentioned in other comments on this submission. There are (near) optimal streaming methods.
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
More efficient in how many flips you consume to produce an unbiased bit. Less efficient in terms of runtime (if you implement it as naively as I have described here).

dmurray 5y ago

More efficient if coin flips are your scarce resource, less efficient if computation is scarce. But nowhere near as inefficient as it sounds - you don't actually have to materialize the table.

steerablesafe 5y ago

This method generates approximately log_2(sqrt(1/(2*pi*p*(1-p))) - 1000*log_2(p^p * (1-p)^(1-p)) bits of entropy from 1000 coin flips, where "p" is the probablity of flipping heads. Neumann's method generates 1000/(p(1-p)) bits of entropy from 1000 coin flips. The theoretical maximum is -1000*log_2(p^p * (1-p)^(1-p)) but it requires knowing "p" exactly. This method is close to the theoretical maximum. I didn't plug in numbers, or analyise further, but it's far better than Neumann's method. One obvious drawback is that you have to flip the coin a 1000 times to produce the first unbiased random bit, while Neumann's method starts producing bits much earlier.

eru 5y ago
> One obvious drawback is that you have to flip the coin a 1000 times to produce the first unbiased random bit, while Neumann's method starts producing bits much earlier. Definitely. Though you could fix that problem relatively easily. I think you might even be able to run von Neumann's method first, but store the coin flips; and then once you've got enough stored, extract a few more bits from the already used flips. Perhaps like this: When you do two flips, you add one of three possible tokens to your list: 'double-heads', 'double-tails' or 'mixed'. Crucially, you only store 'mixed' and not whether it was 'head-tails' or 'tails-heads' because that information was already used to produce the von-Neuman-bit. After your list has 1000 entries, you run an algorithm a bit like what I originally described to extract bits. The complication is that the table you construct has all possibilities of shuffling a fixed number of 'double-heads', 'double-tails' or 'mixed' tokens.
- steerablesafe 5y ago
  It feels like an awkward middle ground. Like this method has a limited entropy output for the first 2000 coin flips (first 1000 double-heads/double-tails/mixed entries), and then suddenly it adds back a ton of lost entropy. An other commenter linked to some papers for asymptotically optimal entropy generation, I wonder if there is more of a streaming method there. It feels like there has to be, even maybe after a slow start. My naive intuition is that after 1000000 coin flips you have a good idea what p is, and then you can basically do arithmetic coding from there. Of course a theoretically correct method can't do exactly this, but it might asymptotically approach it.
  - eru 5y ago
    Oh, if you want something practical, the approach that Linux's /dev/random takes is probably the one to go. /dev/random being unbiased relies on some assumptions about cryptography; but in practice these assumptions are at least as well-founded as our assumption that our coin flips are independent. Look at some of the papers mentioned in other comments on this submission. There are (near) optimal streaming methods.

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

More efficient in how many flips you consume to produce an unbiased bit. Less efficient in terms of runtime (if you implement it as naively as I have described here).