8 ms·

If I give you a biased coin can you simulate a truly random coin flip with it? The answer turns out to be yes. Flip the biased coin twice: HT = heads, TH = tail

by antics 1y ago

If I give you a biased coin can you simulate a truly random coin flip with it? The answer turns out to be yes. Flip the biased coin twice: HT = heads, TH = tails, and HH/TT = flip twice again. The general study of such things is called “randomness extractors”. The new Gödel prize goes to this paper which shows how to extract a nearly perfect random bit out of two sources with low min-entropy.

deleted 1y ago
[deleted]
falcor84 1y ago
Yes, but - you need to replace "twice" there with "an unbounded number of times". If you apply this in an environment where the biased coin is coming from an external source, your system becomes susceptible to DoS attacks.
- pasquinelli 1y ago
  i read "flip twice" as recussion, so, given we're talking randomness, yes, that could go on forever. but i don't think you really need to replace "twice."
- antics 1y ago
  While I obviously think randomness extractors over adversarial sources are very interesting, I think talking about them specifically in this example complicates the point I'm trying to make, which is that it's incredible it can be done at all.
  - dataflow 1y ago
    Note that adversarial is kind of a red herring, not sure why they mentioned that. The number of flips is unbounded regardless. Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed. I realize this sounds like a minor detail to someone who finds this cool (and so do I), but I don't think it is. It's kind of frustrating to be told that your intuition is wrong by someone smarter than you, when your intuition is actually correct and the experts are moving the goalposts. IMO, it makes people lose respect for experts/authority.
    - dwattttt 1y ago
      I don't think anyone would be surprised to hear that if a biased coin can only give one result, you can't extract randomness from it. And if it can only give the second result one in a million times, you could be flipping millions.
    - QuesnayJr 1y ago
      I have the exact opposite reaction, that if someone told me the answer is "no" because it requires an unbounded number of coin flips that they were the ones trying to bullshit me. In antic's formulation, nothing is said about requiring a bounded number of flips.
      - dataflow 1y ago
        "Simulate a truly random coin" implies it IMO. You're not simulating a truly random coin if you need unbounded time for a single flip. The truly random coin definitely doesn't need that. It just feels like a scam if someone sold me such a machine with that description - I'd want my money back. I don't expect everyone would feel the same, but I think a lot of people would.
        dooglius 1y ago
        A real coin could repeatedly land on its side over and over indefinitely, every time you flipped it.
        thaumasiotes 1y ago
        You don't need unbounded time for a single flip, that's all in your imagination. The worst-case time is unbounded, but you can't achieve the worst case.
        falcor84 1y ago
        It's very easy to achieve if someone hands you a "coin" that is made such that it never lands on tails. Sorry for still being in the adversarial mindset, but this means that you essentially have to hardcode a maximum number of same-side flips after which you stop trusting the coin.
pbhjpbhj 1y ago
Speaking from complete ignorance, with apologies to those who that will annoy: I'm sure it's possible to make a coin with what one might term "complex bias" where the bias extends over two events (thick gloop inside the coin, possibly heat activated or non-Newtonian). This method sounds like the bias needs to be fixed ("simple bias" if you like)? I guess that's just out of scope here. Aside: There's a strong 'vibe' that HHHH HHHH with a single coin is somehow less random than HTHTHTHT HTHTHTHT with two coins when discarding HH and TT. I wonder what the origin of that feeling is - maybe just HT doesn't seem like it's a constant result simply due to nomenclature? If we call HT "type-A", then we just have HHHH HHHH vs. AAAA AAAA; and I _feel_ happier about the result!
- lovecg 1y ago
  Could the vibe be due to the fact that HHHH… seems like the coin could not just be biased - it could be completely broken and come up heads every time. There are two distinct possibilities here: 1) the coin is broken and is always H 2) the coin is random or possibly biased, and you got a string of H by chance And observing the string of H… increases the probability of 1) in the Bayesian sense. With the two coins you eliminate this possibility altogether - a broken coin can never produce HT or TH.
