3
$\begingroup$

Suppose you are given a biased coin for which the probability of getting a head is $p (0<p<1)$.Discuss how you will select one of two individuals at random using the biased coin.

$\endgroup$
6
  • 6
    $\begingroup$ Related: C puzzle: Make a fair coin from a biased coin and Getting a Fair Toss From a Biased Coin. $\endgroup$ – user10525 Nov 24 '12 at 16:08
  • 4
    $\begingroup$ Flip the coin. That's it. The choice will still be random, but it will be biased. If you want to try to make the choice .5 for each person, then see the link @Procrastinator gave. $\endgroup$ – Peter Flom Nov 24 '12 at 16:31
  • 3
    $\begingroup$ A technique for making an unbiased selection using biased coin goes back to Von Neumann. $\endgroup$ – whuber Nov 24 '12 at 16:39
  • 2
    $\begingroup$ There are plenty of ways other than Von Neumann's. (One amusing method: buy something cheap with the coin and flip one of the coins you get for change.) A good answer to this question might describe more than one way and assess their properties, such as the bias (if the solution only approximates a fair coin) and the expected number of flips needed to make a selection. $\endgroup$ – whuber Nov 24 '12 at 17:00
  • 1
    $\begingroup$ One nice thing about the Von Neumann solution is that it does not require us to know how biased the coin is... $\endgroup$ – Stephan Kolassa Nov 24 '12 at 19:45
2
$\begingroup$

As listed in the commments, the canonical way to generate an unbiased coin flip for a biased coin, as first proposed by Von Neumann, is as follows:

  • Toss the coin twice.

  • If the result is either both heads of both tails, discard and toss the coin twice again.

  • Otherwise, (if they are different), record the outcome of the first coin toss.

Understanding why this works relies on the observation that if you have a biased coin that comes up heads with probability $p$, and if you flip the coin twice, then:

  • The probability of HH is: $p^2$
  • The probability of HT is: $p(1-p)$
  • The probability of TH is: $(1-p)p$
  • The probability of TT is: $(1-p)^2.$
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for providing an answer to this long-standing question. Translating answers provided in comments into formal answers helps improve the quality of the site. $\endgroup$ – EdM Jul 14 '18 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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