5 ms·

John von Neumann figured out a solution for getting fair results from a biased coin: 1. Toss the coin twice. 2. If the results match, start over, forgetting bo

• darkmarmot 9y ago
  That is amazing! super biased coin and it works! var h = 0; var t = 0; for(i = 0; i < 1000; i++) { var a = Math.random() < .1; var b = Math.random() < .1; if(a !== b) { if(a){ h++} else {t++}} }; console.log(h,t);
  • contravariant 9y ago
    You could also just note that the two possible results where both coins differ are equally likely.
• samfriedman 9y ago
  Is there an extension to biased objects of more sides, say a die?
  • contravariant 9y ago
    You could wait until you got a run of all possible sides, but that could take a while.
  • Steko 9y ago
    I think if you do 6 rolls and take the sum modulo 6 it works. edit: no, got confused with something else (game I used to play was subject to widespread paranoia about the dice including the RNG source and whether other players had hacks. The dev ended up jumping thru all sorts of hoops to satisfy people -- taking random.org, letting each client add their own modifier and then using VN) I think the straightforward way to extend VN is rolling 6 dice and reroll all if there are any duplicates, then use the first one (or whatever). Probably more efficient to turn the die into a coin and then use a few coins to approximate the die.
    • kobeya 9y ago
      That would depend on get probability distribution I think.
  • buzzdenver 9y ago
    Just divide the sides into two groups. For example: (1, 2, 5, 6) -> heads (3, 4) -> tails And use Neumann's algo.
• throwaway613834 9y ago
  I assume it's impossible to achieve in bounded time?
  • contravariant 9y ago
    The coin can only generate a limited amount of entropy per flip, it could take arbitrary long to get enough to generate 1 unbiased coin-flip. You could bound the time if you knew the exact distribution though. Not sure if there's a method that's guaranteed to meet this bound.
    • throwaway613834 9y ago
      How could you bound the time if you knew the exact distribution? Like say it has heads probability p?
      • contravariant 9y ago
        Yeah I may have spoken to soon. There's a minimum bound, but now that I think of it there's generally no reason to believe that any subset of outcomes for any bounded number of flips would have a probability of exactly 1/2. In fact this is impossible if p is transcendental. The set of p for which there is a method to do it in finitely many flips is quite interesting though. It is bigger than the irrational numbers (it contains sqrt(1/2)), but smaller than all algebraic numbers. At the very least you'd need 1/2 ∈ Z[p], but that might not be enough.
  • hughes 9y ago
    With a few dozen flips you can achieve a greater likelihood that you're flipping the most biased coin on the planet, and stop the game.
    • throwaway613834 9y ago
      Right, this was a theoretical question..
  • 9y ago
• twodave 9y ago
  Wow. I took this to the nth degree to convince a colleague. Very little variance between biased and unbiased figures: [javascript] var sim = () =>{ var percentChanceOfHeads = 99; var getRandomArbitrary = (min, max) => { return Math.random() * (max - min) + min; }; let heads = 0, tails = 0; for (let i = 0; i < 100000; i++){ var test1 = getRandomArbitrary(0,100); var test2 = getRandomArbitrary(0,100); if (test1 > percentChanceOfHeads && test2 > percentChanceOfHeads) continue; if (test1 <= percentChanceOfHeads && test2 <= percentChanceOfHeads) continue; if (test1 <= percentChanceOfHeads) heads++; else tails++; } let total = heads + tails; let heads2 = 0, tails2 = 0; for (let i = 0; i < total; i++){ var test1 = getRandomArbitrary(0,100); if (test1 <= 50) heads2++; else tails2++; } var distanceClosed = Math.abs(heads-tails) - Math.abs(heads2-tails2); return distanceClosed; }; for(let i=0;i<10000;i++)temp.push(sim()); console.log('avg variance:' + temp.reduce((a,c)=>a+c)/10000);
  • TekMol 9y ago
    Shorter version: chanceOfHead=0.9; heads=0; tails=0; flips=0; while(flips<1000) { coin1=Math.random()<chanceOfHead; coin2=Math.random()<chanceOfHead; if(coin1==coin2) continue; heads+=coin1; tails+=coin2; flips++; }; console.log(heads,tails);
    • oh_sigh 9y ago
      Oh JavaScript. Will a Boolean always on all browsers coerce itself into a 0 or 1 if treated like a number?
      • tjgq 9y ago
        The Javascript coercion rules, arcane as they are, are actually part of the spec and (barring any bugs) should work across browsers.
    • twodave 9y ago
• deleted 9y ago
  [deleted]
• chillee 9y ago
  If anybody's curious about the math, it's pretty simple. Assume p is the probability of flipping heads. Then, pp is the probability of flipping 2 heads, (1-p)(1-p) is the probability of flipping 2 tails, (1-p)p is the probability of flipping tails then heads, and p(1-p) is the probability of flipping heads then tails. So, basically p^2 + (1-p)^2 + p(1-p) + (1-p)p = 1. Then, we ignore the first 2 terms (since that's when the results match and we start over), and we're only left with the p(1-p) case and the (1-p)p case. These are equally likely, and the first coin is heads in the first case and tails in the second.
  • mlevental 9y ago
    you know what always screwed me up in stats? conditional probability. your expansion makes perfect sense (you've constructed a new measure) but I'm left here wondering if just dropping the first two terms is really the right way to find the conditional density (conditioned on the first two flips coming out the same).
• rajacombinator 9y ago
  Very cool thanks for sharing. One of those things that is non obvious until you read it, then totally obvious.