Harder deal or no deal problem

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: 151

Joined: Apr 15, 2011

May 7th, 2014 at 10:28:03 AM permalink

edit: OP just posted same clarification

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

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

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

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

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

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

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

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

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

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

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

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

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 a_n, with a₁ =0 ; a₂ =0.5 ; a₃ =(1+sqrt6)/5 ~=0.69 ; a₄ ~=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 w_n(x) as the value (= the prob of winning the game) of refusing a draw of value x at the n^th draw before the end, conditional on this x being the highest so far.
Define u_n(x) as the best value if, at the n^th 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 v_n as the integral of u(x). This is the prior value of the game with n draws, when applying optimal strategy.
Define v_n(t) as the partial value of observing a next draw better than the current maximum observed t, when applying optimal strategy.
Of course, v_n is equal to v_n(0).

Typically,
w₁ = 0 (refusing the last one!) ;
u₁ = 1 (you have the max);
v₁ (t) = integ_t¹ u₁ (x) = 1-t

I find
w₂(x) = (1-x) (= x w₁ + v₁ )
a₂ = root of equation {x=w2(x)} = 0.5
u₂(x) = Max[ x, w2(x) ] = two-pieced function: 1-x from 0 to 0.5, x from 0.5 to 1
v₂(t) = integral of u(x) from t to 1 =
(if t < a2) integ_t^a2 w₂(x) + integ_a2¹ x
(if t > a2) integ_t¹ x

w_n (x) = x w_n-1 (x) + v_n-1 (x)
a_n = root of equation {x^n-1=w_n (x)} Polynomial of degree n-1
u_n (x) = Max[ x^n-1, w_n (x) ] = n-pieced function along the a_i 's
v_n (t)= integral of u from t to 1 = from 1 to n integrals according to where t lies among the a_i '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 v_n , likely when n tends to infinity (BUT still is finite!!)

Reperiet qui quaesiverit

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

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

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

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: 2146

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

Threads: 27
Posts: 905

Joined: Jun 28, 2011

May 14th, 2014 at 1:47:57 PM permalink

∫ thank you dx

Reperiet qui quaesiverit

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

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

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

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

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

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

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