Fair toss
As you know, most coins are not perfect (i.e. the probability of heads is not equal to the probability of tails). So here is a simple probability exercise. Given a biased coin with P(heads)=p (obviously p is not a half), how would you simulate a fair coin?
-Satish
-Satish
posted by littlecow at 5/23/2006 10:01:00 AM
13 Comments:
Can't we do what Vegas does?
Assume ph is a fraction. ph=a/b
The ref says she will toss the coin b times. The bettor must call beforehand if # of heads will be <=(or >) a.
I am unable to think immediately of a way to
a. use 1 coin flip
b. simulate non-proper-fraction ph values (unless u make b obscenely high)
Sai: (regarding your comment on the previous puzzle) flip the coin as in relabel heads as tails and vice versa? That sounds close -- could you elucidate further?
-Satish
Sai: (regarding your comment on the previous puzzle) flip the coin as in relabel heads as tails and vice versa? That sounds close -- could you elucidate further?
-Satish
Whoops -- it looks like we posted at the same time and blogger went crazy! Anyway, sisyphus, your scheme would work -- but there are two assumptions to your solution that are not needed in the solution I am looking for:
1) That p is a proper fraction (which is not too bad -- as you said -- we can always make b big enough)
2) That p is known (which is quite restrictive).
To further clarify, you can toss the coin any number of times to get this solution..
-Satish
Flip two identical coins labelled A and B. Call HT or TH.
Alternatively, instead of a single flip, flip twice and call HT or TH.
littlecow great! perfect answer. A bit of history to the question. This is a recurring theme in cryptographical problems and was first tackled by Neumann who suggested this same solution (The algorithm is called Neumanns Algo after him). Since then, there has been much progress on this topic and it is still an area of reserach as a simple google search with "neumann coin toss" will reveal.
-Satish
@satish: whats your email? i will get you added as a contributor...
vedantam@gmail.com -- Thanks Balaks!
Ok. Time for another simple puzzle. You are sentenced to be hanged by the neck till death. Arnie (the governor) agrees to pardon you if you can solve this puzzle for him (since he is thickheaded as we all know). You are given a deck of 52 cards in a dark room (so you cannot see the cards). You are told from the get go that exactly 17 of these cards are face up (and the tactile feel of the cards is the same on both sides). The question then is to split the deck into two stacks which have the same number of face up cards.
Very interesting problem. And nice job littlecow.
...Although I was also under the impression that you might interested in a method that is guaranteed to end before the bar's last call! Another example of death by assumption.
Hey,I thought you said only one coin was available! So I thought the coin could be tossed and every alternate toss, an extra flip is given to the coin...orthat the face value of the sides are interchanged....
>littlecow:How to account for HH or TT occurrences?
sai: you dont have to. just take them as retoss scenarios. alternately, include HT or HH into a single outcome and TH or TT into the opposing outcome... its quite simple actually once you realize that two consecutive outcomes are independent events.
I can solve this problem, but Harold Reiter is smarter than me. See Problem 8 at http://www.math.uncc.edu/~hbreiter/problems/Torontost.pdf
Post a Comment
<< Home