Puzzle about technique of fair using of unfair coin

Question

There is an unfair coin. It tends to land on one side more than on the other. It is unknown which side is it.

There is Mr. A and Mr. B. They argue about something and they want to use that coin to decide who is right.

Is there any technique of using that unfair coin to get fair result?

My solution: I can think of only that there is going to be 2 rounds. First time Mr. A chooses HEAD, than Mr. B chooses HEAD if any of them wins twice they win.

Answer 1

Your solution is fine. An alternative formulation: If $H$ comes with probability $p$ and $T$ with $1-p$, we can combine two consecutive tosses (we may at least assume independance, don't we?) into Meta-Head = $HT$ and Meta-Tails = $TH$, where each occurs with $p-p^2$, but we have Meta-Tie with $1-p+p^2$ (and repeat the Meta-Coin toss until it is resolved). If $0<p<1$ then $1-p+p^2<1$, so this will terminate a.s.

Answer 2

I think you need an unbounded number of coin tosses, however the expected number of tosses to settle the issue will be finite: Toss twice. If it comes up heads, then tails, A wins. If it comes up tails, then heads, B wins. If the two tosses come up the same, start over. If the coin is extremely unfair, this will probably take a long time, but if it is only a little unfair, you should be settled soon enough.

Answer 3

There's a difference here between randomness and predictability. If the coin is only tossed one time, the answer is unpredictable, even though the result is biased. Ask one of them to pick heads or tails, and toss the coin.

The more often you toss, the more the bias will become evident, and predictability becomes an issue. Fairness is based on unpredictability, not randomness.

Answer 4

The answer is 1 toss. let us assume that one side has a 100% chance of coming up - but that we don't know which side that is.

Each person has an even chance of picking that side, so each person STILL has a 50/50 chance of winning. This is the degenerate case of an unfair coin, but you can infer that all other possibilities of an unfair coin lead to the same conclusion.

This is true, of course, if the bias of the coin is unknown to the person picking the "head" or "tail" side. As long as there is no knowledge biasing the choice, the chance is still 50/50 regardless of the bias of the coin.

Another example of this is where one person puts a pebble in their hand and tells the other player to choose which hand. The person with the pebble has a 100% chance of picking the proper hand, but since they don't get to choose, their chance of winning is still 50/50 - as long as the OTHER player has no knowledge.

Answer 5

Well, this answer really worked in my head, I'll leave it here for reference because I think I'll fix it later... but anyways I just built a program to iterate out my hypothesis below to 200 million iterations and the stats it popped out were as follows:

Heads Ratio:            30.0109249726876%
Tails Ratio:            69.9888250279374%
Player_a wins Ratio:    41.924645188387%
Player_b wins Ratio:    58.075104812238%

so it didn't work /:

Flip twice.

The first flip determines what person A will get to call. For example person A does not call heads or tails, they just have the coin flip...

•If it lands on heads then their call for the next flip (the real flip) is tails.
•If it lands on tails then their call for the next flip (the real flip) is heads.

Now do the next flip, the "real" flip... Person A has called either heads or tails (been forced to call either heads or tails based on the previous flip) and now they will either win or lose.

---

Let's say the ratio of heads:tails is 70:30

There is a 70% chance they will get heads on the first flip, meaning there is a 70% chance their call for the "real" flip is tails, which only has a 30% chance of winning. There is a 30% chance their call for the real flip is heads, which has a 70% chance of winning. Both events average to 50%

Answer 6

Assuming neither player knows what the advantage is, they just know that it flips to one side more than the other but they don't know which side or how often...

---

Flip the coin until it has landed at least once on both heads and tails...

The number of times it took before that is satisfied is the "count"

Now instead of picking "heads or tails" users just pick greater than or less than the count, for how many more flips they think it will take for the coin to reach heads and tails at least once.

For example: H, H, H, H, T (count is 5) ... players pick <5 or >5 ... so then we start flipping again H,H,H,T (<5 player wins)... H,H,H,H,H,H,H,H,H,T (>5 player wins) .. and of course, H, H, H, H, T (is =5 which is a tie and we just restart this "second" round (same count)

Answer 7

Tossing a Biased Coin describes an improved algorithm that also doesn't require knowledge of the probability $p$ for the unfair coin to show heads. As in the other answers, interpret, say, $HT$ as $H$ and $TH$ as $T$. If you fail twice, i.e. you get $TT$ or $HH$ twice, treat those as new biased tosses of $T$ and $H$, respectively, and apply the same rule. Continue combining failed results in this manner at all levels. Then an unbiased result is obtained in $2^k$ tosses unless they all have the same outcome. The expected number of tosses required to extract a single unbiased toss is

$$ 2\prod_{k=1}^\infty\left(1+p^{2^k}+(1-p)^{2^k}\right)\;, $$

compared to the

$$ \frac1{p(1-p)} $$

required by the simpler algorithm described in the other answers. For instance, for $p\to\frac12$ the improvement is from $4$ to about $3.4$.

For a further improvement that's possible if $p$ is known, see How to choose between two options with a biased coin.