wu :: forums - Print Page


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

        riddles >> easy >> using a biased coin to make an unbiased decision
        
(Message started by: BenVitale on Feb 7^th, 2010, 7:50pm)

Title: using a biased coin to make an unbiased decision
Post by BenVitale on Feb 7^th, 2010, 7:50pm

You and your friend use a biased coin to make an unbiased decision.

Note that the bias is not known exactly.

Both of you want to choose between 2 options, say

Option #1: go to a movie.
Option #2: stay home and play video games.

How can you use the biased coin to make a decision so that either option -- movie or video games -- is equally likely to be chosen?

Title: Re: using a biased coin to make an unbiased decisi
Post by Grimbal on Feb 8^th, 2010, 12:51am

[hide]
Toss 2 coins. If it is HT: movie. If it is TH: video games. If it is HH or TT, restart.
[/hide]
An interesting question is how to minimize the number of coin tosses. You can improve on the method above.

Title: Re: using a biased coin to make an unbiased decisi
Post by towr on Feb 8^th, 2010, 2:30am

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1027805268;

Title: Re: using a biased coin to make an unbiased decisi
Post by BenVitale on Feb 8^th, 2010, 9:49am

Thanks for the link, because I found on page 1

http://www.ocf.berkeley.edu/~wwu/riddles/coinflip.pdf

On page 2, I did post a message, I don't remember whether I read page 1.

Grimbal asked

Quote:

... how to minimize the number of coin tosses.

If we toss the biased coin, we still get 4 possible outcomes:

HH, HT, TH, TT

If we set the probability of getting Heads p, and the probability of getting Tails (1 - p)
P(H) = p
P(T) = 1 - p

then,

P(HH) = p²
P(TT) = (1 - p)²
P(HT) = p(1 - p)
P(TH) = (1 - p)p

Events HT and TH are equal.

And if we can agree before tossing the coin twice that:

- Event HT is H
- Event TH is T

And if we get HH and TT we need to repeat the experiment

I still need to figure out the minimum of coin toss.

I'm going to read the PDF file and look for hints or solution.

Title: Re: using a biased coin to make an unbiased decisi
Post by mmgc on Feb 9^th, 2010, 9:25pm

on 02/08/10 at 09:49:14, BenVitale wrote:

For each toss (independent events), we can club the outcome with the previous result -- check if it is HT or TH & decide the option...for e.g if HHT comes take HT as decision -- thus no need for the 4th toss..thus we can decrease the number of toss required...

Title: Re: using a biased coin to make an unbiased decisi
Post by rmsgrey on Feb 10^th, 2010, 8:34am

on 02/09/10 at 21:25:48, mmgc wrote:

That doesn't seem to work - it's equivalent to tossing the coin until you get a different result than the one you started with, which, assuming p is neither 0 nor 1, is equivalent to letting the first toss decide the result...

Title: Re: using a biased coin to make an unbiased decisi
Post by mmgc on Feb 11^th, 2010, 3:17am

on 02/10/10 at 08:34:48, rmsgrey wrote:

Thanks for pointing out my mistake.

Another way…

We can repeat if nothing is decided after a group of 2 or 4 or 8 and so on ….(2n) outcomes.
There should be equal series of heads and tails in the group to decide. for e.g HT or TH, HHTT or TTHH (we cannot decide if 2nd toss is H and 3rd toss is T because they are not in same group of 2) , HHHHTTTT or TTTTHHHH and so on…

In group of 2…
If HT or TH comes in subsequent 2 toss then we can decide. Start another group of 2.
In group of 4…
Say, HH comes in first 2 then if TT comes in next 2, we can decide. Similarly, we can decide if TT comes in first 2. But, if the result is HHHH or TTTT then start another group of 4.

Title: Re: using a biased coin to make an unbiased decisi
Post by Grimbal on Feb 11^th, 2010, 5:36am

Yes it works.

If you open the link in BenVitale's post, you will see that method explained under "Problem 4".