|
|
| Probability Discussions of probability theory |
02-05-2012, 02:53 PM
|
#1
|
|
Administrator
Join Date: Aug 2002
Posts: 9,437
|
Cute Little Coin Problem I Made Up
The are numerous variations on this and the general case is probably worthy of a thesis if it hasn't already been done. But first lets do a relatively simple case.
You have three coins that appear identical that are labelled A, B, and C. You know that two are fair but that one comes up heads 60% of the time. You are allowed to flip a coin, note its results, and then flip the same or different coin, note its results, and altogether make four flips. After that experiment you must make your best guess as to which coin is unfair (that might require a random guess between coins, depending on your experimental results.)
What flipping strategy should you use? What are the chances your guess will be right?
Hint:
If you were allowed only one flip, your chances would be the one third chance you picked the bad coin to flip, times the 60% you got a head, plus the two thirds chance the bad coin was unpicked time the 50% chance of a tail, times the 50% chance you chose correctly between the unflipped coins. Thats 20% plus 16 2/3 % which is 36 2/3%. With two flips allowed, you need to decide whether to flip the first coin twice.
|
|
|
|
02-06-2012, 07:41 AM
|
#2
|
|
centurion
Join Date: Dec 2011
Posts: 127
|
Re: Cute Little Coin Problem I Made Up
Quote:
Originally Posted by David Sklansky
The are numerous variations on this and the general case is probably worthy of a thesis if it hasn't already been done. But first lets do a relatively simple case.
You have three coins that appear identical that are labelled A, B, and C. You know that two are fair but that one comes up heads 60% of the time. You are allowed to flip a coin, note its results, and then flip the same or different coin, note its results, and altogether make four flips. After that experiment you must make your best guess as to which coin is unfair (that might require a random guess between coins, depending on your experimental results.)
What flipping strategy should you use? What are the chances your guess will be right?
Hint:
If you were allowed only one flip, your chances would be the one third chance you picked the bad coin to flip, times the 60% you got a head, plus the two thirds chance the bad coin was unpicked time the 50% chance of a tail, times the 50% chance you chose correctly between the unflipped coins. Thats 20% plus 16 2/3 % which is 36 2/3%. With two flips allowed, you need to decide whether to flip the first coin twice.
|
After 5 mins with pen + paper I guess that, because
- 60% is "close" to 50%
- the number of flips is "a little more" than the number of coins
That any strategy almost certainly involves flipping all coins once then selecting your remaining relatively small number of flips based on the result of these first flips.
So with regard to the specific case you go
1. A
2. B
3. C
4. ?
Where ? depends on the results of flips 1-3.
While this is obvious-ish and intuitive, I think it is important to note that if you shifted the biased coin to - say - 99%, then your strategy may not follow the above. Or if you had 3 coins and 10 flips, etc.
OK off to lunch more thinking later.
|
|
|
|
|
02-06-2012, 11:40 PM
|
#3
|
|
Pooh-Bah
Join Date: Feb 2005
Posts: 4,013
|
Re: Cute Little Coin Problem I Made Up
The obvious and intuitive is sometimes dangerous. The answer, as they say, is too big to fit in this margin for 4 flips (but plenty too small to be a thesis.)
In the case of 2 flips, the strategy is decidedly non-intuitive:
Pick a coin and flip it.
If it comes up heads, flip the same coin again. If it comes up heads a second time, guess that coin; if tails, guess at random from one of the unflipped coins.
If it comes up tails, pick another coin to flip. If it comes up heads, guess that one, if tails, guess the third one.
Has a 38.67% chance of success.
Four may be a 'maximally interesting number', at least if the greedy algorithm (maximizing information gained from each flip) is close to optimal.
|
|
|
|
|
02-07-2012, 01:45 AM
|
#4
|
|
Administrator
Join Date: Aug 2002
Posts: 9,437
|
Re: Cute Little Coin Problem I Made Up
Quote:
Originally Posted by Siegmund
The obvious and intuitive is sometimes dangerous. The answer, as they say, is too big to fit in this margin for 4 flips (but plenty too small to be a thesis.)
In the case of 2 flips, the strategy is decidedly non-intuitive:
Pick a coin and flip it.
If it comes up heads, flip the same coin again. If it comes up heads a second time, guess that coin; if tails, guess at random from one of the unflipped coins.
If it comes up tails, pick another coin to flip. If it comes up heads, guess that one, if tails, guess the third one.
.
|
The thesis would concern x flips of y coins where the biased coin is z% to be heads
And the strategy for two flips IS intuitive. Once you realize that a coin flipped twice that gets even one tail is less likely to be biased than an unflipped coin
|
|
|
|
|
02-07-2012, 10:23 AM
|
#5
|
|
journeyman
Join Date: Sep 2004
Posts: 298
|
Re: Cute Little Coin Problem I Made Up
Quote:
|
The thesis would concern x flips of y coins where the biased coin is z% to be heads
|
After recalculating x = 1 and 2 for y = 3 coins and z = 60%:
You flip 1 coin as long as your actual H-%>(z+50%)/2 when actual H-%<(z+50%)/2 you start with the next coin and so on.
You pick the coin with actual H-%>(z+50%)/2 or an unknown coin.
In this example: x=4, y=3, z=60%
A: HHHH => pick A (actual H-% = 100%)
A: HHTH => pick A (actual H-% = 75%)
A: HHTT => pick B or C (A's actual H-% = 50%)
A: HT -> B: T -> C: H => pick C (actual H-%= 100%)
Not thought completely through but it looks cool 
When x gets very high you end up flipping the biased coin because actual H-% won't go below (z+50%)/2
Last edited by cyberfish; 02-07-2012 at 10:44 AM.
|
|
|
|
|
02-07-2012, 06:44 PM
|
#6
|
|
Administrator
Join Date: Aug 2002
Posts: 9,437
|
Re: Cute Little Coin Problem I Made Up
I want to know the chances that the best guess (using the best strategy) is correct in terms of x, y, and z. I think the precise answer to the Sklansky Coin Problem is not easy to find and has probably never been tackled.
(Just in case this is indeed a new problem I should probably reassign letters. You have n coins. One is unfair in that heads comes up y percent. You have a total of z flips to determine which coin is unfair. You choose which coin to flip after noting the results to that point. If you use your best strategy the chances that your guess as to which coin is biased is what, in terms of n, y, and z?)
|
|
|
|
|
02-08-2012, 06:51 AM
|
#7
|
|
journeyman
Join Date: Sep 2004
Posts: 298
|
Re: Cute Little Coin Problem I Made Up
Quote:
Originally Posted by David Sklansky
I want to know the chances that the best guess (using the best strategy) is correct in terms of x, y, and z. I think the precise answer to the Sklansky Coin Problem is not easy to find and has probably never been tackled.
|
I hope so because I think I've tackled it down for every x,y,z.
3 coins, 4 flips and biased coin of 0.6:
Optimal strategy (cfr raw lines in my previous post) gives you 40.91%
I post my conclusion later on: accurate optimal strategy, different ways to calculate the odds (prior to the trials and in every trial-scenario).
Because I started programming I will try to automate this for every x,y,z.
|
|
|
|
|
02-08-2012, 04:40 PM
|
#8
|
|
journeyman
Join Date: Sep 2004
Posts: 298
|
Re: Cute Little Coin Problem I Made Up
Optimal strategy is very simple:
You always choose the coin with the highest probability of getting H on the next throw (always the same calculation):
A) When you decide which coin you throw next.
Example: 3 flips
Coin 1: H T
Coin 2: -
Coin 3: -
What will my last throw be?
B) When you decide which is the biased coin.
Example: 2 flips
Coin 1: H T
Coin 2: -
Coin 3: -
Which is the biased coin?
In both A) and B) (3 coins and 0.6 H-bias) you choose either Coin 2 or 3.
I've written some Java-code: (could be some calcs are still incorrect)
I can select any amount of coins, flips and bias.
You can find overall probability (prior to the trials) below the trials.
I post 2 simple results:
Last edited by cyberfish; 02-08-2012 at 04:57 PM.
|
|
|
|
|
02-08-2012, 04:49 PM
|
#9
|
|
journeyman
Join Date: Sep 2004
Posts: 298
|
Re: Cute Little Coin Problem I Made Up
|
|
|
|
|
02-08-2012, 05:36 PM
|
#10
|
|
journeyman
Join Date: Sep 2004
Posts: 298
|
Re: Cute Little Coin Problem I Made Up
Wording might be confusing/incorrect:
Prob. of Heads is not the probability the next throw is heads with that coin.
It's just the probability that coin is the biased coin.
Ex: Coin to choose: 0 Prob. of Heads = 0.5901
Probability next throw is heads with coin 0 = 0.5901*bias + (1-0.5901)*0.5 = 0.559 (bias=0.6)
Weight-factor is the probability given a specific amount of flips a particular sequence H/T occurs while following the optimal strategy.
Last edited by cyberfish; 02-08-2012 at 05:50 PM.
|
|
|
|
|
02-08-2012, 07:09 PM
|
#11
|
|
Pooh-Bah
Join Date: Jul 2005
Location: Phoenix
Posts: 4,446
|
Re: Cute Little Coin Problem I Made Up
|
|
|
|
|
02-09-2012, 01:05 AM
|
#12
|
|
old hand
Join Date: Jun 2011
Posts: 1,303
|
Re: Cute Little Coin Problem I Made Up
Quote:
Originally Posted by SheetWise
|
Don't try to ruin the fun for us math dorks!
|
|
|
|
|
02-09-2012, 03:16 AM
|
#13
|
|
grinder
Join Date: Jan 2006
Posts: 585
|
Re: Cute Little Coin Problem I Made Up
Just to be clear. Using 3 coins and 4 flips. - Let the biased coin be expected to turn up heads 99.9% of the time instead of 60%. After flipping the 1st coin 3 times producing the sequence HHT, which coin do you select next to flip?
- Again, let the biased coin be expected to turn up heads 99.9% of the time instead of 60%. After flipping the 1st coin 4 times producing the sequence HHHT, which coin do you select as most likely to be biased?
What algorithm are you using to decide this?
|
|
|
|
|
02-09-2012, 06:06 AM
|
#14
|
|
journeyman
Join Date: Sep 2004
Posts: 298
|
Re: Cute Little Coin Problem I Made Up
Quote:
Originally Posted by R Gibert
Just to be clear. Using 3 coins and 4 flips. - Let the biased coin be expected to turn up heads 99.9% of the time instead of 60%. After flipping the 1st coin 3 times producing the sequence HHT, which coin do you select next to flip?
- Again, let the biased coin be expected to turn up heads 99.9% of the time instead of 60%. After flipping the 1st coin 4 times producing the sequence HHHT, which coin do you select as most likely to be biased?
What algorithm are you using to decide this? |
In both scenarios it picks the second coin. Could be obv. the third coin too but I let it choose the first coin in the pile with ex aequo's.
Fwiw I think there are more challenging scenarios.
I dunno how those algo's are called (I'm not a seasoned programmer).
Overall some brute-force calculations, nothing fancy. I'm sure I can make it faster. But before increasing performance I want to be sure my attempt to solve this problem was ok enough.
If interested I can post the Java source code too later on.
|
|
|
|
|
02-09-2012, 10:30 AM
|
#15
|
|
journeyman
Join Date: Feb 2010
Location: Flippin' the coin
Posts: 305
|
Re: Cute Little Coin Problem I Made Up
All I can contribute is, that cyberfishs algorith is superior to the "take 2 coins randomly and flip 'em both twice" strategy, with leads to a 39.537% chance of guessing right.
|
|
|
|
| Thread Tools |
|
|
| Display Modes |
 Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
All times are GMT -4. The time now is 01:22 PM.
|
Two Plus Two
