You and a friend want to make a decision by coin toss, but all you have is a beat-up old ducat, which you fear is slightly biased. How do you make the fairest decision in a reasonable amount of time?
One-or-the-other. It might be fair, but it's probably biased (say, favoring one side no more than 60% of the time), and we don't know which side may be favored.
Both agree on a side, say heads. They continue to flip coin until only one of them gets heads.
Now the mathematical explanation. Lets call people as A and B. If we define probability of getting head as P(H)=t then P(T)=1-t Probability of A winning is: P(Awin) = t(1-t). P(Bwin) = (1-t)t. Their probability of winning is same for all rounds. Probability of reflipping is t^2+(1-t)^2. The more biased the coin, the less rounds is needed.
I have a feeling that this method is not the right way. This just equalizes probability of winnings, does not make it 50%. Besides there is always a chance this will take many turns.
Seems like it matters what kind of a decision you're trying to make.
1)Suppose you're just trying to decide whether to get Thai or Mexican for lunch, and neither of you is particularly invested in the outcome. I.e. you're both kind of just "I dunno, what do you want to do?". Then I think you ignore any bias and just abide by the first flip of the coin. All you want is for the coin to make a decision for you; you don't really care if the flip was "fair".
2)Or, maybe you want Thai and your friend wants Mexican. You both would be OK with either place, but you'd each get moderately less utility from the lunch if you lose the flip.
3)Then there's the case where it's all or nothing. E.g., you both agree on a restaurant, but the loser of the coin flip pays the whole lunch tab.
For cases 2) and 3) I think bitkidoku's solution is good (except I think you meant to say that the more biased the coin the more rounds we expect to be necessary. E.g. if the coin is 60% biased the probability of failing to resolve on the first round is 0.52 > 0.5 = probability of needing a second round if the coin is fair). Since Steve has said the coin is at most 60% biased, we can calculate the odds of needing 10 or more turns as being at most (0.52)^9 = 0.278%. I think this qualifies as a high probability of a decision in a reasonable amount of time.
According to comments in my source, the method proposed by bitkidoku was described by von Neumann. It assures, given enough patience, a perfectly fair result.
The threat of an extended series of matching pairs can be reduced with a nice refinement (mentioned by commenter blake r). Count a pair of heads followed by a pair of tails as a win for A, two tails followed by two heads wins for B.
The post linked above described a different method, attributed to Laplace. Flip the coin twice, and decide based on whether the results are the same or different. This does not eliminate bias, but reduces it significantly with very little effort. The outcome can be made even more fair by flipping more times, and deciding based on whether the count of tails is even or odd.
Bonus question: If you use the Laplace method of two coin flips, should you call "same" or "different"?
Well, the bonus question is just Fischer Price algebra, but I felt compelled to work it out anyway:
Let h be the probability of heads. Then the probability of matching is P(s) = h^2 + (1 - h)^2, and the probability of not matching is P(D) = 2h(1 - h).
So you should call same when h^2 + (1 - h)^2 > 2h(1 - h)
or, 2h^2 - 2h + 1 > 2h - 2h^2
or, 4h^2 - 4h + 1 > 0
or, (2h - 1)^2 > 0.
So you should always call same. In the case of a fair coin your odds are even, and any bias in the coin gives you the edge.
Which, incidentally, seems to render the Laplace method useless, assuming both flippers have basic math skills.
If you don't know which way the coin is biased then you have a 50-50 chance of calling the biased side, so there need be no dispute over who gets which side. But no-one will want to call different if you use that method, so while it may reduce the bias, it makes agreement impossible.
Another commenter to that post observed that Ultimate Frisbee players found the Laplace method helpful, given that (1) Frisbees show bias when flipped, and (2) not all Ultimate Frisbee players have basic math skills.
11 comments:
Do we know which way we suspect the coin to be biased?
I suppose you could flip it a few times and see what happens, but you can never be sure with those old ducats.
It is safe to assume that the coin shows a consistent bias, even if the bias is not known exactly.
What I meant was: do we fear the coin the coin is biased towards the obverse, the reverse, or one-or-the-other?
One-or-the-other. It might be fair, but it's probably biased (say, favoring one side no more than 60% of the time), and we don't know which side may be favored.
Both agree on a side, say heads. They continue to flip coin until only one of them gets heads.
Now the mathematical explanation. Lets call people as A and B. If we define probability of getting head as P(H)=t then P(T)=1-t
Probability of A winning is: P(Awin) = t(1-t). P(Bwin) = (1-t)t. Their probability of winning is same for all rounds. Probability of reflipping is t^2+(1-t)^2. The more biased the coin, the less rounds is needed.
I have a feeling that this method is not the right way. This just equalizes probability of winnings, does not make it 50%. Besides there is always a chance this will take many turns.
Seems like it matters what kind of a decision you're trying to make.
1)Suppose you're just trying to decide whether to get Thai or Mexican for lunch, and neither of you is particularly invested in the outcome. I.e. you're both kind of just "I dunno, what do you want to do?". Then I think you ignore any bias and just abide by the first flip of the coin. All you want is for the coin to make a decision for you; you don't really care if the flip was "fair".
2)Or, maybe you want Thai and your friend wants Mexican. You both would be OK with either place, but you'd each get moderately less utility from the lunch if you lose the flip.
3)Then there's the case where it's all or nothing. E.g., you both agree on a restaurant, but the loser of the coin flip pays the whole lunch tab.
For cases 2) and 3) I think bitkidoku's solution is good (except I think you meant to say that the more biased the coin the more rounds we expect to be necessary. E.g. if the coin is 60% biased the probability of failing to resolve on the first round is 0.52 > 0.5 = probability of needing a second round if the coin is fair). Since Steve has said the coin is at most 60% biased, we can calculate the odds of needing 10 or more turns as being at most (0.52)^9 = 0.278%. I think this qualifies as a high probability of a decision in a reasonable amount of time.
@Rasalom: YEs you are right about the mistake I made, the more biased the the decision is expected to be get in more rounds.
According to comments in my source, the method proposed by bitkidoku was described by von Neumann. It assures, given enough patience, a perfectly fair result.
The threat of an extended series of matching pairs can be reduced with a nice refinement (mentioned by commenter blake r). Count a pair of heads followed by a pair of tails as a win for A, two tails followed by two heads wins for B.
The post linked above described a different method, attributed to Laplace. Flip the coin twice, and decide based on whether the results are the same or different. This does not eliminate bias, but reduces it significantly with very little effort. The outcome can be made even more fair by flipping more times, and deciding based on whether the count of tails is even or odd.
Bonus question: If you use the Laplace method of two coin flips, should you call "same" or "different"?
Well, the bonus question is just Fischer Price algebra, but I felt compelled to work it out anyway:
Let h be the probability of heads. Then the probability of matching is P(s) = h^2 + (1 - h)^2, and the probability of not matching is
P(D) = 2h(1 - h).
So you should call same when
h^2 + (1 - h)^2 > 2h(1 - h)
or, 2h^2 - 2h + 1 > 2h - 2h^2
or, 4h^2 - 4h + 1 > 0
or, (2h - 1)^2 > 0.
So you should always call same. In the case of a fair coin your odds are even, and any bias in the coin gives you the edge.
Which, incidentally, seems to render the Laplace method useless, assuming both flippers have basic math skills.
If you don't know which way the coin is biased then you have a 50-50 chance of calling the biased side, so there need be no dispute over who gets which side. But no-one will want to call different if you use that method, so while it may reduce the bias, it makes agreement impossible.
Another commenter to that post observed that Ultimate Frisbee players found the Laplace method helpful, given that (1) Frisbees show bias when flipped, and (2) not all Ultimate Frisbee players have basic math skills.
Post a Comment