A Dollar Urned

davar55 · 2008-10-18, 01:35

An urn contains 100 balls labeled $1 through $100 inclusively.

You are given 50 chances to select a ball by the following procedure:
take two balls out of the urn; look at ONE of them; if you decide to keep
that one, discard the other; else discard the one you looked at and keep
the other (you may now look at it). Do not replace the balls.

Your object is to accumulate a maximum sum. What is your strategy, and
what sum can you expect to accumulate? (The reference to money is just
to keep the thread title relevant.)

axn · 2008-10-18, 02:18

I don't have an analytical solution. Doing some simulations using random
numbers indicated the following strategy as the best:
"Keep anything > 50"
With this strategy, the simulations give an expected value of 3156. Looks
like approximately (1-1/e)*100*50.

EDIT:- Just realized that there may be a better strategy. Need more programming.

davieddy · 2008-10-18, 09:51

We can keep track of whats left in the urn?

uigrad · 2008-10-20, 20:55

First draw: I get a 3, so I discard it. I now get to look at my other hand before putting it in the keep pile. It's a 2. Oh well.

Second draw: I draw 51. The hidden ball in my other hand is from a group of 97, and this group includes 1, 4-50, and 52-100. The expected value of the ball in this hand is 4995 / 97, approximately 51.49. Since the expected value of the hidden ball is greater than 51, I throw away the 51, and keep the hidden ball, now looking at it.

What I don't understand about the original problem is what happens if we keep the first ball we look at? Do we look at the other one as we throw it away? If not, then this alters our path. Early in the process, we should choose the hidden ball anytime the expected value is close to the viewable ball, just so that we can glean more information. The advantage of this information is rather minimal, so if the expected value is less than the known ball by more than one, I would still take the known ball, and not worry about losing that information.

Wacky · 2008-10-20, 23:47

I don't think that you are allowed to look at the second ball if you choose to take the first.
We don't really care about the MEAN (average) value of the unknown balls. It is actually the MEDIAN that should be the threshold.

Knowing the value of the first ball, we should keep it iff it is expected to be greater than the second one. That is determined by the number of unknown balls which are greater than the disclosed first ball and the number of unknown balls which are less than it.

I don't think that you ever gain anything by violating this rule in order to "gain additional knowledge". The expected cost of that knowledge outweighs the expected value of it.

jrk · 2008-10-21, 00:51

Quote:

Originally Posted by Wacky

We don't really care about the MEAN (average) value of the unknown balls. It is actually the MEDIAN that should be the threshold.

Knowing the value of the first ball, we should keep it iff it is expected to be greater than the second one. That is determined by the number of unknown balls which are greater than the disclosed first ball and the number of unknown balls which are less than it.

No, it is the MEAN that you should look at, not the MEDIAN.

Consider that there are four balls, valued 1, 98, 99, and 100. You draw two of them.

You look at one that you drew and it is 98.

The mean (expected value) of the other three balls is 66.7 but the median is 99.

The reason the mean is important is because while there are more balls higher than 98 than below 98, the difference you gain by getting a higher ball is insignificant to the amount you can lose by getting the 1.

Consider:

1) You trade and get a 1, change -97.
2) You trade and get a 99, change +1.
3) You trade and get a 100, change +2.

Since all three events are equally likely, your expected change if you throw away the 98 is -31.3 (or 98-66.7).

So because 98 is greater than the mean (expected value) of 66.7, you should keep it.

davieddy · 2008-10-21, 02:39

I agree that the mean (expected return) is the criterion, not the median.
You are trying to win as much as possible, not the most number of times.

wblipp · 2008-10-21, 05:58

I agree with Wacky. The question at each point whether the hidden ball is higher or lower than the visible ball. You always want to maximize the probability of selecting the higher of the two balls, and the median is the right test to do this.

axn · 2008-10-21, 06:26

Quote:

Originally Posted by wblipp

I agree with Wacky. The question at each point whether the hidden ball is higher or lower than the visible ball. You always want to maximize the probability of selecting the higher of the two balls, and the median is the right test to do this.

Simulation results do not agree with this. The results are much worse compared to mean. Oddly enough, the "mean" strategy isn't any better on average (slightly better, after redoing the sims -- 3158 for "mean" vs 3156 for "static") compared to the static strategy in my first post.

Kevin · 2008-10-21, 06:44

First of all, yes, I agree you should be looking at means, not median.

I think the main part of this problem is what to do when you choose to keep the first ball and discard the second ball without looking at it. The key is that if you consider all possible combinations of choosing balls, any ball you haven't seen yet is equally likely to be the one that you threw out, and is equally likely to be the first one you look at in the next pair, and is equally likely to be the second ball in the pair, no matter what stage of the game you're in. So at each point in the game, you compare the value of the first ball you picked to the expected value of every ball you haven't seen yet. This seems to be what Wacky was saying, if you replace median with mean.

