wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Easy: COIN UNBIASING
        
(Message started by: Ion Rush on Jul 27th, 2002, 3:50am)
Title: Easy: COIN UNBIASING
Post by Ion Rush on Jul 27th, 2002, 3:50am
You and your arch rival are competing for the same girl. After years of battling, you both decide to settle it by tossing a coin.

Your rival produces a coin, but you don't happen to have one on you. You are certain that the coin your rival has produced is loaded, ie. it will come up with heads more than 50% of the time on average.

How do you arrange a fair contest, based purely on chance and not skill, by flipping this coin?


are these acceptable solutions

each person strives for the longest string of a single occurance
(i.e. heads heads heads heads tials would beat heads heads heads tails)

each person flipps the coin 10 times. The winner is the one who gets the most heads in those 10 tosses. Ties cause a repeat

the 2 guys and one girl flip the coin, The odd person out leaves and the two matching people date.(HHT, T leaves) If all 3 get the same result (likely with a biased coin) it is repeated.  If the girl gets the odd result the outcome is ignored.
Title: Re: Easy: COIN UNBIASING
Post by Adam Hanig on Jul 27th, 2002, 9:07am
Let us assume that each person has not already chosen a side.  This test relies on you, the one who did not bring the coin, calling it in the air.

So have him flip, and you call it.  The variability is now on what you call, so assuming you are completely ignorant as to how it is loaded (which your competitor assumes), then it is 1/2 from both perspectives, completely fair.

However, the way the question is worded indicates that you know the coin is loaded for heads.  Perhaps thats the only version of loaded coin they sell in town, or you switched it to while he wasn't looking.  Then just call heads, and things are in your advantage!
Title: Re: Easy: COIN UNBIASING
Post by srowen on Jul 27th, 2002, 11:11am
Another decent solution:

1) Flip the coin twice.
2) If you get HT, guy #1 wins. If you get TH, guy #2 wins. These are equally probably, regardless of p.
3) If you get HH or TT, go to step 1).
Title: Re: Easy: COIN UNBIASING
Post by BigBadBert on Jul 29th, 2002, 12:27pm
Place the coin on the ground (or table or back of your hand) where the other person can't see it and ask the other person to call it.

Just another possible way.
Title: Re: Easy: COIN UNBIASING
Post by william wu on Jul 29th, 2002, 1:39pm

on 07/27/02 at 11:11:17, srowen wrote:
Another decent solution:

1) Flip the coin twice.
2) If you get HT, guy #1 wins. If you get TH, guy #2 wins. These are equally probably, regardless of p.
3) If you get HH or TT, go to step 1).


Just to add some background, this was one of the classic problems mathematician John Von Neumann was interested in when he was developing game theory. Srowen's solution shown above is originally attributed to Von Neumann.

Here's a short paper on the subject:
http://www.ocf.berkeley.edu/~wwu/riddles/coinflip.pdf

I think BigBadBert's solution is pretty clever BTW  :)
Title: Re: Easy: COIN UNBIASING
Post by continuum on Aug 25th, 2002, 9:03pm
The first solution I thought was the same that srowen said.
But I tried to think in a solution with a limited number of flips, since you could have to wait a long time before it shows something like HT or TH. In fact, with a chance of 100% of H or T, you would wait forever. :o

Then and I arrived at the same solution of Adam Hanig, that uses only one flip.

When I read BigBadBert's solution, I thought of another tricky one:

You hide the coin in one of your hands, and ask your rival to guess which hand has it. Okay, this is too much tricky, I know.  ;D
Title: Re: Easy: COIN UNBIASING
Post by rfeague on Sep 7th, 2002, 4:43pm
How about this: we know that heads is more likely.  So both parties take turns flipping until they get tails.  Whoever gets tails in fewer flips wins.  If you both get tails on the first try, restart.  That seems more efficient than the other approaches.
Title: Re: Easy: COIN UNBIASING
Post by greatly_amuzed on Sep 8th, 2002, 11:25pm
A very practical solution: Why can't the girl just choose which bloke she likes better?  :D
Title: Re: Easy: COIN UNBIASING
Post by Icarus on Oct 9th, 2002, 8:53pm
Anyone have a solution to the variation (using a fair coin to produce a result with probability = P>.5). I know a solution, but will not pretend it is my own: I read it (perhaps from the same source as the esteemed Mr. Wu ;)). I'm curious to see if someone has a different idea!
Title: Re: Easy: COIN UNBIASING
Post by TimMann on Oct 11th, 2002, 12:58am
Icarus, you may need to explain that variation more clearly. What you seem to be saying is too trivial, so I'm assuming you meant something different. I.e., flip the fair coin twice, and say that you win if the flips were not both tails. Then p=0.75. You can obtain (or at least approximate as closely as you like) any probability with a sufficient number of flips.
Title: Re: Easy: COIN UNBIASING
Post by Icarus on Oct 11th, 2002, 3:16pm
What I mean is the variation that William Wu gives with the problem:

