Sciencemadness Discussion Board - Probability: Take a Coin

Probability: Take a Coin

Eddygp - 23-1-2015 at 13:06

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?

The Volatile Chemist - 23-1-2015 at 13:31

Is there a reward to solving this?

Otherwise, I have one thing to say: Statistics is the Voodoo of mathematics.

careysub - 23-1-2015 at 14:31

Quote: Originally posted by Eddygp

There is this game where a player gets a coin from a small barrel....

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 - 23-1-2015 at 16:10

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 - 23-1-2015 at 16:18

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

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.

Etaoin Shrdlu - 23-1-2015 at 18:07

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 - 24-1-2015 at 07:31

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.

mayko - 24-1-2015 at 08:33

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... :cool:

AJKOER - 24-1-2015 at 13:05

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 - 24-1-2015 at 14:31

Quote: Originally posted by Eddygp

Knowing that the expected value is -0.5€ (per turn), how many fake coins are there in the barrel?

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.

Marvin - 24-1-2015 at 15:07

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 - 24-1-2015 at 15:43

Quote: Originally posted by AJKOER

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 - 24-1-2015 at 16:12

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 - 25-1-2015 at 04:10

The game stops when there are only fake coins left, for obvious reasons.

Sedit - 25-1-2015 at 08:18

There all fake and the organizer is a con man

careysub - 25-1-2015 at 08:20

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 - 25-1-2015 at 10:20

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 509 times

Attachment: Program.cs (2kB)
This file has been downloaded 610 times

[Edited on 1-25-2015 by gdflp]

gdflp - 25-1-2015 at 14:25

Ohhh shit, I just found a logical error in my program. Arghhh, it's looped through billions of times. :mad:

Here's the corrected one :

Attachment: Program.cs (2kB)
This file has been downloaded 696 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 - 26-1-2015 at 05:29

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]

Here is something with much wider implication

franklyn - 26-1-2015 at 18:58

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 - 30-1-2015 at 04:56

So Eddygp, is gdflp correct? edit - Or should we help revise his source code?

[Edited on 30-1-2015 by smaerd]

Eddygp - 30-1-2015 at 12:50

To be honest... I do not have the answer...

gdflp - 30-1-2015 at 13:06

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 - 30-1-2015 at 14:38

Quote: Originally posted by Eddygp

Knowing that the expected value is -0.5€ (per turn), how many fake coins are there in the barrel?

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 - 1-2-2015 at 03:06

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]

gdflp - 1-2-2015 at 05:41

That would be correct if no coins were ever eliminated from the game. However, since coins are being eliminated from the game, a large number of turns have different probabilities. That's why I tried a programmatic approach, some games neared 150,000 turns.

aga - 1-2-2015 at 06:08

If the average probability dictates that the take per turn is -0.5, then the number of iterations becomes irrelevant no ?

Edit:

The neatness of the answer also suggests that it's an exam question.

[Edited on 1-2-2015 by aga]

Eddygp - 1-2-2015 at 12:51

Quote: Originally posted by aga

If the average probability dictates that the take per turn is -0.5, then the number of iterations becomes irrelevant no ?

Edit:

The neatness of the answer also suggests that it's an exam question.

[Edited on 1-2-2015 by aga]

Bear in mind that coins are destroyed, leading to a decrease in the total number of coins and either the loss of two genuine ones or a genuine one and a counterfeit one.
It is not an exam question, as far as I know. Due to the abovementioned added difficulty of discarding a genuine coin and another random coin (picked from the barrel), it would be quite complicated unless a more straightforward approach was used. Bayes can get pretty complicated here.

smaerd - 1-2-2015 at 13:04

Something tells me gdflp is on the mark. The source-code looks reasonable, I might of approached it slightly differently.

Quote: Originally posted by Eddygp

To be honest... I do not have the answer...

As much as I would love to read up on bayesian statistics and attempt a notation based solution I just don't have time to spend 3-4 days putting pencil on paper. I know there's a less laborious way to approach it though.

aga - 1-2-2015 at 14:20

Quote:

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?

The answer is in the question.

Average/expected value per turn is -0.5 euros.

