A fair coin?
You have a coin that is biased, although you don’t know its probability of flipping heads or tails.
Using only this coin, can you design a repeatable process that is effectively the same as a fair coin flip?
Assume that the flip outcomes (heads and tails) each have constant non-zero probabilities. The process you design can be as long as it needs to be.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
12 solutions
Moderator note:
The reason this solution works is because the outcomes TH and HT are symmetric and have the same probability no matter what the bias on the coin is. Since you repeat the process if you get any other outcome, you will achieve a fair outcome eventually.
It's possible that this process could go on for a very long time -- if the coin is heavily biased to one side. Even so, all of the possible lengths are finite, and an infinite length would have a probability of 0. Thus, the process is guaranteed to be finite in length.
As a final note -- some may think that the first coin toss is fair no matter what the bias on the coin is. The thinking goes: if you don't know what the bias is, then it's essentially a fair coin flip to decide which side to favor. We avoid this philosophical argument about the first flip by specifying that the process must be repeatable.
Same solution! :)
Can you please explain the solution more clearly.
Log in to reply
Call the probability of landing heads "p". You don't know "p". But by laws of probability, the probability of landing tails must be 1-p. So the probability of a two coin flip resulting in HT or TT must be p(1-p) either way (the probability of HH is p^2 and the probability of TT is (1-p)^2 but you ignore those results). Thus, you arbitrarily the result of HT to be like a fair "H" and TH to be a fair "T", and each result has the same probability as the other.
Log in to reply
Typo correction: Your first "TT" should be a "TH" to read "the probability of a two coin flip resulting in HT or TH must be p(1-p) either way."
Any other way of explaining
Log in to reply
Use Binomial Probability Distribution. It will turn out that even after not knowing the probability. after doing calculations you would end up getting probability of getting heads and tails as 0.5.This question is a ''Brilliant'' way of asking whether there is proof of probability of getting heads and tails equals 0.5.
Suppose the coin has a p chance of flipping heads. Then its chance to flip tails is ( 1 − p ) .
The probability to flip heads and then tails is p × ( 1 − p ) = p ( 1 − p ) .
The probability to flip tails and then heads is ( 1 − p ) × p = p ( 1 − p ) .
Even though the coin is biased, these two particular outcomes have the same probability (no matter what the bias is). The process is this:
- Flip the coin twice.
- If you get heads then tails, then treat this as a "heads" flip.
- If you get tails and then heads, then treat this as a "tails" flip.
- If both the flips are the same, then flip the coin twice again and follow the same process.
Log in to reply
small typo: If you get tails and then tails, then treat this as a "tails" flip ----> If you get tails and then heads, then treat this as a "tails" flip
To explain in a bit simpler (hopefully!) terms...
Flip the coin twice. If the results are the same, discount these results, and flip the coin twice again. Keep flipping (2 flips at a time) until both flips are different. Then count the first flip (of the two) as the result.
This works since the probabilities of each outcome yield the same product when multiplied together.
Note: This requires that p = 0 , 1 .
Log in to reply
Yes, but that is assumed in the problem statement.
Log in to reply
Ah thanks, I missed reading that line. I did a quick read of the problem and then thought about it offline.
To me, the interesting part was figuring out if a "always heads" coin could ever lead to a 50-50 outcome. That seems obvious, but I'm not certain how to prove it rigorously other than "No matter the setup, there is only 1 outcome".
Log in to reply
@Calvin Lin – Well, that is a proof.
I notice from your profile that you are from the University of Chicago, btw. Great school :)
Actually, the assumption that each probability is non-zero is not necessary. Even if the coin has a 100% probability to land on one side, you can still use it to make one 50% chance toss (as long as the other person is free to choose the winning side before the toss).
Log in to reply
How does the other person choose the the winning side? There is no other access to randomness except through this coin.
"Unknown bias" is not the same as "random bias," but I see how one could interpret it that way. I've clarified the problem statement to specify that the process has to be repeatable.
I think this is wrong solution or at least the puzzle is not well phrased. This solution is a process which can be arbitrarily long. My oponion that it should be stated that is allowed. For me it was clear that it is not allowed.
Log in to reply
Thank you for this -- I have added an assumption that the process can be as long as it needs to be. Although the expected length of the process approaches infinity as you increase the bias, the bias will never be 100%, so the length of the process is always finite.
Log in to reply
I still have a problem with the fact that the process is of arbitrarily long length. That creates a system that is very different in nature than a coin flip. It doesn't feel like "essentially the same" as a coin flip, which has a guaranteed, finite bound on the amount of time needed to reach a decision.
Log in to reply
@Richard Desper – Yes, I see your point: technically the probability of a repeat trial is never 0, so the process is not necessarily finite. It is only finite with some increasingly large probability. This is not "essentially the same" as a coin flip.
Log in to reply
@Daniel Fryer – Please notice that we've added "The process you design can be as long as it needs to be" to the assumptions.
@Daniel Fryer – "Finite" and "Bounded" aren't the same thing. A coin flip is a temporally bounded act. A process guaranteed to end in finite time with probability 1 still isn't a bounded act. That's my quibble.
I think you are conflating the length of the process, which may be infinite (unlike the fair coin flip), and the expected length of the process, which is always finite.
I think the confusion here is with the term “effectively the same”, in which case the solution works. However, because the probability of a flip never changes, it is not possible to empirically calculate the bias to 100% accuracy.
Log in to reply
I'm not sure I understand -- We're not trying to calculate the bias of the coin. We're trying to create an outcome that is the same as a fair coin flip. We've clarified the problem statement to clarify -- please let me know if this clears up the confusion.
This seems extremely clever to me, thank you for the clear solution!
I was imagining trying to work out the coin's statistics and based on this define a procedure using a finite number of trials that would take out the bias. This would be enormously more complex, and I think would only work for
p
that are fractions?
This may be true for the first time, but after a bunch of throws you would see which outcome is more common. Lets suppose you notice something like H = .9 and T = .1, or basically you notice H is more likely to show up than T. You then go for a pair of coin flips. First flip, T shows up. Now, going by the actual probabilities i’ve proposed above, there’s a 90% chance the next flip is H - which would cause the first throw, T, to stick. Again, It is likely then (90%), that T will win, regardless of TH being equally as likely as HT.
You can say, “but if H is the first outcome, then you are unlikely to be able to predict H will stick, since its more likely to get HH, instead of HT.” This is true, and it may also be true that a balance may be eventually achieved, were HT and TH occurred the same amount of times over a significant amount of trials: I am not questioning the math here.
What i mean is that through the method you’ve proposed, there’s an instance when the probability a certain outcome occurs may be much higher than another, and in this instances, the coin and the method would not live up to an “effective” 50:50.
Think about the scenario I’ve proposed with an unbiased coin ( i.e H = T). No matter what result you get first, at no point you’d be able to say, “H is more likely to stick than T,” or vice versa. However, in the above example, after a T toss, you can be pretty confident a H will show up.
Overall, on an infinite amount of trials, TH and HT may occur the same amount of times, but during the course of these trials, you will be able to usually predict the outcome of certain specific trials while conducting them. This would not be true for a pure 50:50 coin. This goes to show, that in the long run, this process does not effectively achieve the same purpose as a 50:50 coin.
Log in to reply
You are commenting on the probability of H given that T has already happened. But T is much more rare than H, and you don't know in advance if T has happened yet. This is why TH has the same probability as HT. This is why you "can't argue with the math."
You could break any "fair" coin flip into a series of steps that, when conditioned on, remove the fairness. For example, what is the probability of getting H, given that the coin is within 1 millimeter of my hand at the end of it's flip, and H is already facing up? You are breaking the repeatable process into parts that, when conditioned on, can remove the fairness. This doesn't change the fairness of the whole process when executed non-conditionally in one go.
Log in to reply
First off, thanks for the discourse.
If I got your argument right, you stated this fair, repeatble process can be conditioned so as to make it unfair, and that doesn’t affect the fairness of the whole process.
And I agree, with the first part mostly.
I’m just trying to show that there is a step - or position - on the process when you could make the process unfair, and the same would be really hard to do with a unbiased coin.
Your example “[...] probabilty of getting H, given that the coin is within one millimiter of my hand at the end of [sic] it’s flip, and H is alredy facing up...” could be true for both coins, the biased and unbiased coin. In this sense they would be “effectively the same,” and it wouldn’t be unfair since anyone seeing the event - occurring with either a biased or unbiased coin - could predict H.
In my scenario ( predicting H after T), after an event ( T ) you can be certain - to some degree (90%) - of a specific outcome (H). The same would not happen with an unbiased coin. This is a form thus, the process is not effectively the same as an unbiased coin. Now if you don’t separate this instance from the whole process, there is no unfairness to exploit. Yet, it can be done, and where people find exploits, they exploit. Furthermore, in contrast to your example, in my scenario, only you - that is to say, one who has knowledge of the bias and its effects - could “predict” with certainty an outcome. Anyone who hasn’t learnt about the bias, could not predict an outcome with certainty, and this is ultimately unfair.
Independently of what we choose to do when facing these exploits, the possibilty of unfairness still exists; the same is not true with an unbiased coin.
Maybe the wording of the problem should be changed from “...effectively the same as an fair coinflip,” to something like “effectively a fair process,” not leaving room to comparisons to an actual fair coin toss, and specifying that the process as a whole is to be fair, independently of possible instances of unfairness along it.
Sorry for the use of second person through my writing. I know it is informal and personal. Yet for the sake of simplicity, I have kept the form.
Log in to reply
@Octavio Anino Barber – If you’d prefer imagine two coins with equal (but unknown and potentially biased) probability of landing heads. Both are flipped simultaneously. The procedure described will be unbiased regardless of p. Flipping two simultaneously is indistinguishable from flipping one twice.
You don't know the bias is independent. It could be an internal mechanism that switches so the coin always gives heads, tails, heads .... or any other pattern.
Log in to reply
It is stated in the assumptions that the probabilities of the flip are constant and non-zero.
If the bias was for heads, the sample is two flips, with the output dependent on the first flip, you would preserve a bias toward a heads output. The probability of (HT) does not equal Probability (TH).
Log in to reply
The output is dependent upon both flips. If the first flip is heads and the second flip is also heads, then the process repeats itself with another two flips.
Log in to reply
I thought as Jarrod Hitchings. If Heads are more probable, p(HT) should be > p(TH) as I see it, but I have made a simulation with 1000 flips and p(H)=0.6 and p(T)=0.4. The outcomes are almost equal: 228 vs 227 for HT and TH respectively. Awsome.
Log in to reply
@Félix Pérez Haoñie – This is because the flips are independent, so the probability of HT is 0.6 x 0.4 = 0.24 and the probability of TH is 0.4x0.6 =0.24. They are equal!
Log in to reply
@Varsha Dani – Thak you for answering. I realized of that explanation short time later after I posted my comment. :-)
I don't know how to post my solution to this problem and maybe I'm wrong. Mine is more painful but I would like to hear about your opinion on its effectiveness:
Make 10+10 flips and count how many of the first 10 are Heads (H) and how many Tails (T). The same with the next 10. Then interchange the numbers of H and T in the second row. This way, you have now balanced the chances of H and T accounting all the 20 flips. Now look at the overall numbers of H and T and take H if H overnumbers T, and T if T is higher.
If numbers of T and H are equal then you must repeat the process until getting a difference between the numbers.
Would this work?
The probability of H first is higher than T, but the probability of H second is also higher than T second (i.e. P(HH) > P(HT), so the higher frequency of H first will be negated by the higher frequency of H in the second, so fewer of the H first events will go forward (more will be rejected as HHs). Conversely, the probability of T second, after a T first is lower than the probability of H after T first, so fewer of the T first events will be rejected (as TTs) so the bias against the T first throws is equally negated. Thus P(TH) = P(HT).
Very cool solution, Varsha!
This process will never guarantee an output after a finite amount of trials (we could flip HH or TT for all trials). Wouldn't it be necessary that a process guarantees itself will have an output?
If the bias is 100% (two headed coin, for example), the test never produces a result.
Log in to reply
It is specifically assumed that this is not the case.
For every other flip, declare the opposite result. Each flip won't be fair, but after several flips you will get 50/50.
If playing with two people, alternate the win condition between players every flip. I.e. I win on H on odd numbered flips and T on even numbered flips. As long as there is an even number of flips, the bias of the coin is irrelevant.
Take the extreme case of 100% prob of H. I will win every second flip and lose every other. Over an even number of games it will be exactly 50/50 with no winner.
Over an odd number of games, if the bias is unknown to either player, then the game will still be fair but there will be a winner. Although every game after the first will be irrelevant if the coin is 100% bias to one side.
I believe this solution is close, but not quite. With your process, you're going to have an unknown bias on each flip -- it's just that the bias is going to switch on each subsequent turn. We need a process with no bias on every turn.
We have clarified the problem to help with some of the confusion.
Log in to reply
I had a solution which was: In the odd turns, H and T represent themself, whereas in the even turns if the coin lands on H take it as T and vice versa. This way the bias is balanced out. Would this be a valid solution?
You are given a coin, about which you know that it is biased, but then, you don't really know which outcome is more probable once you toss it, as per the question. Therefore you can treat it just like any other coin as you can only think of two possible ways it may be biased, i.e. whether the coin will prefer heads as outcome or tails. So, Just for once, the coin has same number of equally probable outcomes as any unbiased coin has.
"Therefore you can treat it just like any other coin as you can only think of two possible ways it may be biased"
This is wrong. You are told that it is biased. In fact, if you like I can even promise you that it is biased towards Heads. You cannot just pretend that it isn't and toss it like a regular coin. This is not a philosophical question about Bayesian priors. It is a mathematical question about sampling from a uniform distribution when you only have access to a non-uniform one.
It is never stated that the bias is randomly assigned. What if the person who gave you the coin specifically biased it in a certain way (but you didn't know which way that was)?
Anyways, we are making an edit to this problem to clarify.
Log in to reply
When I viewed the Question first, I directly assumed that the coin was biased "randomly" as you said (not stated by the problem). Thanks anyway.
You didn't understand the problem
I agree that this is not what the problem was looking for. But still, a very nice observation. I like it.
I think that your solution is valid for a one time coin toss, and quite clever, but the problem clearly states that a repeatable process is required.
You didn't understand the problem. The coin is biased, you know this for sure. You know that the chances are not 1/2 for each so you need to find a way to provide a 1/2 chance for each.
Log in to reply
Disagree. It just says "that is the same a fair coin flip". If the two parties do not know the head-tails bias, nor the % bias then the ignorance of the two cancel it out. Even with a 100% bias if you do not know it and allow some1 to choose in ignorance then that is your fairness injected. Have you seen the Only Fools and Horses episode with the coin with two heads? ;-)
Log in to reply
I don't want to get into a Bayesian philosophical discussion about the first toss. However, I will point out that the problem asks for a repeatable process.
Doesn't a fair coin still have a bias (in this case, bias = 0)?
Its not about knowing the which side it prefers, its about continuously have a fair flip, with your solution, after the n'th flip, you will get ideas about the favourite side of the coin.
The question states that the method must be repeatable, and so, since your solution only works on the first flip ("Just for once,"), this is not a valid answer.
This is not entirely true. It is possible that you don't know which way it is biased (or how much), but someone else might. What you think about is that you need to make a decision and want to let faith decide. Ie, to go left or right. In that case you could argue that your choice to couple left to Heads is equal to that you'd choose to couple right to Tails. In that case you'd be right but only because you (the one not knowing the bias) does that coupling. But what is a mean looking person gives you two guns and he says: tell me how you will decide A or B with this coin and then I'll link A to one or the other gun (only one of them is loaded); and then you can do your flipping - pick up the coupled gun and shoot yourself... Then chosen a strategy that gives you 50% chance for REAL is better (this guy is REALLY mean; he wants you dead).
To everyone stating that this 'solution' isn't valid after more than 1 flip, please note that at the time I answered this, the Question didn't ask for "repeatable process". This is clearly now, a redundant solution, but at core, is valid for tossing once, because even though the bias was NOT randomly assigned, it is never intimated to you as an observer, so the bias is random for you, for a single toss. And to answer Carlo Wood's comment, the observer would most definitely be dead if he chooses the biased side, but choosing that side in the first place, has a 50-50 chance for the observer.
Yes (if p = 0 , 1 ). Here are other ways of doing this by simulating a two player game:
Game 1 : In a round of this game, both player A and player B toss the coin. They get one point if they toss a "Head".
If after one round, there is equality, repeat. If not, you have a winner.
Since the game is symmetric, there is an equal probability for each player to win. Hence, we have a process which is the same as a fair coin flip.
Game 2 : In a round of this game, player A tosses the coin until he gets a "Head". He gets one point for each "Tail". Then player B does the same.
If after one round, there is equality, repeat. If not, you have a winner.
Since the game is symmetric, there is an equal probability for each player to win. Hence, we have a process which is the same as a fair coin flip.
Note: Much like the other solution by Varsha Dani, you might need to repeat for a very long time (especially if p is very close to 0 or 1).
Do the following:
A)
Toss the coin. Toss again. If the latest outcome is different from the previous outcome, stop tossing, else go on tossing until the latest outcome is different from the previous outcome.
Write down the number of tosses.
B)
Repeat A.
C)
-
In case the first number of tosses (A) was larger than the second number of tosses (B), call the outcome H
-
In case the first number of tosses (A) was smaller than the second number of tosses (B), call the outcome T
-
In case the first number of tosses (A) was equal to the second number of tosses (B), repeat A, B and C.
I used the top solution to get the awnser certainly but also I see this as a plausible solution: one person closes their eyes, the other one puts the coin in one of his/her hand unvisible to the other person, the other person then chooses in which hand the coin is, the human has 2 hands hence the probability of winning is 50% and therefore the odds are equal?
Assuming the people are honest.
You can (almost) always eat a fair outcome. (The almost is in the case of P=0,1)
You and your friend each flip the coin independently. Whoever gets heads wins. In the case of two heads or two tails, start over. This should eliminate all bias. In the case of P=0,1; this will loop infinitely (likely the best you could hope for).
And if P does equal one or zero? My best advice is to stop flipping coins with that person and play rock, paper, scissors instead.
From a Bayesian perspective: If we don't know the probability of heads and tails, then we can assign a probability 0.5 to heads and 0.5 to tails, since there is no prior preference to either side of the coin. Even if the coin has two heads or two tails. Just throwing the coin once has the same unpredictability as for any other coin, including the unbiased coin. But it can only be done once when we are in a state of complete ignorance , after that another method is required.
This is like guessing in which hand I have a candy. You don't know me, it can be in both hands with equal probability (from your perspective). I could even always play it by putting in my right hand, you just don't know that. Of course we only play it once like that.
So the answer to the question "Can you use this coin to generate an outcome that is effectively the same as a fair coin flip?" is yes .
Yes
Keep tossing the coin twice until the second toss is different to the first toss. That is, if the results of the two tosses is the same then discard and do another pair of tosses. p(HT | HT or TH) = p(TH | HT or TH). The result of the first toss is H or T with a 50% probability.
Assuming you have two contestants, have each person take turns flipping the coin. The first person to flip heads when the other person flips tails wins. Alternatively, the first to flip tails when the other flips heads wins.
Let’s say a biased coin will show heads 55% of the time, but you don’t know that just yet. If you flip the coin enough times, say 500 times, then you are going to see a definite pattern of heads coming up more often than tails. The number of heads coming up should be pretty close to 275, which is 55% of 500. A definite pattern can be determined because the biased coin won’t change the degree of biasedness.
For one fair game, flip the coin twice. If the results match (HH or TT) I win. If the results differ (HT or TH) you win.
For example if the coin is biased by 20% don't need to know which way):
P(HH or TT) = 0.3 + 0.2 = 0.2 + 0.3 = 0.5
P(HT or TH) = 0.25 + 0.25 = 0.5
Therefore the game is fair
This does not work. For instance if the coin is such that P(H) = 0.9, then P(HH or TT) is 0.82 which is way more than 0.5
Yes
You can use rejection sampling to simulate a fair coin flip as follows:
Note that P r o b ( H T ) = P r o b ( T H ) = p ( 1 − p ) . Thus you have an equal chance of the outcome being H or T on any particular trial. Moreover, the probability that a trial succeeds instead of being rejected is 2 p ( 1 − p ) > 0 . So after 2 p ( 1 − p ) 1 trials, in expectation, you will have produced an outcome.