- Terr_ 1y ago
  I suspect this depends on where you drawn the upper bound, since a really really complex biased coin is one that spies on your thesis and data and is committed to making you suffer. Descartes' evil demon, in numismatic form.

by antics 1y ago

deleted 1y ago

[deleted]

falcor84 1y ago

Yes, but - you need to replace "twice" there with "an unbounded number of times". If you apply this in an environment where the biased coin is coming from an external source, your system becomes susceptible to DoS attacks.

pasquinelli 1y ago
i read "flip twice" as recussion, so, given we're talking randomness, yes, that could go on forever. but i don't think you really need to replace "twice."
antics 1y ago
While I obviously think randomness extractors over adversarial sources are very interesting, I think talking about them specifically in this example complicates the point I'm trying to make, which is that it's incredible it can be done at all.
- dataflow 1y ago
  Note that adversarial is kind of a red herring, not sure why they mentioned that. The number of flips is unbounded regardless. Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed. I realize this sounds like a minor detail to someone who finds this cool (and so do I), but I don't think it is. It's kind of frustrating to be told that your intuition is wrong by someone smarter than you, when your intuition is actually correct and the experts are moving the goalposts. IMO, it makes people lose respect for experts/authority.
  - dwattttt 1y ago
    I don't think anyone would be surprised to hear that if a biased coin can only give one result, you can't extract randomness from it. And if it can only give the second result one in a million times, you could be flipping millions.
  - QuesnayJr 1y ago
    I have the exact opposite reaction, that if someone told me the answer is "no" because it requires an unbounded number of coin flips that they were the ones trying to bullshit me. In antic's formulation, nothing is said about requiring a bounded number of flips.
    - dataflow 1y ago
      "Simulate a truly random coin" implies it IMO. You're not simulating a truly random coin if you need unbounded time for a single flip. The truly random coin definitely doesn't need that. It just feels like a scam if someone sold me such a machine with that description - I'd want my money back. I don't expect everyone would feel the same, but I think a lot of people would.
      - dooglius 1y ago
        A real coin could repeatedly land on its side over and over indefinitely, every time you flipped it.
      - thaumasiotes 1y ago
        You don't need unbounded time for a single flip, that's all in your imagination. The worst-case time is unbounded, but you can't achieve the worst case.
        falcor84 1y ago
        It's very easy to achieve if someone hands you a "coin" that is made such that it never lands on tails. Sorry for still being in the adversarial mindset, but this means that you essentially have to hardcode a maximum number of same-side flips after which you stop trusting the coin.

pbhjpbhj 1y ago

Speaking from complete ignorance, with apologies to those who that will annoy: I'm sure it's possible to make a coin with what one might term "complex bias" where the bias extends over two events (thick gloop inside the coin, possibly heat activated or non-Newtonian). This method sounds like the bias needs to be fixed ("simple bias" if you like)? I guess that's just out of scope here. Aside: There's a strong 'vibe' that HHHH HHHH with a single coin is somehow less random than HTHTHTHT HTHTHTHT with two coins when discarding HH and TT. I wonder what the origin of that feeling is - maybe just HT doesn't seem like it's a constant result simply due to nomenclature? If we call HT "type-A", then we just have HHHH HHHH vs. AAAA AAAA; and I _feel_ happier about the result!

lovecg 1y ago
Could the vibe be due to the fact that HHHH… seems like the coin could not just be biased - it could be completely broken and come up heads every time. There are two distinct possibilities here: 1) the coin is broken and is always H 2) the coin is random or possibly biased, and you got a string of H by chance And observing the string of H… increases the probability of 1) in the Bayesian sense. With the two coins you eliminate this possibility altogether - a broken coin can never produce HT or TH.
Terr_ 1y ago
I suspect this depends on where you drawn the upper bound, since a really really complex biased coin is one that spies on your thesis and data and is committed to making you suffer. Descartes' evil demon, in numismatic form.