A Win is 6 euros, a Lose is -1 euro.

Therefore the average probability is 0.5/8 which equals 1500 Real coins.

The Game mechanics are irrelevant, and put there simply to confuse.

Edit :

Despite knowing little about maths, i think i grasp the concept.

If 'w' is the number of winning coins then :

On the First iteration of the program, the probability of picking a Winning coin (p) is w/24000

At this point the value of p changes, as the probability of discarding another winning coin
is p * ( (w-1)/23999 )

Then the probability changes again before the next 'turn', to account for the fact that two coins have now been removed from the game.

Programatically this is do-able, however the overall Probability is pre-determined in the Question.

This signifies that the question itself contains the parameters required for the calculation.

Likely it is a Stats/Probability question from some past paper.

[Edited on 1-2-2015 by aga]

Marvin - 1-2-2015 at 14:36

I don't understand aga's analysis at all. Maybe write drunk and edit sober does not apply to math ;D Though going through it made me spot a mistake in my own initial analysis, which makes me think that if fake coins were not returned to the pot the concentration would be stable turn to turn, at 1:13 real to fake. ie 1 in 14 coins real. As it is the concentration of real coins must drop as the game is played.

I've written and run a short program based on my sum of games idea but the result does not match gdflp results and it's far enough away (9500ish) to make me think there must be a mistake. Aside from trusting the random number gen, I can't see any potential problems with his code. I suspect the problem lies in rnd.next or me. Weighted with me. I never took stats. Should I have said this before

I tried to approach this with calculus, which I think is a viable method, this is a lot like a radioactive decay where the rate of reduction is related to the amount of material. Turns out my calculus is a bit rusty and I'm having difficulty arranging the math so I don't have multiple dependent variables.

I like this problem, but I'm not feeling the love back yet.

aga - 1-2-2015 at 14:57

Failure to read and understand the Question is a common reason for students failing in exams.

I've done that a few times.
Read, misunderstood, then answered a question i made up myself on the spot, and preferred.

aga - 1-2-2015 at 15:33

My reasoning is this :

The Stated 'expected value is -0.5€ (per turn)' is the Clue.

There are 24000 coins in the pot.

The Max payout is 6 euros.
The Min is -1 euro.

