Author |
Topic: using a biased coin to make an unbiased decision (Read 8613 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
using a biased coin to make an unbiased decision
« on: Feb 7th, 2010, 7:50pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: using a biased coin to make an unbiased decisi
« Reply #1 on: Feb 8th, 2010, 12:51am » |
Quote Modify
|
Toss 2 coins. If it is HT: movie. If it is TH: video games. If it is HH or TT, restart.
An interesting question is how to minimize the number of coin tosses. You can improve on the method above.
|
| « Last Edit: Feb 8th, 2010, 12:52am by Grimbal » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: using a biased coin to make an unbiased decisi
« Reply #3 on: Feb 8th, 2010, 9:49am » |
Quote Modify
|
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) = p2
P(TT) = (1 - p)2
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: using a biased coin to make an unbiased decisi
« Reply #4 on: Feb 9th, 2010, 9:25pm » |
Quote Modify
|
on Feb 8th, 2010, 9:49am, BenVitale wrote:
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) = p2
P(TT) = (1 - p)2
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. |
|
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...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: using a biased coin to make an unbiased decisi
« Reply #5 on: Feb 10th, 2010, 8:34am » |
Quote Modify
|
on Feb 9th, 2010, 9:25pm, mmgc 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... |
|
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...
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: using a biased coin to make an unbiased decisi
« Reply #6 on: Feb 11th, 2010, 3:17am » |
Quote Modify
|
on Feb 10th, 2010, 8:34am, rmsgrey 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... |
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: using a biased coin to make an unbiased decisi
« Reply #7 on: Feb 11th, 2010, 5:36am » |
Quote Modify
|
Yes it works.
If you open the link in BenVitale's post, you will see that method explained under "Problem 4".
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print