Fair outcome using unfair coin

Question

I have been thinking a lot about the following puzzle, but could not arrive at a solution.

Can someone explain to me how can you get a fair (equal probability) outcome using only an unfair coin (where unfair means that it will land head with probability p and tails 1-p where p != .5)?

Answer 1

It will require some extra tosses, but you can get a fair result this way:

Always use two throws to determine the answer, a HH or TT throw is discarded.

HT == True TH == False

You know that the probability of HT is the same as the probability of TH.

Answer 2

Let a and b be the results of 2 tosses of the unfair coin. (Where true is heads, false is tails).

Now a is true with a probability of p, a is false with a probability of (1-p) (and the same with b).

          | b = true | b = false
a = true  | p*p      | p*(1-p)
a = false | p*(1-p)  | (1-p)(1-p)

Two of these probabilities are equal, a && !b, and !a && b

We can use the following relation to calculate a fair result

if a && !b
  true
elsif !a && b
  false
else
  # try again
end

Greater the value of |p-0.5|, greater is the number of calls you'd need.

Demonstration using ruby

An unfair coin toss

f=->n { rand < n }

Testing it with p=0.6

irb(main):010:0> (1..10000).count{f[0.6]}
=> 5958
irb(main):011:0> (1..10000).count{f[0.6]}
=> 6088
irb(main):012:0> (1..10000).count{f[0.6]}
=> 5923

Fair coin toss, based on the unfair one

g=->n{a=f[n];b=f[n];a && !b ? true : !a && b ? false : g[n]}

Testing the fair coin toss.

irb(main):021:0> (1..10000).count{g[0.6]}
=> 5005
irb(main):022:0> (1..10000).count{g[0.6]}
=> 5072
irb(main):023:0> (1..10000).count{g[0.6]}
=> 4954

Number of recursive calls made as p increases.

# redefining g to count calls.
irb(main):002:0> g=->n{$c+=1;a=f[n];b=f[n];a&&!b ? true:!a&&b ? false:g[n]}
=> #<Proc:0x259e150@(irb):2 (lambda)>
irb(main):003:0> $c=0
=> 0
irb(main):004:0> (1..10000).count{g[0.99]}
=> 5062
irb(main):005:0> $c
=> 499582
irb(main):006:0> $c=0
=> 0
irb(main):007:0> (1..10000).count{g[0.1]}
=> 4961
irb(main):008:0> $c
=> 55358
irb(main):009:0> $c=0
=> 0
irb(main):010:0> (1..10000).count{g[0.9]}
=> 5003
irb(main):011:0> $c
=> 55013
irb(main):012:0>

Answer 3

While it would be a fairly cumbersome answer, you can work it out with the binomial distribution function.

My Strategy would be to pick some large(ish) number of trials. Use the binomial distribution to find the probabilities of each number of successes. Partition the numbers as best as possible to make two sets of equal size.

For example, 10 trials, probability of 0.6 for success:

# successes
    Probability
0   0.00010
1   0.00157
2   0.01061
3   0.04246
4   0.11147
5   0.11147
6   0.25082
7   0.21499
8   0.12093
9   0.04031
10  0.00604

Find some combination of the above that adds up to as close to 50% as you can (this is probably pretty hard to do well, especially if something like 100 trials were used.)

Remember which numbers of successes contributed to that 50%.

Do N random trials, 10 in our case. The number than came up successes will either be in the combination (call the whole thing a success) or not (call the whole thing a failure)

This strategy completely falls apart as the probability approaches 0 or 1, as more trials will be needed to be able to come close to 50%.

I should also mention this isn't completely fair. It can make unfair coins more fair, depending on how well you can partition the number of successes.

Answer 4

HT probability = P*(1-P) TH Probability = (1-P)*(P)

So you can use the above two as the real outcomes and discard HH and TT