Poll

No votes (0%)
1 vote (7.69%)
No votes (0%)
3 votes (23.07%)
No votes (0%)
1 vote (7.69%)
1 vote (7.69%)
1 vote (7.69%)
6 votes (46.15%)

13 members have voted

chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 7th, 2014 at 8:48:44 AM permalink
You see N briefcases each with a different amount of money written on the inside. You know the amounts inside are random from $0 to $1,000,000. (uniformly distributed). You can select and look inside each brief case one at a time and decide to keep it or discard it. You win if you decide to keep the briefcase with the highest amount inside. If you choose to keep a case other than the largest you win nothing.

Assuming you play optimal strategy, what is the minimum probability of winning?

edit:

note 1: the cases have an amount in them sampled from a continuous uniform distribution

note 2: you know what N is when you are playing the game.
FinsRule
FinsRule
  • Threads: 128
  • Posts: 3914
Joined: Dec 23, 2009
May 7th, 2014 at 9:14:51 AM permalink
I have to keep saying "No solution exists" because it depends on the number of briefcases.
vetsen
vetsen
  • Threads: 3
  • Posts: 46
Joined: Jun 4, 2013
May 7th, 2014 at 9:50:37 AM permalink
Isn't optimal strategy to just open cases until you open the one with $1,000,000? What am I missing?
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26432
Joined: Oct 14, 2009
May 7th, 2014 at 9:54:06 AM permalink
I'm assuming that there are no suitcases with 0 or $1M. For example, if there were 9 suitcases they would have values of $100,000, $200,000 ... $900,000.

My strategy would be to open a small number of them and try to determine the increment between suitcases. The maximum would be $1M - (the increment). This doesn't guarantee success, but should have a very good chance for large values of N.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
MathExtremist
MathExtremist
  • Threads: 88
  • Posts: 6526
Joined: Aug 31, 2010
May 7th, 2014 at 9:57:30 AM permalink
Even if there are no suitcases with 0 or $1M, you can still guarantee a win with the knowledge of a uniform distribution. You don't need to open any cases to determine the increment, it's just $1M / (N+1). The largest case contains $1M - $1M/(N+1), so just keep picking until you find that.

Edit: I assume you actually know what N is. That is, you can count the number of cases before you start picking.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26432
Joined: Oct 14, 2009
May 7th, 2014 at 10:00:27 AM permalink
Quote: MathExtremist

Edit: I assume you actually know what N is. That is, you can count the number of cases before you start picking.



I assumed you don't know N.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
MathExtremist
MathExtremist
  • Threads: 88
  • Posts: 6526
Joined: Aug 31, 2010
May 7th, 2014 at 10:19:32 AM permalink
Quote: Wizard

I assumed you don't know N.


But you can see the N cases...
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
FinsRule
FinsRule
  • Threads: 128
  • Posts: 3914
Joined: Dec 23, 2009
May 7th, 2014 at 10:22:34 AM permalink
Quote: FinsRule

I have to keep saying "No solution exists" because it depends on the number of briefcases.



Perhaps I worded it wrong.

No solution exists because not enough information exists in the problem. There's more than just the number of briefcases needed.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 7th, 2014 at 10:27:13 AM permalink
sorry for the confusion, the amount is randomly sampled from a continuous uniform distribution and you do know what N is.
chevy
chevy
  • Threads: 3
  • Posts: 146
Joined: Apr 15, 2011
May 7th, 2014 at 10:28:03 AM permalink
edit: OP just posted same clarification
AceTwo
AceTwo
  • Threads: 5
  • Posts: 359
Joined: Mar 13, 2012
May 7th, 2014 at 1:53:30 PM permalink
Very nice problems you have posted chrisr. I like it when seemingly complex problems have a short elegant solution like 1/e.
I bet the same applies for this one.

Do not know the solution and never seen this problem before.
Obviously teh answer is higher than 1/e.
First thoughts is that the probability should be very high approaching 100%.
But on second thoughts, the probability is much lower.
I am sure it is above 1/2 .

The strategy would be in the beginning to Stop only at a very high value approaching $1 million (I will use % for simplicity)
So at the beginning say round 1, you stop if it exceeds 99%.
Round 2 if it exceeds 98% and so on.
On the previous from last round you stop if it exceeds 50%.
The exact % depend on N and the round you are.
And there is a non-linear distribution of dropping from 99% to 50% depending on the round