Quote:
Variation: (COIN BIASING) You and your rival are competing for the same girl, and decide to settle it with a coin toss. Your rival has known the girl longer than you have, so you agree that it is fair for him to have a chance of winning equal to P, where P > 0.5. However, you only have a fair coin. How can you conduct this contest such that the biased probability is manifested? What is the average number of coin flips needed to determine a winner?

The solution I refered to is exact, regardless of the value of P, though for some values of P, you could theoretically go on forever without deciding the question. ( The probability of this is zero, but that is not the same thing as saying it cannot happen.) I am curious if someone can find a different exact solution.
Title: Re: Easy: COIN UNBIASING
Post by Jonathan_the_Red on Oct 11th, 2002, 5:01pm
I have a solution to that as well, but I've known it for awhile so I don't remember if I came up with it myself or read it somewhere :) Probably the same as yours, Icarus.
Title: Re: Easy: COIN UNBIASING
Post by Pietro K.C. on Oct 11th, 2002, 7:11pm
  I just saw this, and thought it was very interesting! I had an idea, but I'm in a bit of a hurry, so excuse me if the following is all nonsense. :)

  Suppose you want to answer YES to a question with probability P.

  Given a number P such that 0 <= P <= 1, if you randomly choose a number x on the interval [0,1], there is a probability P that x will be less than P.

  All right. Now consider the binary expansion of P, which will be 0.b1b2... . There may be only zeroes after some point. Start flipping the fair coin, and interpret the n-th result as the n-th binary place (this sounds funny :)) of a real number r between 0 and 1. If some digit of r ever differs from the corresponding digit in P, stop.

  If the number r you obtained in this manner is less than P, answer YES. Otherwise, answer NO. It seems pretty clear to me that this achieves the desired result (with probability 0 that it goes on forever), but I also have a feeling this is the answer everyone already knows. :-/

  I also don't see the reason for the restriction p > 0.5... be patient, I'm REALLY in a hurry. ;D
