5 ms·

You've always got the standard way to get fair random numbers from a fairness-unknown coin. Flip it twice. Restart if you get both heads or both tails. If yo

You've always got the standard way to get fair random numbers from a fairness-unknown coin. Flip it twice. Restart if you get both heads or both tails. If you get H then T or T then H, those are equally probable, so take the first one of those as the final outcome. This generalizes to a die of N sides. Roll it N times. If you don't get all N distinct results, restart. If you do, then take the first result as your final outcome. (That may take a lot of trials for large N. It can be broken down by prime factorization, like roll 2-sided and 3-sided objects separately, and combine them for a d6 result.)

eddd-ddde 2y ago
Hmm my intuition isn't agreeing with this. Does this have a name so I can read more about it?
- shmageggy 2y ago
  Von Neumann randomness extractor https://en.m.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor https://en.m.wikipedia.org/wiki/Randomness_extractor#Von_Neu...
  - Jerrrrrrry 2y ago
    I have the humility to admit that this, despite everything I pretend to know, has always escaped my understanding. Someone please (jump?) at the chance to explain this one to me. (assume i failed 9th grade 3 times)
    - voldacar 2y ago
      The key assumption is that T and H may not have the same probability, but each flip isn't correlated with past or future flips. Therefore, TH and HT have the same probability. So you can think of TH as "A" and HT as "B" then you repeatedly flip twice until you get one of those outcomes. So now your coin outputs A and B with equal probability.
      - Jerrrrrrry 2y ago
        I feel like I am missing something so obvious that I feel the need to correct wiki, but that likely means I am fundamentally missing the point. "The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being "one"->[first] and there is no correlation between successive bits.[7]" As long as the person doesn't favor which of the two bits they chose is "first", then it should appear as random. But that is self-defeating, as if the person had the capability to unbiased-ly choose between two binaries, they wouldn't need the coin. But since the only way to determine the variation from expectation is repeatedly increasing sample size, I don't see how doing it twice, and just taking encoding of the bits, then... Is the magic in the XOR step? To eliminate the most obvious bias (1v5 coin), until all that could had been left was incidental? Then, always taking the first bit, to avoid the prior/a priori requisite of not having a fair coin/choosing between two options? and it clicked. Rubber duck debugging, chain of thought, etc. I will actually feel better now.
        Jerrrrrrry 2y ago
        >To eliminate the most obvious bias (1v5 coin), until all that could had been left was incidental? There is only one coin, flipped _twice_; not a running occurrence, but in couples, perfectly simulating two coins functionally. Once a literal couple of coins result in a XOR'd result eventually, no matter how biased - they differ - the exact ordinality of which will be random. Two sides to a coin, no matter how random, still half the chance. (for lurkers cringing at my subtle mis-understanding)
        ljsprague 2y ago
        Maybe I don't understand why or what you don't understand but... Say you have a biased coin. It lands heads 55% of the time (but you don't know that.) Then the probabilities are: HH = (0.55 * 0.55) = 0.3025 TT = (0.45 * 0.45) = 0.2025 HT = (0.55 * 0.45) = 0.2475 TH = (0.45 * 0.55) = 0.2475 If you disregard the HH and TT results then the equal probabilities of HT and TH result in a perfect binary decider using a biased coin. You assign HT to one result and TH to the other.
- jvanderbot 2y ago
  It may be more likely that H or T happens (an unfair coin), but in a pair of H and T, both HT and TH are equally likely. Therefore which is "first" is equally likely H or T. Only holds if no spooky effects change results based on last result. (like a magic die that counts upwards or a magic coin that flips T after H no matter what) P(TH) = p(T)*p(H) = P(HT)
  - vikingerik 2y ago
    Your second paragraph is correct and may be where the previous poster's intuition was disagreeing, that the method doesn't necessarily hold for repeated iterations in a physical system where one trial starts from where the last one ended. It's not even really "spooky" - all you need is a flipping apparatus that's biased towards an odd number of rotations, and so then THTH is more common than THHT and you get a bias towards repeating your last result.
    - eddd-ddde 2y ago
      Exactly right, I was thinking an unfair coin could have "memory" but then the method doesn't hold.
  - guenthert 2y ago
    What about a 'dirty' coin or dice, where the dirt falls off during the run?
    - jvanderbot 2y ago
      That'd do it. P(H|N) != P(T|N) And P(H|N) != P(H|N-1) (and visa versa) Means that P(HT) = P(H|N-1, T|N) != P(TH)
    - AJTSheppard 2y ago
      That's a clever point. But I think a corner case. I suspect that when the user is loading coins or dice in the machine, they would notice any dirt that was significant enough to look as though it might be a problem. And oil deposits from your fingerprints I would imagine are so minuscule as to be insignificant in creating varying bias. Even then, in both cases, you could wipe the objects with an alcohol swab before putting them into the shaker cups. It could be argued, I suppose, that every micro-collision of the coin or die with the cup removes a few atoms, but I would suggest that its effect on the bias of the coin or die over time is again minuscule. Indeed, unmeasurable over a full sequence of cycles (128 for example) of the machine when generating a Bitcoin key. But an interesting point. Keep 'em coming!

eddd-ddde 2y ago

Hmm my intuition isn't agreeing with this. Does this have a name so I can read more about it?

shmageggy 2y ago
Von Neumann randomness extractor https://en.m.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor https://en.m.wikipedia.org/wiki/Randomness_extractor#Von_Neu...
- Jerrrrrrry 2y ago
  I have the humility to admit that this, despite everything I pretend to know, has always escaped my understanding. Someone please (jump?) at the chance to explain this one to me. (assume i failed 9th grade 3 times)
  - voldacar 2y ago
    The key assumption is that T and H may not have the same probability, but each flip isn't correlated with past or future flips. Therefore, TH and HT have the same probability. So you can think of TH as "A" and HT as "B" then you repeatedly flip twice until you get one of those outcomes. So now your coin outputs A and B with equal probability.
    - Jerrrrrrry 2y ago
      I feel like I am missing something so obvious that I feel the need to correct wiki, but that likely means I am fundamentally missing the point. "The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being "one"->[first] and there is no correlation between successive bits.[7]" As long as the person doesn't favor which of the two bits they chose is "first", then it should appear as random. But that is self-defeating, as if the person had the capability to unbiased-ly choose between two binaries, they wouldn't need the coin. But since the only way to determine the variation from expectation is repeatedly increasing sample size, I don't see how doing it twice, and just taking encoding of the bits, then... Is the magic in the XOR step? To eliminate the most obvious bias (1v5 coin), until all that could had been left was incidental? Then, always taking the first bit, to avoid the prior/a priori requisite of not having a fair coin/choosing between two options? and it clicked. Rubber duck debugging, chain of thought, etc. I will actually feel better now.
      - Jerrrrrrry 2y ago
        >To eliminate the most obvious bias (1v5 coin), until all that could had been left was incidental? There is only one coin, flipped _twice_; not a running occurrence, but in couples, perfectly simulating two coins functionally. Once a literal couple of coins result in a XOR'd result eventually, no matter how biased - they differ - the exact ordinality of which will be random. Two sides to a coin, no matter how random, still half the chance. (for lurkers cringing at my subtle mis-understanding)
      - ljsprague 2y ago
        Maybe I don't understand why or what you don't understand but... Say you have a biased coin. It lands heads 55% of the time (but you don't know that.) Then the probabilities are: HH = (0.55 * 0.55) = 0.3025 TT = (0.45 * 0.45) = 0.2025 HT = (0.55 * 0.45) = 0.2475 TH = (0.45 * 0.55) = 0.2475 If you disregard the HH and TT results then the equal probabilities of HT and TH result in a perfect binary decider using a biased coin. You assign HT to one result and TH to the other.
jvanderbot 2y ago
It may be more likely that H or T happens (an unfair coin), but in a pair of H and T, both HT and TH are equally likely. Therefore which is "first" is equally likely H or T. Only holds if no spooky effects change results based on last result. (like a magic die that counts upwards or a magic coin that flips T after H no matter what) P(TH) = p(T)*p(H) = P(HT)
- vikingerik 2y ago
  Your second paragraph is correct and may be where the previous poster's intuition was disagreeing, that the method doesn't necessarily hold for repeated iterations in a physical system where one trial starts from where the last one ended. It's not even really "spooky" - all you need is a flipping apparatus that's biased towards an odd number of rotations, and so then THTH is more common than THHT and you get a bias towards repeating your last result.
  - eddd-ddde 2y ago
    Exactly right, I was thinking an unfair coin could have "memory" but then the method doesn't hold.
- guenthert 2y ago
  What about a 'dirty' coin or dice, where the dirt falls off during the run?
  - jvanderbot 2y ago
    That'd do it. P(H|N) != P(T|N) And P(H|N) != P(H|N-1) (and visa versa) Means that P(HT) = P(H|N-1, T|N) != P(TH)
  - AJTSheppard 2y ago
    That's a clever point. But I think a corner case. I suspect that when the user is loading coins or dice in the machine, they would notice any dirt that was significant enough to look as though it might be a problem. And oil deposits from your fingerprints I would imagine are so minuscule as to be insignificant in creating varying bias. Even then, in both cases, you could wipe the objects with an alcohol swab before putting them into the shaker cups. It could be argued, I suppose, that every micro-collision of the coin or die with the cup removes a few atoms, but I would suggest that its effect on the bias of the coin or die over time is again minuscule. Indeed, unmeasurable over a full sequence of cycles (128 for example) of the machine when generating a Bitcoin key. But an interesting point. Keep 'em coming!