I am sure, it is above 1/2 and I believe that it is below 3/4.
So a nice answer could be 2/e (just a wild guess on my side)
endermike
endermike
  • Threads: 7
  • Posts: 584
Joined: Dec 10, 2013
May 7th, 2014 at 3:21:46 PM permalink
Clearly you should never accept a case which has a value lower than any you have seen (since doing so would be a certain loss). So our strategy must to maximize the chance that the highest "max so far" (local optimum) which we choose to go with is the actual "max overall" (global optimum). However what I just proposed is simply maximizing the chance we win. Maximizing the EV of the game is different. Hmm, more thought is required.

OP, should we try to maximize our chances of winning or the EV of the game?
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 7th, 2014 at 4:34:33 PM permalink
Quote: endermike

OP, should we try to maximize our chances of winning or the EV of the game?



chance of winning.

I didn't specify what the prize was for winning. But it's fabulous.


edit:

In case anyone is confused. The probability of winning is a function of N and there is a lower bound to that function. The problem is asking for that lower bound.
AceTwo
AceTwo
  • Threads: 5
  • Posts: 359
Joined: Mar 13, 2012
May 8th, 2014 at 12:39:35 PM permalink
The solution is above 1/2 but I do not think by much. The answer is 0.53.
Defitions:
N = Number of Suitcases
m = current suitcase
Xm= Value of m suitcase
Xm(s) = Minimum Value to Stop on the m suitcase
I am using 0-1 scales (instead of $0 to $1million) so values can also be seen as % from 0% to 100%.

I believe the formula that optimises Probability of win as follows:
Xm(s) is the Minimum value where the following inequality holds 1 - Xm < Xm^(N-m)
(always provided that all previous values are lower otherwise you continue)

For example
N=10
m=4
If Xm = 0.77 then 1-Xm = 0.23 AND Xm^(N-M) = 0.77^(10-4) = 0.208 So the Inequality does not Hold
If Xm = 0.78 then 1-Xm = 0.22 AND Xm^(N-M) = 0.78^(10-4) = 0.225 So the Inequality Holds
So the minimum value that the inequality holds is slighly below 0.78 for the 4th Suitcase when there are 10 suitcases.
You stop if the 4th suitcase is at least 0.78 (and of course provided that none of the first 3 are above that)

And then you have to Find a way to find the frequencies of stopping at each point the Total Weighted Sum of all of them.
Which is a lot more difficult.
Dween
Dween
  • Threads: 66
  • Posts: 339
Joined: Jan 24, 2010
May 9th, 2014 at 5:06:26 AM permalink
This is also known as the Interview Puzzle.

Given a group of N candidates, you need to pick the best one. You may interview them one at a time, and either hire them on the spot, or pass and interview the next. You may not go back and hire anyone passed on.

What are the chances of picking the best candidate? How many candidates should you interview before hiring?

You should interview the first 36.79% (1/e) candidates, taking note of the best one. Keep interviewing until you find a person better than the noted best. There is a 36.79% (1/e) chance that you will have chosen the best candidate.

This blog post has a full analysis of this problem, which shows how to determine the solution.
-Dween!
AceTwo
AceTwo
  • Threads: 5
  • Posts: 359
Joined: Mar 13, 2012
May 9th, 2014 at 11:03:59 AM permalink
Quote: Dween

This is also known as the Interview Puzzle.

Given a group of N candidates, you need to pick the best one. You may interview them one at a time, and either hire them on the spot, or pass and interview the next. You may not go back and hire anyone passed on.

What are the chances of picking the best candidate? How many candidates should you interview before hiring?

You should interview the first 36.79% (1/e) candidates, taking note of the best one. Keep interviewing until you find a person better than the noted best. There is a 36.79% (1/e) chance that you will have chosen the best candidate.

This blog post has a full analysis of this problem, which shows how to determine the solution.



That is a different problem, with answer 1/e. In that probablem the population was compeletely random with no low or upper limit.

In this new problem, the population is uniformly distributed (still randomly chosen) with Low Limit 0 and High Limit $1million.
There is a lot more information with this set-up than the unbounded problem and the solution far exceeds 1/e.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 9th, 2014 at 1:50:46 PM permalink
This is a pretty hard problem..

Quote:

Xm(s) is the Minimum value where the following inequality holds 1 - Xm < Xm^(N-m)