Title: Re: Easy: COIN UNBIASING
Post by TimMann on Oct 11th, 2002, 9:52pm
Hi, Pietro. I'm sure that's correct, and it's probably what everyone had in mind. It's also what I had in mind when I said you could approximate the probability as closely as you like -- I was assuming a fixed bound on the number of flips, but if you let the number of flips be unbounded, you get an exact result.
Title: Re: Easy: COIN UNBIASING
Post by Icarus on Oct 12th, 2002, 9:13am
Yes, that was the solution I was refering to. I read it in a book by Martin Gardner (a collection of some of his Scientific American columns) many years ago! Say, William, how about you take over for Martin!:D After he retired, Sci-Am's replacements have never been as good. :'( The last I saw (I canceled my subscription after they decided to become a clone of "Discover") was a mere puzzle column, with little challenge, and no discussion. One thing I really like about this site is your appreciation that the true worth of a puzzle is not in simply finding a solution, but in the thought processes that lead to the solution, and in what new thoughts that solution can evoke!

There is no reason for the restriction P > .5. I assume that it is in there simply because the narration led to it.

Also, unless I've made an error :o, the average number of flips needed to decide the matter is 2.
Title: Re: Easy: COIN UNBIASING
Post by william wu on Jan 22nd, 2003, 1:29pm

on 08/25/02 at 21:03:17, continuum wrote:
When I read BigBadBert's solution, I thought of another tricky one:

You hide the coin in one of your hands, and ask your rival to guess which hand has it. Okay, this is too much tricky, I know.  ;D


Actually, I dunno what we were smoking on this one. The human mind is a poor random number generator. Your rival might be inclined to choose the right hand based on what he heard on the radio that morning or some other nonsense. It's like on that Regis show where they ask people to choose random numbers so an audience member can win something -- I'm sure some numbers get chosen much more often than others.
Title: Re: Easy: COIN UNBIASING
Post by william wu on Mar 17th, 2003, 7:41am
A colleague of mine recently suggested the following solution: just spin the coin. When the coin comes to rest, it's equally likely that the side facing up will be heads or tails. Do you think that's reasonable? On one hand, everyone probably spins coins with roughly the same force. On the other, the micro perturbations between the tabletop surface and the coin might be significant enough and random enough to make the outcome equiprobable.

On another note, if the heads side of a coin was heavier than the tails side, would that make the heads side more likely to face the floor after a flip? My intuition says no but I'm not confident. If the answer is no, how would you physically construct a biased coin?  
Title: Re: Easy: COIN UNBIASING
Post by Icarus on Mar 17th, 2003, 4:36pm
I don't know - My intuition tells me that the heavier side is more likely to come out on the bottom of a spun coin (assuming that the portion of the edge that is contacting the surface on which it is spinning is level and smooth). If one side of the coin is heavier than the other, then the coin's CG is going to be closer to that side. That means that the small perturbations of the coin's angle that eventually cause it to precess and fall over are more likely to reach the "point of no return" on that side than on the other.
Title: Re: Easy: COIN UNBIASING
Post by towr on Mar 17th, 2003, 11:13pm
it all depends on how you spin the coin.. I can bias it pretty well in my favour..
I can even do it with a die sometime (in the end it's pretty much deterministic classical mechanics, just a matter of throwing right)
Title: Re: Easy: COIN UNBIASING
Post by Chronos on Mar 20th, 2003, 7:42pm
Even ordinary coins which are "fair" (or as close an approximation as anybody could need) when flipped can be horribly biased when spun.  I think this is because of irregularities on the edge of the coin:  A slight taper, for instance, could cause this bias.  I once had a silver dollar which had about an 80-20 bias in favor of tails, when spun.  On the other hand, if neither you nor your rival know in which direction the coin is spin-biased, then it's fair for much the same reason that "Call it in the air" is.
Title: Re: Easy: COIN UNBIASING
Post by ozzz169 on Feb 10th, 2009, 1:43pm
I know this is old but I am new so here is my 2 cents:

fav answer to get the fair one...  

just guy that calls it cant be the guy who brought the coin as he has 50% chance of calling what it will land on regaurdless of how its biased... could land on heads 100% but he does not know that so he has 50% chance to call heads... and therfor 50% chance to win.

for the unbias to creat bias....

I am sure there is more elegent way to the second question... but I would just give the odds..... for example if p=.6 then he should have 60 percent and other guy 40 then he has to get to 4 wins before you get to 6 wins...... lets just hope p=a rational number or this would not work as they would take forever.. if p= .6534214564 then i got to get to that before he gets to 1-p and that will take a while :)

in other words I have to get p wins and he has to get to 1-p wins... you can also reduce when possible. ex above he could get to 2 wins before I get to 3 is still valid.
Title: Re: Easy: COIN UNBIASING
Post by Grimbal on Feb 12th, 2009, 9:09am

on 03/17/03 at 07:41:45, william wu wrote:
A colleague of mine recently suggested the following solution: just spin the coin. When the coin comes to rest, it's equally likely that the side facing up will be heads or tails. Do you think that's reasonable? On one hand, everyone probably spins coins with roughly the same force. On the other, the micro perturbations between the tabletop surface and the coin might be significant enough and random enough to make the outcome equiprobable.

Actually, coins are not disks but cylinders.  They have 2 edges.  When they spin they spin on only one edge.  And on a flat surface the edge doesnt' tend to change.  If you start spinning the coin with one side facing up slightly, that side is likely to end up.
Title: Re: Easy: COIN UNBIASING
Post by singh_sukhu on Sep 29th, 2009, 4:01am
This wasn't as easy as it looked!

My solution to the first part is : The girl tosses the coin. The first person makes a call (heads or tails,doesn't matter!). Now only the girl and first person see the outcome. It is simply win(i.e, he got what he called) or loose. Now the second person has to choose whether he wants this outcome for himself or the first person.

My solution to the second part : Consider probability of first person required is p/q. Now we do something like in the famous "the three doors" probability problem.
Step1: The second person tosses the coin 'mq' times and note the number of heads and tails that occur. He gives this list of outcomes to the girl in an envelope, which the girl is not allowed to open right now.
Step2: The second person asks the first person to tell the number of total heads(or tails,whatever. Its the choice of the second person) that occurred.
Step3: The first person may now chooses 'mp' numbers from "1..mq" (all are equally likely to occur).
Step4: Now, as in the "three doors problem" the second person reveals to him k number of incorrect options. The girl now chooses for the first person whether he should flip the choice or stay with it.
Now if he stays with it the probability of him winning is obviously mp/mq=p/q. If  he flips the probability of him winning would be ((mq-1)/mq)*1/(mq-k-1). Lets call this A. values of m and k may be so chosen according to given p such that A=p/q.
Title: Re: Easy: COIN UNBIASING
Post by Grimbal on Sep 29th, 2009, 6:58am

on 07/27/02 at 03:50:51, Ion Rush wrote:
If the girl gets the odd result the outcome is ignored.

Why  >:( .

;)
Title: Re: Easy: COIN UNBIASING
Post by singh_sukhu on Oct 1st, 2009, 3:27am
i think i have made some calculation errors...

Any ways I hope my idea is clear...
Title: Re: Easy: COIN UNBIASING
Post by towr on Oct 1st, 2009, 3:53am

on 10/01/09 at 03:27:50, singh_sukhu wrote:
i think i have made some calculation errors...

Any ways I hope my idea is clear...
The first one is; the second not so much. For one thing, you say "values of m and k may be so chosen according to given p such that A=p/q", but there is no guarantee such m and k can be chosen as integers as would be required.
But I'm not really clear on the rest either. In step 1, the number of heads/tails follows a binomial distribution; I see nothing that takes this into account later on.

Maybe you could give an example of how the process works? For, say, p=3, q=7 ?
Title: Re: Easy: COIN UNBIASING
Post by singh_sukhu on Oct 1st, 2009, 8:27am
Yes. I made that mistake . I noticed it later.
I'd rather have to work on them equations.
However the idea was that probability changes in 'three doors problem'. Can some similar logic be used here...??

Meanwhile google churned out something to chew upon..
http://www.eecs.umich.edu/~qstout/abs/AnnProb84.html

PLUS my method of the first part just requires one toss! :)
Title: Re: Easy: COIN UNBIASING
Post by BenVitale on Oct 7th, 2009, 1:38pm
I wonder if you flip a coin n times and you get n-1 Tails, and on the n-th trial Heads, what are the chances that your coin is unfair?

Adding a background to Von Neumann simple method : Flip the coin twice. If it comes up heads followed by tails, then call the outcome HEAD. If it comes up tails followed by heads, then call the outcome TAIL.

Persi Diaconis' Dynamical Bias in the Coin Toss (http://siamdl.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SIREAD000049000002000211000001&idtype=cvips&gifs=Yes
)

