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

AceTwo
AceTwo
Joined: Mar 13, 2012
  • Threads: 5
  • Posts: 359
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
Joined: Dec 10, 2013
  • Threads: 7
  • Posts: 584
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
Joined: Dec 9, 2013
  • Threads: 13
  • Posts: 141
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
Joined: Mar 13, 2012
  • Threads: 5
  • Posts: 359
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
Joined: Jan 24, 2010
  • Threads: 66
  • Posts: 339
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
Joined: Mar 13, 2012
  • Threads: 5
  • Posts: 359
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
Joined: Dec 9, 2013
  • Threads: 13
  • Posts: 141
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
Joined: Mar 12, 2011
  • Threads: 10
  • Posts: 905
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
Joined: Sep 12, 2012
  • Threads: 32
  • Posts: 5761
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
Joined: Dec 9, 2013
  • Threads: 13
  • Posts: 141
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.

  • Jump to: