5
\$\begingroup\$

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)?

\$\endgroup\$

closed as off-topic by Johannes Kuhn, Doorknob, Hasturkun, Kevin Brown, John Dvorak Dec 11 '13 at 7:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Doorknob, John Dvorak
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ If you gave integers p and q and the probability of heads was p/q, one wouldn't have to deal with things such as floats not being exact. \$\endgroup\$ – user475 Feb 10 '11 at 17:49
  • 2
    \$\begingroup\$ This question appears to be off-topic because it is not a programming puzzle \$\endgroup\$ – Johannes Kuhn Dec 6 '13 at 16:20
11
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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>
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 Also, have a look at Randomness extractor and von Neumann extractor. \$\endgroup\$ – Eelvex Feb 10 '11 at 19:33
0
\$\begingroup\$

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.

\$\endgroup\$
-3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ this is a duplicate of the currently most popular answer... \$\endgroup\$ – boothby Dec 5 '13 at 3:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.