And,

The author uncovers bias in a flip of a coin (http://news-service.stanford.edu/news/2004/june9/diaconis-69.html)

The author says, flipped coins tend to come up the same way they started ... For natural flips, the chance of coming up as started is about .51 .... a flipped coin is more likely than not (51%) to come up the same way it started.
Title: Re: Easy: COIN UNBIASING
Post by singh_sukhu on Oct 7th, 2009, 11:52pm

on 10/07/09 at 13:38:32, BenVitale wrote:
The author uncovers bias in a flip of a coin (http://news-service.stanford.edu/news/2004/june9/diaconis-69.html)

The author says, flipped coins tend to come up the same way they started ... For natural flips, the chance of coming up as started is about .51 .... a flipped coin is more likely than not (51%) to come up the same way it started.

This conclusion was reached after studying merely '25' tosses. Isn't the number too less?!!
Title: Re: Easy: COIN UNBIASING
Post by singh_sukhu on Oct 7th, 2009, 11:57pm

on 10/07/09 at 13:38:32, BenVitale wrote:
I wonder if you flip a coin n times and you get n-1 Tails, and on the n-th trial Heads, what are the chances that your coin is unfair?


No matter how many tosses with a given coin we do , and study the outcomes, the outcomes alone can never prove that the coin is biased or unbiased.
Title: Re: Easy: COIN UNBIASING
Post by towr on Oct 8th, 2009, 12:41am

on 10/07/09 at 23:52:31, singh_sukhu wrote:
This conclusion was reached after studying merely '25' tosses. Isn't the number too less?!!
Considering that one coin flip accounts for 4%, yes. You can't even get 51% of one outcome.


on 10/07/09 at 23:57:25, singh_sukhu wrote:
No matter how many tosses with a given coin we do , and study the outcomes, the outcomes alone can never prove that the coin is biased or unbiased.
It can give overwhelming support to the hypothesis though. It is extremely unlikely to get predominantly one side of a coin turning up in a fair coin.
Title: Re: Easy: COIN UNBIASING
Post by Pyotr on Jan 24th, 2011, 9:31am

on 07/27/02 at 11:11:17, srowen wrote:
Another decent solution:

1) Flip the coin twice.
2) If you get HT, guy #1 wins. If you get TH, guy #2 wins. These are equally probably, regardless of p.
3) If you get HH or TT, go to step 1).


Another possibility would be to have the condition that both players must always call either Heads or Tails.

They must both bet on the same side of the coin.

Would that work?

For biasing an unbiased coin, one could simply multiply one player's result by a factor that gave them the needed handicap. This is not as elegant as the binary digit solution, of course, as it doesn't set a limit for the number of throws needed for a fair result, but it should get the job done.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board