It's somewhat counter-intuitive. Say you picked the first ball on the first 5 tries. Then on your next turn, even though you're picking a pair from a set of 90 balls, you still end up looking at the expected value of the 94 numbers you haven't yet seen after looking at the first ball.

davieddy · 2008-10-21, 14:04

Quote:

Originally Posted by Wacky

I don't think that you are allowed to look at the second ball if you choose to take the first.

Can Davar55 resolve this for us please?
Meanwhile I would like to resolve the mean/median debate.

2008-10-18, 01:35	#1
davar55 May 2004 New York City 2×29×73 Posts	A Dollar Urned An urn contains 100 balls labeled $1 through $100 inclusively. You are given 50 chances to select a ball by the following procedure: take two balls out of the urn; look at ONE of them; if you decide to keep that one, discard the other; else discard the one you looked at and keep the other (you may now look at it). Do not replace the balls. Your object is to accumulate a maximum sum. What is your strategy, and what sum can you expect to accumulate? (The reference to money is just to keep the thread title relevant.)

2008-10-18, 02:18	#2
axn Jun 2003 31·163 Posts	I don't have an analytical solution. Doing some simulations using random numbers indicated the following strategy as the best: "Keep anything > 50" With this strategy, the simulations give an expected value of 3156. Looks like approximately (1-1/e)10050. EDIT:- Just realized that there may be a better strategy. Need more programming. Last fiddled with by axn on 2008-10-18 at 02:36

2008-10-20, 20:55	#4
uigrad Aug 2008 86₁₀ Posts	First draw: I get a 3, so I discard it. I now get to look at my other hand before putting it in the keep pile. It's a 2. Oh well. Second draw: I draw 51. The hidden ball in my other hand is from a group of 97, and this group includes 1, 4-50, and 52-100. The expected value of the ball in this hand is 4995 / 97, approximately 51.49. Since the expected value of the hidden ball is greater than 51, I throw away the 51, and keep the hidden ball, now looking at it. What I don't understand about the original problem is what happens if we keep the first ball we look at? Do we look at the other one as we throw it away? If not, then this alters our path. Early in the process, we should choose the hidden ball anytime the expected value is close to the viewable ball, just so that we can glean more information. The advantage of this information is rather minimal, so if the expected value is less than the known ball by more than one, I would still take the known ball, and not worry about losing that information. Last fiddled with by uigrad on 2008-10-20 at 20:55

2008-10-21, 06:44	#10
Kevin Aug 2002 Ann Arbor, MI 433 Posts	First of all, yes, I agree you should be looking at means, not median. I think the main part of this problem is what to do when you choose to keep the first ball and discard the second ball without looking at it. The key is that if you consider all possible combinations of choosing balls, any ball you haven't seen yet is equally likely to be the one that you threw out, and is equally likely to be the first one you look at in the next pair, and is equally likely to be the second ball in the pair, no matter what stage of the game you're in. So at each point in the game, you compare the value of the first ball you picked to the expected value of every ball you haven't seen yet. This seems to be what Wacky was saying, if you replace median with mean. It's somewhat counter-intuitive. Say you picked the first ball on the first 5 tries. Then on your next turn, even though you're picking a pair from a set of 90 balls, you still end up looking at the expected value of the 94 numbers you haven't yet seen after looking at the first ball. Last fiddled with by Kevin on 2008-10-21 at 06:45

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
[$]Recent-update-has-broken-the-dollar-sign[/$]	NBtarheel_33	Forum Feedback	47	2016-10-11 09:43
The missing dollar	Andi47	Puzzles	4	2008-09-11 14:56

2008-10-18, 09:51	#3
davieddy "Lucan" Dec 2006 England 14512₈ Posts	We can keep track of whats left in the urn?

2008-10-20, 23:47	#5
Wacky Jun 2003 The Texas Hill Country 1089₁₀ Posts	I don't think that you are allowed to look at the second ball if you choose to take the first. We don't really care about the MEAN (average) value of the unknown balls. It is actually the MEDIAN that should be the threshold. Knowing the value of the first ball, we should keep it iff it is expected to be greater than the second one. That is determined by the number of unknown balls which are greater than the disclosed first ball and the number of unknown balls which are less than it. I don't think that you ever gain anything by violating this rule in order to "gain additional knowledge". The expected cost of that knowledge outweighs the expected value of it.

2008-10-21, 02:39	#7
davieddy "Lucan" Dec 2006 England 6474₁₀ Posts	I agree that the mean (expected return) is the criterion, not the median. You are trying to win as much as possible, not the most number of times.

2008-10-21, 05:58	#8
wblipp "William" May 2003 New Haven 2×7×13² Posts	I agree with Wacky. The question at each point whether the hidden ball is higher or lower than the visible ball. You always want to maximize the probability of selecting the higher of the two balls, and the median is the right test to do this.