You still need to consider what happens when there is more than 1 number larger than the selection threshold later in the sequence. For example if there are two numbers you will only choose the correct one with probability 1/2
MangoJ
MangoJ
  • Threads: 10
  • Posts: 905
Joined: Mar 12, 2011
May 9th, 2014 at 2:06:24 PM permalink
Quote: chrisr

You see N briefcases each with a different amount of money written on the inside. You know the amounts inside are random from $0 to $1,000,000. (uniformly distributed). You can select and look inside each brief case one at a time and decide to keep it or discard it. You win if you decide to keep the briefcase with the highest amount inside. If you choose to keep a case other than the largest you win nothing.

Assuming you play optimal strategy, what is the minimum probability of winning?



This is the classical "secretary problem" (http://en.wikipedia.org/wiki/Secretary_problem). A well defined optimal strategy exists, it's structure is simple: You decide to open M = N/e envelopes just to just observe their value. Let the highest value observed be X. Then you open the remaining envelope each at a time, and you keep the amount whenever the value in the envelope is higher than X.
AxiomOfChoice
AxiomOfChoice
  • Threads: 32
  • Posts: 5761
Joined: Sep 12, 2012
May 9th, 2014 at 2:08:50 PM permalink
Quote: MangoJ

This is the classical "secretary problem" (http://en.wikipedia.org/wiki/Secretary_problem). A well defined optimal strategy exists, it's structure is simple: You decide to open M = N/e envelopes just to just observe their value. Let the highest value observed be X. Then you open the remaining envelope each at a time, and you keep the amount whenever the value in the envelope is higher than X.



No, this is not the secretary problem. The distribution is already known (uniform from $0 to $1,000,000). No sampling is needed.

In the secretary problem the distribution (as well as the min and max values) are unknown.

In this problem, if the first briefcase contained $1,000,000 (the max possible), would you throw it out? Of course not. It's a different problem.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 9th, 2014 at 2:35:28 PM permalink
Just to clarify for people who might not understand what is meant by "sampled from a continuous uniform distribution". Here is an example.

808224.17, 338134.27, 592705.74, 707417.77, 115461.79, 554842.67

It does not mean that the items are exactly uniformly spaced.. So you can not infer which case is the largest by simply knowing what N is or observing some pattern in the numbers. The numbers are completely random.
AceTwo
AceTwo
  • Threads: 5
  • Posts: 359
Joined: Mar 13, 2012
May 10th, 2014 at 1:18:07 PM permalink
Quote: chrisr


It does not mean that the items are exactly uniformly spaced.. So you can not infer which case is the largest by simply knowing what N is or observing some pattern in the numbers. The numbers are completely random.



Using 0-1 scale, I understand from this that if the current number is say 0,7 then the next number (and each susbsequent one) have a 30% probability of been higher than this number.
And that seeing a briefcase with exactly 1 is a trivial case, say because you are using a million digits.

Quote: chrisr

This is a pretty hard problem..

You still need to consider what happens when there is more than 1 number larger than the selection threshold later in the sequence. For example if there are two numbers you will only choose the correct one with probability 1/2



Yes , I think I am wrong.
What aboy the following answer:

You stop whenever Xm^(N-m)>0,5
ie the probability that all of the remaing briefases is below the current one is less than 50%.

And the probaility of winning is around 70%.

MangoJ
MangoJ
  • Threads: 10
  • Posts: 905
Joined: Mar 12, 2011
May 10th, 2014 at 2:35:36 PM permalink
So let's try to tackle the problem. Say the current briefcase is contains number 0 to 1, and there are N briefcases remaining.

Let p(X,N) denote the probabiltiy of a win by optimum strategy, if X is the current briefcase and the highest number observed yet, and there are N remaining briefcases. Likewise let q(X,N) denote the probabiltiy of a win by optimum strategy, if X is the highest number observed yet but not the current briefcase.

If X is the highest number observed, the probability that X is the target overall highest briefcase is X^N.
If we open the next briefcase, then with probability X the new value Y will be smaller than X, and we need to consider q(X,N-1). If Y is larger than X, we need to consider p(Y, N-1).

If we don't hold X in the current briefcase, then we definetly need to open the next briefcase, and thus
q(X,N) = X * q(X, N-1) + int_X^1 dY p(Y, N-1).
Here int_X^1 dY means the integral over Y from X to 1.

If we hold X in the current briefcase, optimum strategy would be obviously making the action that maximizes winning probability:
p(X,N) = max[X^N, q(X,N)]

Of course if there is no remaining briefcase, then p(X,0) = 1 and q(X,0) = 0.
This should give the right recursion formula for the problem, however the solutions will be difficult, let alone finding a generalized formula for all N, let alone finding the limiting value for large N. The problems solution would be q(0,N+1) which should coincide with p(0, N+1).

Maybe someone can write a program (Mathematica should work) to find all values:

q(X,0) = 0
p(X,0) = 1

q(X,1) = X*0 + (1-X) * 1 = 1-X
p(X,1) = max[X, 1-X]

if X > 1-X: (i.e. X > 1/2)
q(X,2) = X * (1-X) + int_X^1 dY Y = X*(1-X) + (1 - X^2)/2 = (1 + 3X)*(1-X)/2
p(X,2) = max[X^2, q(X,2)] = max[X^2, (1 + 3X)*(1-X)/2]

if X < 1-X: (i.e. X < 1/2)
q(X,2) = X * (1-X) + int_X^1 dY (1-Y) = X * (1-X) + (1-X) - (1 - X^2)/2 = (1+X)*(1-X)/2
p(X,2) = max[X^2, (1+X)*(1-X)/2] = (1+X)*(1-X)/2

so:
q(1 > X > 1/2, 2) = (1 + 3X)*(1-X)/2
q(1/2 > X > 0) = (1+X)*(1-X)/2

p(1 > X > 1 + sqrt(6)/5, 2) = X^2
p(1 + sqrt(6)/5, 2 > X > 1/2, 2) = (1 + 3X)*(1-X)/2
p(1/2 > X > 0, 2) = (1+X)*(1-X)/2


I hope this is correct and should give a (clumsy) way to calculate .... Note that the polynoms gets a degree of N, which makes analytical work impossible for N>=3 (as one needs to find all equality points in the max[...] calculations). But this recursive equations should be easy enough for numerical calculations, if one works with discrete bins of, say, 10^-6....
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 11th, 2014 at 5:40:13 AM permalink
Quote: chrisr

You see N briefcases (...)
Assuming you play optimal strategy, what is the minimum probability of winning?

note 2: you know what N is when you are playing the game.

The problem statement is, IMHO, incomplete. My calculations give a different answer according to the value of N, so there isn't ONE answer. For example I have 0.750 for N=2 and 0.642626 for N=3.

Do you mean to say: "Of all the (optimal play) win probabilities p(N), which one is the minimal?" ? Then, I conjecture that it is the (N=infinite), since it may be reckoned that the prob shrinks with N.
Reperiet qui quaesiverit
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 11th, 2014 at 7:59:22 AM permalink
If N goes to infinity, then whatever the current briefcase you're considering, there is always an infinity left to open afterwards. Among these, there is (almost) certainly one which has a bigger amount than yours (*). So stopping is always a bad decision.
Conclusion: you endlessly open new cases and never win.

The expected value is zero.

(*)Unless you see the million, but in a continuous setting that is an event of zero probability.

Note: this may be useless, as a finite number N increasing is maybe not giving an answer equal to the limit as N = infinity. Reason: backward induction from the last briefcase.
Reperiet qui quaesiverit
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 11th, 2014 at 8:07:42 AM permalink
Now consider a non continuous distribution: for example the amounts are in integer number of dollars.
Then, saying the values are independently drawn from a uniform distribution is inconsistent with the statement that they are all different.

You must choose, either independence and the amounts may be the same (and N can go to infinity), or the amounts are different, which requires that N is limited and the distribution is not indep. uniform but some sort of multinomial.
Reperiet qui quaesiverit
MangoJ
MangoJ
  • Threads: 10
  • Posts: 905
Joined: Mar 12, 2011
May 11th, 2014 at 8:28:10 AM permalink
If N is infinity, then still all amounts are different from a continuous distribution.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 11th, 2014 at 8:23:05 PM permalink
Quote: kubikulann

Do you mean to say: "Of all the (optimal play) win probabilities p(N), which one is the minimal?" ? Then, I conjecture that it is the (N=infinite), since it may be reckoned that the prob shrinks with N.



yes that's right. It is possible to prove that p(N) converges as N->inf
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 11th, 2014 at 8:40:44 PM permalink
Quote:

Then, saying the values are independently drawn from a uniform distribution is inconsistent with the statement that they are all different.



Quote: MangoJ

If N is infinity, then still all amounts are different from a continuous distribution.



yes, the probability of selecting a specific number from a continuous distribution is 0. So the probability of drawing the same number twice is also 0.
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 12th, 2014 at 2:09:41 PM permalink
Thinking in progress:

The game is better understood if we abandon the physical setting of briefcases and monetary amounts. Just consider a game where a number N of random (uniform [0,1]) draws are to be made sequentially. You, as a punter, have to choose one on which to bet, and you win if your choice is the maximum among the N. Sequentially, you either reject the draw (and not come back) or accept it (and of course not bet on any subsequent one).

Thinking of it, that might make a nice casino game. Adapt it to dice (craps like) or cards (poker like) or a random number generator. Find a N with the right House Edge... provided chrisr's answer is lower than 50%!

--

Strategic elements:
We have seen that in the last steps, the optimal strategy is to refuse a draw lower than some threshold an, with a1 =0 ; a2 =0.5 ; a3 =(1+sqrt6)/5 ~=0.69 ; a4 ~=0.78.
Let us conjecture that this is an increasing sequence. (I haven't proved it yet.)

Of course you also reject if you get a draw lower than the latest max.

Notation:
I use t for initial draw, x,y,z for further draw results.
  • Define wn(x) as the value (= the prob of winning the game) of refusing a draw of value x at the nth draw before the end, conditional on this x being the highest so far.
  • Define un(x) as the best value if, at the nth draw before the end, you witness a draw x, conditional on this x being the highest value observed so far. That is, u(x) is a multi-pieced function, selecting the maximum of accepting or refusing draw x.
  • Define vn as the integral of u(x). This is the prior value of the game with n draws, when applying optimal strategy.
  • Define vn(t) as the partial value of observing a next draw better than the current maximum observed t, when applying optimal strategy.
    Of course, vn is equal to vn(0).

Typically,
w1 = 0 (refusing the last one!) ;
u1 = 1 (you have the max);
v1 (t) = integt1 u1 (x) = 1-t

I find
w2(x) = (1-x) (= x w1 + v1 )
a2 = root of equation {x=w2(x)} = 0.5
u2(x) = Max[ x, w2(x) ] = two-pieced function: 1-x from 0 to 0.5, x from 0.5 to 1
v2(t) = integral of u(x) from t to 1 =
(if t < a2) integta2 w2(x) + intega21 x
(if t > a2) integt1 x

wn (x) = x wn-1 (x) + vn-1 (x)
an = root of equation {xn-1=wn (x)} Polynomial of degree n-1
un (x) = Max[ xn-1, wn (x) ] = n-pieced function along the ai 's
vn (t)= integral of u from t to 1 = from 1 to n integrals according to where t lies among the ai 's

(all integrals with x as integration variable)
These recursive formulas are those of Mango's exploration above, except I use the thresholds instead of the MAX.

I can't seem to be able to find a useable closed form for those. You work with multi-pieced high-degree polynomials.

The OP's question is to find the minimal vn , likely when n tends to infinity (BUT still is finite!!)
Reperiet qui quaesiverit
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 12th, 2014 at 2:10:10 PM permalink
Does anyone have a solution for typing an integral sign ?
Reperiet qui quaesiverit
Sonuvabish
Sonuvabish
  • Threads: 29
  • Posts: 1342
Joined: Feb 5, 2014
May 12th, 2014 at 3:32:03 PM permalink
At first glance, the answer appears to be 1/e.

But the actual answer is close to 100% or 1. But not quite.

There's a small chance you could open the largest suitcase first and discard it, before you can determine the increment. The largest suitcase could have $100.

No solution.

Anyone guessing a decimal value...I hope you were just mad there was no bigot option.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 12th, 2014 at 3:37:07 PM permalink
Quote: Sonuvabish

Anyone guessing a decimal value...I hope you were just mad there was no bigot option.



the correct answer is one of the decimal value options
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 14th, 2014 at 6:48:52 AM permalink
In order to not confuse things, instead of rewriting the correct equations here, I have edited post https://wizardofvegas.com/forum/questions-and-answers/math/18112-harder-deal-or-no-deal-problem/3/#post358799.

I am exploring the track of analysing the difference v(n) - v(n-1), to see what happens if this tends to zero (as it should if there is a limit). But it does not seem promising (I still am stuck with n-tiered integrals).
Reperiet qui quaesiverit
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 14th, 2014 at 1:05:04 PM permalink
Done a little computation on an envelope.
Giving v1 = 1, v2 = .75, v3 = .684293 and v4= .655396

So I conjecture the answer is "around .64".
Reperiet qui quaesiverit
miplet
miplet
  • Threads: 5
  • Posts: 2105
Joined: Dec 1, 2009
May 14th, 2014 at 1:43:46 PM permalink
Quote: kubikulann

Does anyone have a solution for typing an integral sign ?


∫= & int ; without the extra spaces
“Man Babes” #AxelFabulous
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 14th, 2014 at 1:47:57 PM permalink
∫ thank you dx
Reperiet qui quaesiverit
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 14th, 2014 at 2:21:53 PM permalink
The general solution to this for n remaining cases is.

x^n= summation(r=1 to n)[nCr * x^(n-r) * (1-x)^r * (1/r)], 0<x<1.

We solve for x in this equation to find the threshold where we should keep the case when there are n cases remaining

The left hand side of the equation is the probability that all the remaining cases are lower value.

The right hand side is the probability of having 1 or more better cases remaining and choosing the highest value among them. The probability of having r better cases is [nCr *x^(n-r)*(1-x)^r].. if you have r remaining cases the probability of selecting the correct one is the probability that it is first in order, hence the 1/r term. Then we should sum all possibilities for r to get the entire right hand side of the equation.

The selection threshold for n=1 to 20

1 0.5
2 0.6899
3 0.7758
4 0.8246
5 0.8559
6 0.8778
7 0.8939
8 0.9062
9 0.916
10 0.924
11 0.9305
12 0.9361
13 0.9408
14 0.9448
15 0.9484
16 0.9521
17 0.9548
18 0.9572
19 0.9594
20 0.9613

Using a simulation, for large N the probability of selecting the correct case can be shown to be around 0.58.

kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 14th, 2014 at 2:38:10 PM permalink
Quote: chrisr

if you have r remaining cases the probability of selecting the correct one is the probability that the it is first in order, hence the 1/r term.

I don't get that part. Why should it be 'the first in order'? Definitely the player may be choosing one that is further away?

Yet your figures do correspond to my hand calculations for n=1 to 4, so your approach must be compatible with mine. I simply don't see why...
Reperiet qui quaesiverit
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 14th, 2014 at 2:43:02 PM permalink
Quote: kubikulann

Quote: chrisr

if you have r remaining cases the probability of selecting the correct one is the probability that the it is first in order, hence the 1/r term.

I don't get that part. Why should it be 'the first in order'? Definitely the player may be choosing one that is further away?

Yet your figures do correspond to my hand calculations for n=1 to 4, so your approach must be compatible with mine. I simply don't see why...



because you will always choose to keep a case with a value greater than the selection threshold in hand for the remainder of the sequence.
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 14th, 2014 at 2:46:58 PM permalink
...because the selection threshold goes down. Right! Thanks for the fun.

Too bad the answer is above .50. We won't have invented the new game of the season... I doubt run-of-the-mill casino goers would play a game where their winnings are less than even, even though their odds are better.
Reperiet qui quaesiverit
AceTwo
AceTwo
  • Threads: 5
  • Posts: 359
Joined: Mar 13, 2012
May 15th, 2014 at 2:03:49 PM permalink
Chrisr
I am sure your solution is the correct.
But, I have used my suggested solution (very simple)
You stop whenever X^(n-r)>0,5
And run a few sims and get as answer around 58%.
The sims was for only 100 briefcases and the sim run for 1 million iterations.
Any comments why should this simplified strategy produce similar Results.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 15th, 2014 at 4:29:36 PM permalink
Quote: AceTwo

Chrisr
I am sure your solution is the correct.
But, I have used my suggested solution (very simple)
You stop whenever X^(n-r)>0,5
And run a few sims and get as answer around 58%.
The sims was for only 100 briefcases and the sim run for 1 million iterations.
Any comments why should this simplified strategy produce similar Results.



i think the simulation is programmed incorrectly..
kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
May 16th, 2014 at 9:44:34 AM permalink
Or "around .58" is not exactly equal to "around .58" :-)

Like .584 is better than .578
Reperiet qui quaesiverit
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 16th, 2014 at 9:48:55 PM permalink
with 100 cases, i think you should be getting around 0.54 with the X^(n-r)>0.5 strategy.
  • Jump to: