Pages:
1
2 |
Eddygp
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 858
Registered: 31-3-2012
Location: University of York, UK
Member Is Offline
Mood: Organometallic
|
|
Probability: Take a Coin
There is this game where a player gets a coin from a small barrel. The player then looks at the coin and depending on whether it is fake or not, he'll
have to pay some money or receive some money. The player can tell whether the coin is a fake one or not with a maximum accuracy. There is no room for
doubt. The game is planned to proceed as follows:
If the coin was fake: The player pays 1€ to the organiser and returns the coin to the barrel.
If the coin was NOT fake: The player receives 6€ and discards the coin. The player grabs another coin and discards it (without paying or receiving
money, regardless of whether the coin was fake or not).
There are 24000 coins in the barrel.
Knowing that the expected value is -0.5€ (per turn), how many fake coins are there in the barrel?
there may be bugs in gfind
[ˌɛdidʒiˈpiː] IPA pronunciation for my Username
|
|
The Volatile Chemist
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1981
Registered: 22-3-2014
Location: 'Stil' in the lab...
Member Is Offline
Mood: Copious
|
|
Is there a reward to solving this? Otherwise, I have one thing to say:
Statistics is the Voodoo of mathematics.
|
|
careysub
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1339
Registered: 4-8-2014
Location: Coastal Sage Scrub Biome
Member Is Offline
Mood: Lowest quantum state
|
|
Are you going to present us with an analysis and solution after some set period of time?
NB: I must defend the honor of probability theory (this problem is not really one of statistics) - it is just as much "mathematics" as any other part
of mathematics. Fundamentally it is just set theory in another guise.
[Edited on 23-1-2015 by careysub]
[Edited on 23-1-2015 by careysub]
|
|
Loptr
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1348
Registered: 20-5-2014
Location: USA
Member Is Offline
Mood: Grateful
|
|
I am going to shut my mouth now because at first it sounded like a "mark and recapture" problem, then I read it again.
|
|
mayko
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1218
Registered: 17-1-2013
Location: Carrboro, NC
Member Is Offline
Mood: anomalous (Euclid class)
|
|
Not to nitpick... well... actually that's what mathematicians do best
I think there might be too few/too many factors at play in the problem as stated.
Quote: Originally posted by Eddygp ![](images/xpblue/lastpost.gif) | There is this game where a player gets a coin from a small barrel. The player then looks at the coin and depending on whether it is fake or not, he'll
have to pay some money or receive some money. The player can tell whether the coin is a fake one or not with a maximum accuracy. There is no room for
doubt. |
So, we have an random variable B, corresponding to the coin we pull from the Barrel. B has an event space {Genuine, Counterfeit} and an unknown
probability function Pb; all we can really say is that Pb(G) = 1-Pb(C) and vice versa: they are mutually exclusive.
We also have a random variable D, corresponding to the Decision about the legitimacy of the coin. D has event space {True, False} with an unknown
probability function Pd, though again we know Pd(F) = 1-Pd(T) and vice versa.
As phrased, we also know that Pd and Pg are independent: the false rejection rate of Genuine coins is the same as the false acceptance rate of
Counterfeit coins.
Quote: | The game is planned to proceed as follows:
If the coin was fake: The player pays 1€ to the organiser and returns the coin to the barrel.
If the coin was NOT fake: The player receives 6€ and discards the coin. The player grabs another coin and discards it (without paying or receiving
money, regardless of whether the coin was fake or not).
|
This description of the game, however, makes no actual use of the player's detection skill; she is given a reward or a penalty based solely on B!
Quote: |
There are 24000 coins in the barrel.
Knowing that the expected value is -0.5€ (per turn),
|
I'm not sure how you're going to manage this in an iterated game. Exactly one of G and C occur. If G, the number of coins in the barrel, N remains
constant. If C, N increments downward by two. Thus, as a function of time measured in number of turns played, N(t), is a decreasing function. (It is
not guaranteed to be strictly decreasing unless Pb(G)==1, that is to say, all coins are Genuine. Interpreting N(t) is the job of statistics )
Thus, if she plays for a long enough period of time, she will eventually hit one of two 'end states' (again, assuming neither Pb(G) nor Pb(C) are
equal to 1):
a) she discards the last counterfeit coin. At this point, Pb(G) == 1 and EV = +$6
b) she discards the last genuine coin. At this point, Pb(C) == 1 and EV = -$1
In neither case will EV == -$0.5 on her next turn.
Quote: | how many fake coins are there in the barrel? |
If EV = -$0.5 on every turn, it holds on the first turn t=0 in particular. Given that N(0) = 24000, the payoffs assigned to G and C (+$6 and -$1
respectively), and the fact that T and F are mutually exclusive, I arrive at a non-integer ~22,286, in the barrel at t=0.
al-khemie is not a terrorist organization
"Chemicals, chemicals... I need chemicals!" - George Hayduke
"Wubbalubba dub-dub!" - Rick Sanchez
|
|
Etaoin Shrdlu
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 724
Registered: 25-12-2013
Location: Wisconsin
Member Is Offline
Mood: Insufferable
|
|
Mayko, the player can tell whether the coin is counterfeit with no room for doubt, so Pg is not independent of Pb, it's exactly the same.
Detection/decision skill is perfect.
EV=-$0.5 per turn over the course of the game, as I understand it. Since counterfeit coins are returned and true coins are removed, EV of turn 1
should be significantly higher than EV of later turns.
[Edited on 1-24-2015 by Etaoin Shrdlu]
|
|
Eddygp
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 858
Registered: 31-3-2012
Location: University of York, UK
Member Is Offline
Mood: Organometallic
|
|
EV=-0.5€ over the course of the game, of course. Bear in mind that if you pick a counterfeit coin, you return to the same situation (no coins are
removed and, therefore, there are still the same probabilities to draw a genuine or a fake one). However, if you get a genuine one, you destroy that
one and another random one (bear in mind that, when picking this random one to be destroyed, there is one coin LESS in the barrel).
Therefore, you will destroy either two genuines or a genuine and a counterfeit one.
there may be bugs in gfind
[ˌɛdidʒiˈpiː] IPA pronunciation for my Username
|
|
mayko
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1218
Registered: 17-1-2013
Location: Carrboro, NC
Member Is Offline
Mood: anomalous (Euclid class)
|
|
Gotcha. I got thrown by all this talk of counterfeits: if the false positive/negative rate is zero, then they aren't very good fakes, and I'd have
phrased it in terms of red and green balls or something similar.
Back to the scratch pad...
al-khemie is not a terrorist organization
"Chemicals, chemicals... I need chemicals!" - George Hayduke
"Wubbalubba dub-dub!" - Rick Sanchez
|
|
AJKOER
Radically Dubious
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 3026
Registered: 7-5-2011
Member Is Offline
Mood: No Mood
|
|
I would choose to solve this problem numerically via a spreadsheet.
Steps:
1. Assign a probability to the fake coins.
2. To simplify, work with rows (likely over a thousand) with formulae to replicate possible turns if say 500 coin are in the barrel. Unused rows on a
particular simulation run return blank to assist in tabulation of an observed complete game event.
3. Repeat the simulation with the same probability at least 30 times, storing the $ return for each run and computing the average $ return.
4. Assume a much higher p for the fake coins and run at least 30 simulations of a game event.
5. Interpolate return results with the given observed return. Select a high and low value again around this improved estimate and repeat simulation
run for 30 plus complete games.
6. Repeat Step (5) until an acceptable error rate is achieved on the portion of fake coins.
Workable, but a bit of work.
|
|
Nicodem
Super Moderator
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 4230
Registered: 28-12-2004
Member Is Offline
Mood: No Mood
|
|
Isn't the solution a probability function itself (a series of probabilities for each certain number of fake coins giving that expected value of -0.5
€)? I can't see how such a game could be mathematically modelled to give an absolute number as a solution.
If the solution is a probability function, then the problem is can be relatively easily solved by running and averaging a large number of Monte-Carlo
simulations. A brute force approach and not as elegant as a purely mathematical solution, but at least there would be no doubt in the correctness of
the solution, just doubts about its exactness.
…there is a human touch of the cultist “believer” in every theorist that he must struggle against as being
unworthy of the scientist. Some of the greatest men of science have publicly repudiated a theory which earlier they hotly defended. In this lies their
scientific temper, not in the scientific defense of the theory. - Weston La Barre (Ghost Dance, 1972)
Read the The ScienceMadness Guidelines!
|
|
Marvin
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 995
Registered: 13-10-2002
Member Is Offline
Mood: No Mood
|
|
He means the "value of the game" assuming you don't know how many times it's been played before.
Is it fair to say that there is a missing rule that states if the number of genuine coins reaches zero the game must be stopped even if there are fake
coins left? Otherwise I don't see how the conditions can be met.
|
|
Etaoin Shrdlu
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 724
Registered: 25-12-2013
Location: Wisconsin
Member Is Offline
Mood: Insufferable
|
|
Quote: Originally posted by AJKOER ![](images/xpblue/lastpost.gif) | I would choose to solve this problem numerically via a spreadsheet.
Steps:
1. Assign a probability to the fake coins.
2. To simplify, work with rows (likely over a thousand) |
Oh boy. Way over a thousand. You need enough rows to be confident of winding up with no good coins in the barrel. Then you need those rows
duplicated enough times to be confident of the average of your "trials." Even small probability problems can go to a crawl with spreadsheets. I'd do
something with scripting.
EDIT: I'm just assuming the stop point is when there are no good coins left. There has to be some definite end since your ratio of false coins
increases towards 100% and the limit at infinite turns gives you an EV of -$1 per turn.
[Edited on 1-24-2015 by Etaoin Shrdlu]
|
|
smaerd
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1262
Registered: 23-1-2010
Member Is Offline
Mood: hmm...
|
|
Nicodem that's sort of what I was thinking too. The hardest part of the problem is in setting it up. I started chipping away at it but had to stop
because it would probably take me a few days to reach a solution(if it was even right). My approach was to start with assigning a variable for the
number of turns and integrating that from 0 to infinity. If I could find the expectation value for the number of turns taken to "complete" the game I
think that'd be a good place to start. Ultimately though, I think there is an issue with the information given, in that the question asks for an exact
number of fake coins in the barrel and only an expectation value was given.
The problem is essentially that there are two variables that are related to each other, and the few ways I tried to set up the problem one or the
other ended up as the "bound" for the other. I was doing something similar to the derivation of the diffusion equation. I'm sure it's a matter of
bayesian statistics. The effect of a true coin being found effects the probability of the next 'turn', so the probability is conditional. It's inverse
probability .
I wonder if there's a short-cut using information theory or something. Aside from all of that meanderings, I am with many of the other poster's here,
I'm more inclined to approach a solution via programming. This thing would go so easily with some for/next loops verses mathematical notation. I'm
just too lazy and already have to apply some higher math for an experiment next week(system of ODE's I solved).
Edit - Marvin, that was why I was thinking about PDE's because that is a sort of boundary condition. That would also define an expectation value
integral, and could create an error in the game, I believe the ratio of the fake to real coins likely mitigates the logical error of discarding coins
that do not exist as well.
[Edited on 25-1-2015 by smaerd]
|
|
Eddygp
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 858
Registered: 31-3-2012
Location: University of York, UK
Member Is Offline
Mood: Organometallic
|
|
The game stops when there are only fake coins left, for obvious reasons.
there may be bugs in gfind
[ˌɛdidʒiˈpiː] IPA pronunciation for my Username
|
|
Sedit
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1939
Registered: 23-11-2008
Member Is Offline
Mood: Manic Expressive
|
|
There all fake and the organizer is a con man
Knowledge is useless to useless people...
"I see a lot of patterns in our behavior as a nation that parallel a lot of other historical processes. The fall of Rome, the fall of Germany — the
fall of the ruling country, the people who think they can do whatever they want without anybody else's consent. I've seen this story
before."~Maynard James Keenan
|
|
careysub
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1339
Registered: 4-8-2014
Location: Coastal Sage Scrub Biome
Member Is Offline
Mood: Lowest quantum state
|
|
If you want to tackle this problem programmatically* to get an approximate answer the way to do it is not to "solve" the n=24,000 coin case but to
work up from a minimal version of the problem where the number of states is small and look at what happens as n increases.
There is nothing special about n=24,000. If he had said n=24 trillion you would realize right off that you couldn't actually simulate the full game,
but could only compute a smaller version, but the ratio of fake to real should be the same.
Developing a formula that expresses the relationship between the fake/real ratio and the expected value can be done using recurrences.
*There are an infinite number of arbitrary problems that can be posed. The OP has given me insufficient reason to want to tackle this particular one.
It is easy to pose difficult arbitrary problems, but difficult arbitrary problems aren't inherently interesting. I have done graduate work in
probabilistic reasoning and this one looks very tedious to solve exactly. Does he already have an answer that we can verify?
|
|
gdflp
Super Moderator
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1320
Registered: 14-2-2014
Location: NY, USA
Member Is Offline
Mood: Staring at code
|
|
Okay, I'm close to solving the problem, I'm just running the program now. Attached is the program I wrote to find a rough solution, and the program I
wrote to tune in on the solution(they're both in C#). Right now, I believe it's in the range of 8765-8780 real coins.
Attachment: Rough Version.cs (2kB) This file has been downloaded 536 times
Attachment: Program.cs (2kB) This file has been downloaded 636 times
[Edited on 1-25-2015 by gdflp]
|
|
gdflp
Super Moderator
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1320
Registered: 14-2-2014
Location: NY, USA
Member Is Offline
Mood: Staring at code
|
|
Ohhh shit, I just found a logical error in my program. Arghhh, it's looped through billions of times. Here's the corrected one :
Attachment: Program.cs (2kB) This file has been downloaded 721 times
Edit : After running the program through 100,000 simulated games through a series of numbers, I believe that the solution is 8,765 real coins and
15,235 fake coins.
[Edited on 1-26-2015 by gdflp]
|
|
Marvin
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 995
Registered: 13-10-2002
Member Is Offline
Mood: No Mood
|
|
Do you need to simulate multiple games? If you are going to solve it computationally then instead of introducing a random element just compute the
probable result in total. ie effectively all games at once.
Edit. A mathematical solution to the last coin should speed up a game simulation and applying that to the sum of all games should provide an end
point when the simulation crosses 1.0 coins left.
[Edited on 26-1-2015 by Marvin]
|
|
franklyn
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 3026
Registered: 30-5-2006
Location: Da Big Apple
Member Is Offline
Mood: No Mood
|
|
Here is something with much wider implication
http://www.youtube.com/watch?v=kLmzxmRcUTo&feature=youtu...
Explanation
http://www.youtube.com/watch?v=OcYnlSenF04&feature=youtu...
Deeper reading
http://bact.mathcircles.org/files/files/Summer2010/PenneyAnt...
For long sequences , it also works
http://www.haverford.edu/math/cgreene/390b-00/software/CoinF...
Press NEXT, then GENERATE A , and GENERATE B , press NEXT and then later press NEXT TRIAL.
Press RESTART anytime to enter new strings for A and B
More fun and games
http://sourceforge.net/p/penneyante/wiki/Home
.
|
|
smaerd
International Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1262
Registered: 23-1-2010
Member Is Offline
Mood: hmm...
|
|
So Eddygp, is gdflp correct? edit - Or should we help revise his source code?
[Edited on 30-1-2015 by smaerd]
|
|
Eddygp
National Hazard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 858
Registered: 31-3-2012
Location: University of York, UK
Member Is Offline
Mood: Organometallic
|
|
To be honest... I do not have the answer...
there may be bugs in gfind
[ˌɛdidʒiˈpiː] IPA pronunciation for my Username
|
|
gdflp
Super Moderator
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 1320
Registered: 14-2-2014
Location: NY, USA
Member Is Offline
Mood: Staring at code
|
|
Any revisions offered would be greatly appreciated. After running the program multiple times consecutively, I am less sure that 8765 is correct
number. After running multiple times with the iterations set to 100,000 games, the range of 8760-8772 gives a value of -0.500 when rounded. I think
it's reasonably safe to say that the answer is within this region, but I have no idea how to narrow it down further. A test I did with 1,000,000
iterations for 4 numbers gave the following results :
8765 : -0.50012848
8766 : -0.49998012
8767 : -0.49997471
8768 : -0.49978269
It took 12 hours though for my computer to process and calculate these four numbers.
[Edited on 1-30-2015 by gdflp]
|
|
aga
Forum Drunkard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 7030
Registered: 25-3-2014
Member Is Offline
|
|
Expected value to whom ?
The Player or the Operator ?
i.e. is the average value to the Player -0.5 per turn, or the value to the Operator -0.5 per turn ?
|
|
aga
Forum Drunkard
![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif) ![*](images/xpblue/star.gif)
Posts: 7030
Registered: 25-3-2014
Member Is Offline
|
|
Had me puzzling quite a lot has this one.
I think the answer is 1500 Real coins and 22,500 Fake ones.
Let p=probability of a win, w=number of Real coins
The range of cash outcomes is +6 to -1, so 8 in total.
therefore p = w/24000 also p = 0.5/8
so w = ( 24000 * 0.5 ) / 8 = 1500
The actual mechanics of the game can be ignored, as the nett probability of a -0.5 outcome per 'turn' is already known.
[Edited on 1-2-2015 by aga]
|
|
Pages:
1
2 |