That makes a Range of 8 euros (don't forget to count 0 euros)
Thenotion that you get either -1 or +6 is irrelevant.

Therefore the Average Probability of picking a winning Coin is 0.5/8, no matter what the game actually is,
or whether coins are discarded or not.

The Question already states that the outcome is -0.5 euros per turn : the Overall Result is already known.

I do feel aqbit drunk now, so i'll stop posting for today.

gdflp - 21-1-2017 at 14:02

I came across this thread again recently, so I thought I would revisit this and see if I could narrow down the answer anymore. First of all, I adapted the script to Matlab, hoping that it would run more efficiently. Unfortunately, it seems that it's a bit slower than the C# code if anything, but I ran it anyway. I didn't bother to set up multi-threading as I've only got a quad core right now(though substantially faster than the processor I was running 2 years ago), so it's simpler to just manually run a couple of instances simultaneously. I ran another 1,000,000 game simulation and got the following rather promising results :

8765 - -0.5001441
8766 - -0.4999944
8767 - -0.4998910
8768 - -0.4998794

This seems to again point to 8766, so I decided to run a 10,000,000 game simulation with 8766 and the two adjacent numbers, resulting in the following:

8765 - -0.5001112
8766 - -0.5000162
8767 - -0.4999233

Unfortunately, a bit worse than the million game simulation, but it still seems to point to 8766.

If anyone who is better at statistics than I would like to take a more orthodox approach to this problem and confirm my result, I would be more than happy. As it stands though, I'm fairly confident that 8766 is the correct answer, unless there's another logical error in my code which I'm not seeing.

JJay - 21-1-2017 at 18:15

This can be formulated as a maximum likelihoood optimization if you can specify the potential earnings as a probability distribution which is a function of the number of coins.

It's trivial to come up with a recursive formula for the distribution that simply covers all possible outcomes, but it would require infinite time to evaluate. Reducing that formula to closed form... hmm....

[Edited on 22-1-2017 by JJay]

Marvin - 23-1-2017 at 17:05

I've been meaning to return to this for a long time.

I've tried a completely new approach and I was much happier with it than any of my previous efforts until I actually got results. Rather than play the game turn by turn and get non integer numbers of genuine coins in my sum of games probability idea, I hit on computing the value of moving between states in the game. So the average number of turns needed to remove a genuine coin at every state in the game and keep track of the value, summing every transition as it is produced. I even started working it as a grid of states so I wasn't averaging state values as well as probability in case that made the answer wrong.

My closest values are,
8838 = -0.500052
8839 = -0.499957

I don't know why they bear no relation to the Monte Carlo values. Getting the last coin is responsible for almost 10 percent of the total money made by the game, so screwing up there, say by an off by 1 error results in a different answer by hundreds of coins referred to the start of the game.

I think what I need to do is try my method with something simpler and with vastly fewer turns to see if it can produce right answers and then make things more complex until it breaks.

Maroboduus - 23-1-2017 at 18:12

Quote: Originally posted by aga

My reasoning is this :

The Stated 'expected value is -0.5€ (per turn)' is the Clue.

There are 24000 coins in the pot.

The Max payout is 6 euros.
The Min is -1 euro.

That makes a Range of 8 euros (don't forget to count 0 euros)
Thenotion that you get either -1 or +6 is irrelevant.

Therefore the Average Probability of picking a winning Coin is 0.5/8, no matter what the game actually is,
or whether coins are discarded or not.

The Question already states that the outcome is -0.5 euros per turn : the Overall Result is already known.

I do feel aqbit drunk now, so i'll stop posting for today.

My first reaction was to calculate the average probability of picking a winning coin as well. I think that's a natural first thing to try if you're trying to dissect the problem to figure out how its author was thinking.
(Oh my god, I have something in common with aga? The mind boggles, but it does that a lot lately.)

However I get a probability of 3/14 of picking a winning coin.

([3x6]-11)/14=0.5

This also seems to mean the average game would take 5600 tries to complete. (discard 2 coins 3 times for every 14 tries.....so 2400 coins every 5600 tries). (six to fourteen is as 2400 to 5600)

But this hasn't gotten me any farther as of yet.

I am somewhat limited when it comes to solving problems like this in my head, so I am attempting this as a mental exercise.

This is a COOL question for a mathematical novice to bend his brain over, but I do have a nagging feeling that some hotshot mathematician probably examined this class of problems and found a general solution for them decades or centuries ago.

Will think this over a bit more next time I'm in the proper mood.

EDIT: OOPS, that's what I get for not re-checking the question. Those results are for an expected payout of 0.5, not -0.5.

[Edited on 24-1-2017 by Maroboduus]

So then it's 1/14 odds of a winning pull.
(6-13)/14= -0.5
And 16,800 tries for an average game.

Like I said, I'm somewhat limited when it comes to solving problems like this in my head.

[Edited on 24-1-2017 by Maroboduus]

EDIT: Make that 168,000 tries. Damn! (24000 coins, NOT 2400)

[Edited on 24-1-2017 by Maroboduus]

So the odds for EACH given try will be expected to reduce at a some rate from some given value to a dead certainty, and the remaining pulls will all be sure winners.
The average of the odds on all these tries will be 1/14.

Seems like some clever little algebraic equation should solve this for the number of genuine coins, and the number of fakes is trivial from there.

Problem is the rate of change itself will also change as the odds increase.
EDIT:
From an initial rate of the initials odds of success per pull plus one times the initial odds per pull up to 2 per pull when you reach certainty of successful pulls and continuing at that rate till the coins are gone?

Equaling an overall rate of (1+[1/14])/14=15/196 for all pulls?

[Edited on 24-1-2017 by Maroboduus]

[Edited on 24-1-2017 by Maroboduus]

zed - 10-2-2017 at 13:01

Hmmmm.

I'm an aspiring con man myself, but I seem to lack the required potential for un-bridled evil.

Sounds like there is the potential here, to steal lotsa money. But, exactly how?

Universal default, scratch-offs, and mortgaged back securities....have already been done.