Poll

1 vote (11.11%)
4 votes (44.44%)
No votes (0%)
No votes (0%)
No votes (0%)
No votes (0%)
3 votes (33.33%)
No votes (0%)
No votes (0%)
1 vote (11.11%)

9 members have voted

chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 6th, 2014 at 9:06:28 PM permalink
You see N briefcases each with a different amount of money written on the inside. You have no idea how the amounts are distributed or what the amounts are. 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?



zzzzzzzzzz
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 9:14:38 PM permalink
I am voting for
1/N
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
May 6th, 2014 at 9:17:28 PM permalink
1/3
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 9:23:19 PM permalink
I guess the question is, what is the value of the potential information you get by opening as many cases as you want?

If you have a million briefcases, the odds that the first one you open will be the highest are 1/million. So you can gain information by opening more cases. But really, how much information do you gain? Because the numbers can be anything. They don't have to fall on some standard curve.

You could have 10 cases and the numbers could be

1

8

8974893789

2

11

16

19

17

500

7894732987432




Even if one seems like an outlier worth stopping at, you have no way of knowing the distribution.


Obviously, you could keep opening cases until you get one with a higher number all previous cases. Does that help you?
geoff
geoff
  • Threads: 3
  • Posts: 368
Joined: Feb 19, 2014
May 6th, 2014 at 9:27:04 PM permalink
I totally read the problem wrong. I thought it was just the regular deal or no deal where you knew what the amounts could be.
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 9:29:48 PM permalink
OK, thinking about it more, I think opening cases until you have a larger number than any previous case does help you beat 1/N. But I have no idea how much it helps you.
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 9:37:20 PM permalink
Quote: Wizard

1/3



How can this be right, though? He didn't specify how many cases. If the game were just two cases, you could beat that by blindly picking one.
FinsRule
FinsRule
  • Threads: 128
  • Posts: 3914
Joined: Dec 23, 2009
May 6th, 2014 at 9:39:28 PM permalink
Quote: sodawater

Quote: Wizard

1/3



How can this be right, though? He didn't specify how many cases. If the game were just two cases, you could beat that by blindly picking one.



I thought he was being flippant because its a ridiculous problem. Don't want to speak for him though.

My answer is that it was impossible.
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 9:43:19 PM permalink
Quote: FinsRule

Quote: sodawater

Quote: Wizard

1/3



How can this be right, though? He didn't specify how many cases. If the game were just two cases, you could beat that by blindly picking one.



I thought he was being flippant because its a ridiculous problem. Don't want to speak for him though.

My answer is that it was impossible.



If it's impossible, then there would be no strategy better than just sticking with your first case. hence 1/n
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
May 6th, 2014 at 10:23:05 PM permalink
This is the Secretaries (aka Sultan's Dowry) problem, for which the answer is something like, pass on the first N/e (e as in the base of natural logarithms) briefcases, then take the first one you open that is higher than the rest that you had opened up to that point; the probability is slightly higher than 1/e, so, given the choices, I'd say "around 1/3".
endermike
endermike
  • Threads: 7
  • Posts: 584
Joined: Dec 10, 2013
May 6th, 2014 at 10:25:22 PM permalink
I don't remember how to find the solution off the top of my head and I plan on going to bed shortly.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
May 6th, 2014 at 10:27:59 PM permalink
Quote: sodawater

How can this be right, though? He didn't specify how many cases. If the game were just two cases, you could beat that by blindly picking one.



My answer is not appropriate for small numbers of cases, like less than ten. You specifically do not know anything about the distribution. However, the way this problem is usually stated is every suitcase has a different amount, and you're given this information before starting.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 10:29:21 PM permalink
Quote: ThatDonGuy

This is the Secretaries (aka Sultan's Dowry) problem, for which the answer is something like, pass on the first N/e (e as in the base of natural logarithms) briefcases, then take the first one you open that is higher than the rest that you had opened up to that point; the probability is slightly higher than 1/e, so, given the choices, I'd say "around 1/3".



Very interesting.

http://en.wikipedia.org/wiki/Secretary_problem

OP did specify the minimum probability of success following optimal strategy, so 1/e looks correct. But in the exact case of 2 cases, you could achieve 1/2 by any strategy. However 1/e is less than 1/2 so I guess it technically is still correct.
sodawater
sodawater
  • Threads: 64
  • Posts: 3321
Joined: May 14, 2012
May 6th, 2014 at 10:35:09 PM permalink
Quote: Wizard

My answer is not appropriate for small numbers of cases, like less than ten. You specifically do not know anything about the distribution. However, the way this problem is usually stated is every suitcase has a different amount, and you're given this information before starting.



From wikipedia:




So it looks like the wording of the original problem (and the answer choices) could have been modified a little to avoid these cases.
chrisr
chrisr
  • Threads: 13
  • Posts: 141
Joined: Dec 9, 2013
May 7th, 2014 at 8:41:03 AM permalink
I didn't know this problem was so well known. I guess it makes sense since the final answer is quite simple.

The probability of winning is always greater than 1/e regardless of N, so around 1/3 is the best answer.


A harder problem: You know the distribution of the cases is uniformly distributed between $0 and $1,000,000. What is the probability of winning now? [split thread]
  • Jump to: