7 ms·
How to turn a biased coin into a Fair Coin
- bdhe 15y agoInterestingly, the Euro, when introduced back in the early 2000s was considered biased and even led to a statistician testing it out. http://www.newscientist.com/article/dn1748 http://www.newscientist.com/article/dn1748
- imurray 15y agoThe statement about spinning is too weak. You have to spin rather than flip to try to reveal bias: http://www.stat.columbia.edu/~gelman/research/published/diceRev2.pdf http://www.stat.columbia.edu/~gelman/research/published/dice... As for the statistical significance, here's another view of how to do it: http://www.inference.phy.cam.ac.uk/mackay/abstracts/euro.html http://www.inference.phy.cam.ac.uk/mackay/abstracts/euro.htm...
- eridius 15y agoThis article claims this algorithm is very likely happening inside my computer right now, but it doesn't elaborate. Why would my computer be performing this algorithm?
- adrianN 15y agoSome processors have a hardware random source. Due to manufacturing problems these are usually biased, but can still be used because of this algorithm.
- aantthony 15y agoFrom http://en.wikipedia.org/wiki/Randomness_extractor http://en.wikipedia.org/wiki/Randomness_extractor: Randomness extractors are used widely in cryptographic applications, whereby a cryptographic hash function is applied to a high-entropy, but non-uniform source, such as disk drive timing information or keyboard delays, to yield a uniformly random result. Is that what he is talking about?
- deleted 15y ago[deleted]
- tyree732 15y agoThis works and is very intuitive, but loses quite a bit of the coin flip's entropy in the process. There are more efficient algorithms, such as http://www.eecs.umich.edu/~qstout/abs/AnnProb84.html http://www.eecs.umich.edu/~qstout/abs/AnnProb84.html , which better use the entropy generated by the coin flip.
- deleted 15y ago[deleted]
- DanBC 15y ago...but in the context (a children's book, teaching simple concepts of logic and math and programming) something that is intuitive is what's needed. (But thanks for the nice link!)
- imurray 15y agoOne solution I heard has a basic idea that's quick to explain, although the details are messy. It might be interesting to get some intution: Flip the coin N times and count the number of heads, K. You got one of the C = {N \choose K} = N!/((N-K)!K!) ways of getting K heads, all of which have the same probability, no matter what the bias of the coin is. If you consider an ordering of the C choices, then you have an integer from 0 to C-1 drawn uniformly at random. You could represent that integer using binary and extract about log_2(C) random bits. For large N, the number of bits extracted is nearly the optimal NH bits, where H is the binary entropy of the coin. To count how far through a list of combinations I am for large N, I might construct a lattice and, I'm guessing, start reproducing works referenced by the paper that the parent linked to. Whereas the paper itself seems to have, from my quick skim, the definitive answer. Nice. As tucked away in another comment, related is: http://en.wikipedia.org/wiki/Randomness_extractor http://en.wikipedia.org/wiki/Randomness_extractor
- 0x12 15y agoIf I set the slider to 50% then it still wants me to flip 3 times. At 50% one flip would do. There should be at least an exception for that situation, I can't imagine I'm being alone in testing the edge cases first.
- sp332 15y agoThe point is, you don't know ahead of time what the bias is. In that case, you have to keep flipping until you get a head followed by a tail, or a tail followed by a head. If the coin happens to have no bias, you should expect to flip 3 times before you get one of those results.
- adrianN 15y agoThe algorithm doesn't care for the edge case and still throws away HH and TT. That case has probability 0 anyway, if the bias is continuous.
- aristus 15y ago50/50 is a special case. You don't need to use the von Neumann extractor. This algo is for sources of randomness that you suspect have a bias. But if you did use this algo on a 50/50 coin, half the time you'll get an HH or TT and have to start over. The other half of the time you'll get an HT or TH and return. So, on average, you'll need to do 3 flips for each execution of the algo.
- 0x12 15y agoSure, I get that. But that's why the bias can never be a (discrete) input, it is an emergent property of some unknown piece of matter, not something you set with a slider in steps of 1%. As the coin gets more biased you'll need to flip more often to get a HT or TH pair with the amount of bias showing up as the frequency of the heads and tails over a longer run. But the interesting bits are right around the middle where you can take a coin that is nearly perfect and use it in a perfect way, even when you can't even find out in finite time if the coin is perfect or not (and I would expect no real life coin to be perfect, but I would expect them to be so good as to be undetectable in a reasonable amount of time, 50/50 to me is 'perfection', I can't tell the left 50 from the one on the right). The 'edge case', a perfect coin does not need three flips, it just needs one. If that's not the intended outcome you could either remove that 50/50 point or handle it correctly. One of the more elegant ways of doing that would be to go from 49.9 to 50.1 or so, or an even smaller difference from the true center.
- blahedo 15y agoWhat I particularly like here is that the title of the article, and thus the title of the HN post, fully conveyed the puzzle, so I was able to think about it for a moment before reading the article, solve it, and then confirm that I had the correct answer. Always a happy moment. :)
- deleted 15y ago[deleted]
- swaraj 15y agoCool article, I got asked this question during my FB interviews and had luckily seen something exactly like this before.
- aristus 15y agoIf you did, then it was very likely me interviewing you, and you should have said that you had seen it before. #busted :D
- hugh3 15y agoWell, this is why you shouldn't be using semi-well-known problems as interview questions.
- aristus 15y agoA fair cop. :) I used to ask it as a follow-up to a much harder, less "ah-ha" question, to see how candidates approach probability.
- gujk 15y agoI thought brainteaser trivia interviews were left back at Microsoft in 2002.
- burgerbrain 15y agoWhy would they be? They're immensely useful tools.
- vsl2 15y agoIf you like these types of puzzles, the biggest online collection I've found is at: http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
- Steko 15y agoRelated: I vaguely recall hearing of a p2p game client where dice rolls were needed and to secure against cheating they polled each client and took the modulo of the sum of responses (iirc). You get unbiased outcomes as long as one player doesn't cheat.
- bretthopper 15y agoIf anyone is wondering, the interactive calculator is done using Tangle (http://worrydream.com/Tangle/ http://worrydream.com/Tangle/) made by Bret Victor (most recently of http://worrydream.com/#!/LadderOfAbstraction http://worrydream.com/#!/LadderOfAbstraction fame). Good to see more examples of it in the wild.
- losethos 15y agoYou knew this. http://bible.cc/proverbs/16-33.htm http://bible.cc/proverbs/16-33.htm 10 i = i + 1 20 IF i > 99999 THEN i = 0: PRINT ".";: GOTO 10 30 IF INKEY$ = "" THEN 10 40 PRINT "Line:", i Line: 23709 God says... said unto him, Why have I found grace in thine eyes, that thou shouldest take knowledge of me, seeing I am a stranger? 2:11 And Boaz answered and said unto her, It hath fully been shewed me, all that thou hast done unto thy mother in law since the death of thine husband: and how thou hast left thy father and thy mother, and the land of thy nativity, and art come unto a people which thou knewest not heretofore. 2:12 The LORD recompense thy work, and a full reward be given thee of the LORD God of Israel, under whose wings thou art come to trust.
- jhamburger 15y agoMaybe I'm crazy and it's the end of the day and my reading comprehension is shot, but I honestly can't even understand what the question is. Can somebody explain?
- impendia 15y agoYou have a coin which is weighted, so it comes up heads 70% of the time and tails only 30%. Or worse yet, perhaps you don't even know what frequency it comes up heads. Given such a coin, and nothing else, how can you simulate a fair single coin flip?
- y3di 15y agoThe question is how can you use a biased coin to reproduce an unbiased coin flip. In this article, they give the example of a coin that flips heads 70% of the time. Their method was to flip the coin twice. They only considered cases where heads was flipped once and tails was flipped once because these cases both had a 21% chance of happening. So both cases have the same chance of occurring. In order to differentiate between the two cases, you consider the first coin flip to be your result. So heads than tails is the same as getting a heads and tails than heads is the same as getting a tails.
- prof_hobart 15y agoA fair coin would be one that is equally likely to land on either heads or tails when tossed - on any given toss, you have exactly a 50% chance of getting either heads or tails. A biased coin, on the other hand, has a bias towards one side or another - e.g. you could have a coin that lands on heads 75% of the time. The question is - if you've got a biased coin, how do you get it to behave like the fair coin? It's probably easier to imagine a 10 sided die. You've got one with 7 sides painted red and 3 painted blue, so you've got a 70% chance of rolling red on any given roll. But you and your friend want to be able to use this die to decide who's round it is next - guess the right colour and it's the other guy's round. If you were to base this on a single role, you'd obviously both want to pick red. So what you want is to be able to use this die to create two outcomes which are both equally likely to happen. Does that help?
- ch0wn 15y agoOne of the few sites, where I don't need to use my iReader chrome extension to read the text. I love the font and the hyphenation using the sweet-justice JS script seems to work out great.
- biot 15y agoThe hyphenation seems a bit off. The word mathematical is split as "mat-hematical" which I'm quite sure is incorrect.
- grot 15y agoThis is a pretty well known problem. (First problem the professor in my undergrad algorithms class ever gave to us) SPOILER p = probability of heads 1 - p = probability of tails. flip the coin twice: head head = p^2 head tail/tail head = 2p(1-p) tail tail = (1 - p)^2 Notice the two in the middle there. We can just say head tail = Heads and Tail Heads = Tails. If we get HH or PP, just do it again. Ok, now call the above procedure, our "randomization algorithm" we can calculate the expected running time -- our algorithm succeeds with probability 2p(1-p). The number of trials we need to run our algorithm for is a geometric random variable. Thus, the expected running time is 1/(2p(1-p)).
- granfalloon 15y agowhy is H/T equal to 2p(1-p) rather than p(1-p)?
- mkl 15y agoHT is p(1-p), and TH is also p(1-p), so HT/TH (i.e. either of these) is 2p(1-p).
- mikhael 15y agothanks for writing this. the formula used in the webpage, (HH+TT+HT)/TH, appears to be off by one. i calculated it myself from the series, i.e. sum(n=0 to inf, 2(n+1)2pq(p^2+q^2)^n), and through the algebra i work it out to the same as yours (doubled). i'm not sure how the author's formula was derived, but i get the same result calculating the series for a slightly different (but wrong) algorithm: just keep flipping until HT or TH appears (not flipping by pairs). this series is sum(n=1 to inf, (n+1)(qp^n + pq^n)), i.e. sum(n=0 to inf, (n+1)(qp^n + pq^n)) - (p+q). the series works out to 1/(p(1-p)), but that last term would account for the one-off difference.
- aristus 15y agoGood point. I am going off of the original algo by von Neumann, which throws away both flips if you get HH or TT. There are many others, and I don't see any reason against your optimization, if the flips are truly independent. http://www.fas.harvard.edu/~libcs124/CS/coinflip3.pdf http://www.fas.harvard.edu/~libcs124/CS/coinflip3.pdf
- jasny 15y agoI would say both parties flip the coin. The one that throws heads wins. If they both throw the same, they need to throw again. Easy and effective :)
- dennyabraham 15y agoi'm not sure if i understand the problem. couldn't you just take the inverted result of every other flip?
- wnight 15y agoNo. With a large bias you'd have hundreds of one result for one of the other.
- dhruvbird 15y agoThis sounds simpler - if it works (can anyone confirm it?) * We maintain a fair coin abstraction that contains an unfair coin. * Along with the unfair coin, we also maintain a counter 'C'. * 'C' starts from 0, counting up 1 every time the coin is flipped. * If C % 2 == 0 then we report the value of the unfair coin's toss. Otherwise, we reverse the value of the unfair coin's toss and report it.