1. Toss the coin twice. 2. If the results match, start over, forgetting both results. 3. If the results differ, use the first result, forgetting the second.
This has appeared on HN before, but no one's pointed it out so far in the discussion. More info: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...
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.
[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); 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);It's also interesting (and I guess should be obvious) to note that the "thrown out" tosses seem to be a pretty consistent ratio based on the "biased-ness" of the coin.
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.
(1, 2, 5, 6) -> heads
(3, 4) -> tails
And use Neumann's algo.
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.
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.