Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a puzzle:

Two groups want to break a tied vote using a simple coin flip, however the only coin they have available is a biased coin (i.e., one side will come up more often than the other). To make matters worse nobody in the room knows (or is willing to admit) how the coin is biased.

Assuming that the coin has two distinct sides, design a method for using only this coin to determine a fair outcome between the two parties.

Initially, I thought, since neither party knows how the coin is biased, then either party could simply randomly guess which side the coin will land on and then they will receive a 50% chance they are correct (and 50% chance they are incorrect). This is assuming they are not influenced by any knowledge that they know for how the coin is biased when randomly deciding (or rather they do not know how it is biased). I even performed a simulation on this for a large amount of trials (live demo in python).

However, I stumbled upon this wikipedia article, which mentions an alternative method.

If a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure:

  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.

I'm just curious: is my method of solving the puzzle a viable solution? It seems so, but I'm not 100% certain.

share|improve this question
1  
Your method, while certainly viable in practice, doesn't have the same ammount of fairness as the one on wiki. If you are one of the two parties, you cannot be completely certain that the other party knows nothing about the bias. –  Arthur May 13 at 13:45

2 Answers 2

up vote 2 down vote accepted

If you have the ability to generate a random value with 50% probability in your head, then you can just pick one of the two outcomes and you don't need a coin at all.

Also, I think implicit in this problem is the possibility that one of the parties knows how the coin is biased and will secretly use this to their advantage. If you have a fair protocol that will worke with a biased coin then you can still produce a fair outcome despite secret knowledge.

share|improve this answer

Your method seems good to me as long as both parties are honest about their ignorance. In this case, each party must assign a subjective probability of heads of $0.5$ (since the subjective probability of heads must equal the subjective probability of tails).

The other method is more robust since it works even when one or both parties has knowledge about the nature of the bias. When looking at pairs, you can always assume that $$P[HT\vert HT \textrm{ or } TH]=P[TH \vert HT \textrm{ or } TH].$$


It occurred to me that you may want a method using a single coin flip which doesn't become unfair if one party has undisclosed knowledge. Here are the steps.

  1. Party $A$ guesses either heads or tails.

  2. Party $B$ guesses either heads or tails.

  3. If $A$ and $B$ make the same guess, then $A$ wins. $A$ and $B$ make different guesses, then $B$ wins.

  4. (Optional) Toss the coin.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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