Monty Hall's Revenge

[ChienFou]

Discard the first 100/e bags noting the sums of money in each. Take the first bag containing more than any sum found in any discarded bag. Feels about right, couldn't prove it to save my life.

[ralphmerridew]

This is just a bigger version of The Fattest Stack.

[JToomey]

This is so unfair:

> You watch, along with the rest of the crowd,
> as a door opens revealing the car of your
> dreams (a 1981 Chrysler Station Wagon).

There's no WAY I could concentrate with that station wagon -- the car of my dreams! -- staring at me. I mean, come on! Either close that door back up and give me some time to get my heart rate under control, or I'm as good as done.



------------------
The Big, Stupid Puzzle:
http://www.yark.org/puzzle

[santaclaws]

Using the Fattest Stack Method will make your probability of winning 5.2%

The formula for the percentage for any number of population bags (n) can be derived as follows:

If the first bag has the lowest amount of money in it then you will select the next bag. The probability of this bag being the winner is 1/(n-1) since there is only one winning bag and (n-1) bags left.
If the first bag contains the second smallest amount who will pick any bag but the lowest and thus the chance of winning is 1/(n-2)
This pattern continues and:
If the first bag contains the third highest amount you have 1/2 chance to win because there are only 2 bags with greater amounts to be selected.
If the first bag contains the second highest amount you will win because there is only the highest amount to be selected.
If the first bag contains the highest amount though you automatically lose because you dont choose it.

Since all combinations have the same probability of occuring the total chance of winning is given by :

[ the sum of all fractions 1/(k-1) { from k=1 to k=n-1} ] divided by n

This is equal to 5.2% for n=100 and equal to 45.8% for n=4 as in the Fattest Stack.

[mathgrant]

I would choose the first bag to have less money than the previous one, because I don't like Chrysler. Then I'd only have a 1/100! chance of winning.

------------------
"I meant to join the Algebra Club, but I joined the Complex Number Club instead, and a lot of my friends were -- imaginary. . ." - Alfie!!!!!

[Icarus]

The way the puzzle is phrased, the strategy I would use would be to ask the host what is the highest amount in a single bag. Then I would continue to open bag after bag until I found the bag with the highest amount.

[santaclaws]

Actually, the best way to win is to strangle the host with his own microphone cord; then throw all the money bags in the trunk of the Chrylser; then drive the car into the audience and knock as many people down as you can. FInally pick up all their wallets and jewellry and high-tail it out of the country.

[gemmaTheCat]

I would choose this method:
Look in n bags and determine the most money in them, and then select the first bag that exceeds this amount in the remaining 100-n bags.

Winning condition:
We will win if the bag with the second most money is in the first n bags, and the bag with the most money is in the remaining 100-n bags. What is ‘n’ that will give me the maximum chance?

The chance that the first n bags contain any particular bag is n/100 (eg: the bag with the second-most money.

The chance that the first n bags do NOT contain any particular bag is (1-n/100) (eg: the last lot of bags contain the bag with the most money)

Therefore the n/100(1-n/100) is the chance that we have a winning condition (as above). I won’t go through the solution, but the maximum value of this expression is 0.25 where n=50.

So if I look in 50 bags and remember the maximum amount in these bags, and then stop as soon as I find a bag with more than this amount, then I have a probability of winning of at least 1 in 4.

In fact, even if the bag with the second most money is not in the first 50, there is still a small chance of picking the correct bag.

[Chuck]

Should the amounts in the bags that I've opened matter? If each of the first 20 bags contains between $10 and $20 and bag 21 contains $75 should I keep it? It's well above the average amount I've found so far. It seems like it would have a better than average chance of being the highest.

[This message has been edited by Chuck (edited 01-29-2002 08:11 PM).]

[ralphmerridew]

Well, you will win if the bag with the second-most money is in the first half, and the bag with the most isn't, but that probability is low; you'll also win if the third-highest is in the first fifty, and the second-highest is after the highest.

[GemmaThe Cat]

I don't think that one chance in four is "low"!!
Have you a solution that gives a higher chance?

[Laramie]

The approaches discussed here (gemma's and santa's in particular) are fine given that the distribution is continuous and has an infinite range in both directions. For a discrete distribution or for one that is bounded (non-negative, for example), the problem is far more complicated and is not all that tractable.

Suppose, for example, that your strategy is to open the first five bags and then take the first bag after that that has more money than the highest of the first five. This seems like a reasonable approach, but suppose the first five bags have $0.00, $0.01, $0.02, $0.03, and $0.04. If the sixth bag has $0.05, you would take it (according to your strategy). Because each bag has a different amount of money, however, you know that the maximum cannot be $0.05.

The implication of this idea is that a pure strategy (roughly one that follows a rule with probability one) cannot be the optimal strategy. In choosing such a strategy, we ignore most of the information we receive along the way. Instead, it must be that we accept a given bag with some probability (a "mixed strategy" for you game theorists) that is increasing in the amount observed. The bottom line is that we can do better with a mixed strategy than with a pure strategy.

Incidentally, Chuck's example also illustrates the problem with a pure strategy.

[ed to fix typo and expand a bit]



[This message has been edited by Laramie (edited 01-30-2002 10:07 AM).]

[Icarus]

O.K. - Maybe I'm reading too much into this, but read the way the puzzle is phrased. It states

If, however, you manage to find the bag with the most money, you will also win this!"

It doesn't state if you manage to keep the bag with the most money.

So if you take the puzzle literally, then why not simply choose to open every single bag. Eventually you will find the bag with the most money.

[mith]

bad phrasing on my part. *~goes off to change "find" to "choose"~*

[Fjord]

I'm fairly certain that gemma's method (the closest so far), is incorrect. It is good quick work, but it ignores the special case too much. The special case is when neither the highest nor second highest is in the first set. In fact, there are a bunch of these cases (you get the 3rd highest in the set but not the two higher, you get the 4th highest in the set but not the 3 higher).

From this I tried out a few values of n.
p(n=1)=1/100 // p(1 is second highest)
+1/100*1/2 // p(1 is third highest)*p(first in front of second)
+1/100*1/3 // p(1 is fourth)*p(first in front of 2nd&3rd)
+...
+1/100*1/99 // p(1 is last)*p(first in front of 2nd-99th)

p(n=2)=2/100*(1-1/100) // p(1 or 2 is second)*p(the remaining is not first)
+2/100*(1-1/100)^2*1/2 // p(1 or 2 is thirst)*p(remaining is neither first nor second)*p(first is in front of second)
+...
+2/100*(1-1/100)^98*1/98 // p(1 or 2 is second last)*p(the remaining is not 1st-98th)*p(1st is in front of all 98)

From this I got the general pattern
p(n)=n/100*sum(i=1..100-n)(1-(n-1)/100)^i/i

I then wrote a program to iterate through the values for n=1..100. I also had my program experimentally try to deduce the answer by running 10000 separate trials using that n as a strategy. Unfortunately the experimental way does not yeild the same probabilities as the theoretical I derived (even if the # trials are put up to 1m), but they both never let n=50. The theoretical has n=37, the experimental will have the winner around that number. Here is a sample output, with the n, the theoretical percentage chance to win (over 1/3rd!), and the experimental chance to win (only off by .005):

25: 0.3567790888985053 0.3497
26: 0.36043653388547875 0.3554
27: 0.3637098849481358 0.3471
28: 0.36661332959400816 0.3502
29: 0.3691600459849939 0.3629
30: 0.37136230680009713 0.357
31: 0.3732315693408347 0.3647
32: 0.3747785540808324 0.3721
33: 0.37601331345210015 0.3669
34: 0.3769452923373145 0.3663
35: 0.37758338148015685 0.3677
36: 0.37793596481951314 0.3664
37: 0.3780109615868271 0.3737
38: 0.37781586387066574 0.3601
39: 0.37735777024206296 0.3662
40: 0.3766434159433767 0.3671
41: 0.3756792000684029 0.366
42: 0.37447121009918866 0.3711
43: 0.3730252441130305 0.3612
44: 0.37134683092959275 0.3639
45: 0.3694412484314235 0.3571
46: 0.36731354026017493 0.3615
47: 0.36496853106452826 0.3469
48: 0.3624108404534559 0.3484
49: 0.3596448957892983 0.338
50: 0.3566749439387323 0.35

So I'm currently inclined to say 37, but I don't think my theoretical equation is correct (which could make it 36 or 35, I'm pretty sure it's in the 30s). Can anyone see where I went wrong?

[This message has been edited by Fjord (edited 01-30-2002 04:47 PM).]

[Fjord]

Actually, I just noticed that ChienFou's result (the first in the thread) is the same as mine: 100/e ~=36.8. Rounding gives my 37

Damn! How did he do that?

[Zarriar]

I disagree with you Laramie, if you suspect that the bags are in some kind of order then you can sample them randomly. I didn't see anywhere in the puzzle that you have to pick bags 1 to 100 in order.

[Laramie]

My point does not depend on order at all. I assumed a random draw and then apparently used a misleading example. Suppose, for example, that there are 100 bags and you observe $0.76, $0.84, $0.02, $0.25, and $0.64. If the next bag contains $0.98, would you take it? No! Because the distribution is discrete and no two bags contain the same amount, we know that the maximum must be at least $0.99.

This example is simplistic, but the intuition behind it applies in less obvious cases. The lower the numbers you observe (even if they are greater than $1 in this cases), the less likely it is that the given number is the maximum. The idea is that although we don't know the distribution to begin with, we can infer something about it by examining the observations along the way.

[DJC]

I am throwing in my vote for Laramie's logic. The standard formulation of the problem allows for ties. I have even seen it expressed in terms of needing to choose a bride from a sequence of possibilities - but no chance to go back. For this, I agree with the 100/e rule though I may not be wild about participating in the contest. But Laramie is surely right. If the money is in discrete amounts (whether cents or dollars) and we know there are no ties, then we know a lower bound on the highest value bag - if the units are dollars, then at least $100, if cents (or if we do not know whether dollars or cents), then at least $1. If this sum has not been exceeded in the first 36 draws, then there is an obvious refinement to the 100/e rule that cannot make you worse off and may make you better off. Suspect this will make the optimising rule quite complex - look forward to seeing the solution.

[Zarriar]

That makes more sense to me Laramie.

Hopefully the gameshow host hasn't thought of that and put fines of various amounts in some of the bags to represent negative dollars

[Fjord]

I figured out an error in my theoretical probability. The a closer equation is

p(n)=n/100*sum(i=1..100-n)(1-(n-1)/(100-i))^i/i

The reason is that since I have already chosen one of the positions to be a specific ball and I'm saying that i other balls are not in the set, so I have to pick the ball from 100-i balls. This is represented by the "-i" in the denominator.

This gives a result closer to the experimental results. I'm actually pretty sure this is right, but there could be another error in there. The result is still 37.

36: 0.3679286301096208 0.367175
37: 0.368004009280318 0.368377
38: 0.36780926479219306 0.366936

Still wonder why 100/e works though.

[Laramie]

See problem 26 at http://www.thewizardofodds.com/math/group2.html . A solution (37) and explanation for the non-discrete case is given there.

[Fjord]

Ok. It looks like my last p equation is wrong, given the solution in Laramies link. I see the error (actually, I got those results as an interim step, but thought they were in error, oh well).

[kevsterogg2001]

I wouldn't care about the car. I don't want a Chrysler car, but I'll take what I can get. I would start by asking the host how much money is in the bag that has the most money. If he/she tells me, then start counting money in bags. If not, then I would start by lifting the bags. The heaviest ones I would look in because they probably have mostly coins, not bills. Then look in each bag. Take the one containing mostly $100 bills, becausde that one will probably be the one that contains the most money, then the car will be yours.

[CrystyB]

sorry.
My initial reaction was:
1. This should be Fattest Stack's revenge.
2. How in the world would you answer this, mith? Who decides what puzzles are worth the post???
I see both these points HAVE been answered. I WILL read this topic as soon as i get the time.


[This message has been edited by CrystyB (edited 02-01-2002 10:08 AM).]

[CrystyB]

Last year I actually did some extensive study on this problem for small n's. Here are the results:

3 4 - 1st [0.5 0.4583]
5 6 7 - 2nd [0.43333 0.427778 0.4142857]
8 9 10 - 3rd [0.4098214 0.4059524 0.3986905]
11 12 - 4th [0.3984127 0.3955147]
I also have these (and others) probabilities as fav.cases and irred.fractions, if anyone wants to be spared the computing process.

13 was uncheckable because 13! (the total number of situations) exceeds 2^31 (long-integer).

In short:
So int(n/e) does not work for 5 and 8. My idea is int((n+1)/3). I can't prove it either.

[Chuck]

There are programming languages with longer integers. I use UBasic which uses 2600 digit integers.

What if the first bag I choose has a million dollars in it? I would certainly keep it. Even though there's a good chance I could get more, maybe a lot more, I wouldn't risk a million dollars on continuing.

[ChienFou]

How did I guess/know it's 100/e? I've played mathematical games all my life, as have many of my friends. What I do know is that any problem of this class which has a solution convergent on a saddle point (ie the closer to being correct, the greater the expectation) inevitably involves 'e'. In seriously unpleasant cases it can have a 'pi' thrown in as well. It seemed self-evident to me that the answer is about 1/3 (because that leaves 2 chances in three that the largest bag is unchecked - this is very loose I agree), and given that e is about 2.8 it seemed the obvious answer.

There are families of this problem, sometimes the answer is 63 [100(1-1/e)] but that fraction 1/e always turns up. So like I said, I've no clue how to prove it, although I probably could have derived your formula if my life depended on it, but I was pretty sure it was right.

[Chuck]

It's all because the graph for x^(1/x) reaches its high point when x = e.

[mtc32]

I believe that in this problem that we have to assume that you can't determine what bag has the most money based on what the opened bags contained. If you opened a dozen bags to see that they all had less than a dollar and then you choose one that had more than a dollar, you can't say that that bag is the winner. The funny part is that if this game was on Let's Make a Deal, I would seriously doubt that one in 3 would win. People would not know what strategy to pick.

[CrystyB]

Chuck, that depends on how much one thinks of a million dollars. I agree it's big, but for me it's only a number...

As Laramie said "we ignore most of the information we receive along the way". There is nothing wrong here, because we DON'T receive any info along the way... (i recall from the original F.S. that the amount of money was not guessable, and you could only perceive which is bigger)

[This message has been edited by CrystyB (edited 02-03-2002 05:34 AM).]

[Chuck]

The problem is a lot less interesting if you can only perceive which amount is larger. It's too unrealistic. You might as well just post an equation to be solved. There seems to be little point in dressing it up with Monty and the car if you're going to remove all traces of reality from it.

[extropalopakettle]

[Chuck]

Cool! I've always wanted to search for billion digit primes.

[extropalopakettle]

Java is free. The hardware isn't.

[DJC]

Two points. First, the discussion appears to have agreed to settle on the non-discrete interpretation of the problem that looks more tractable, though it is obvious that it still has its challenges. The discrete interpretation should offer a rule that depends on the contents of the bags opened so far. Anyone want to take the discrete case further or do we just treat it as too hard?

On the issue of taking the first bag if it has $1m, this is really about objective functions. The question specifies a very clear objective function - to maximuise the chance of winning the car by maximising the probability of choosing the bag with the most money. I guess that is the problem we need to solve. Chuck quite sensibly says his objective would be different and most of us offered a certain $1m would be less excited about a small chance of winning the car and a possibly big risk of getting a lot less than $1m. But it leads to a question that is different from that asked.

[Chuck]

Well, I'm sure they'd sell me the car for a lot less than a million dollars. But you're right, it's not just getting the car, it's winning it. There're no bragging rights for paying for a car that was made in 1981.

[Woodrat]

OK -
Step 1 - Open 35 random bags noting the highest two amounts -
Step 2 - begin opening another 35 bags accepting the first one greater than the highest in Step 1 -
Step 3 - If no bag in Step 2 is higher than the highest in Step 1 then begin opening the remaining bags accepting the first one that is greater than the second amount in Step 1 - This may be also greater than the highest amount from Step 1.
Of course the two highest amounts could have been in Step 1 and you would go away with only whatever was in the last bag opened - but then you would also be spated the embarassment of having to drive the car.

[CrystyB]

n is given as 100. The pure strategy is to let k go by and choose the first that is bigger than the max of those first k.

Let me reduce the problem to handle only permutations, that is values of only 1..n, so that max of the first k is >= k.

SUM for i_from_k_to_n of P(max[1..k]_is_i)*P(next_bigger_than_i[k+1..n]_is_n)

in [k+1..n] we have n-i biggers and i-k lessers.

given "a Q and b R", what is the P that the first R is a given number, x?
it is 1/b !!!
Very cute, but i did NOT manage to spot this at first glance (i had to run a few tests =[ )

so now P = SUM for i_from_k_to_(n-1) of {P(max[1..k]=i) / (n-i)}
( if max of the first was n, P is 0 (and btw n-i=0, thus T_(i=n) would have been meaningless) )

but that probability IS P=[(i-1)!*(n-k)!*k]/[n!*(i-k)!], believe me (although i am extrapolating).

and through running spreadsheet calculations for various k's, optimal_k is [drum rolls please!] 37 (sorry i doubted y'all).

[Laramie]

The problem (including the non-discrete case) is very difficult because it "should" depend on our prior beliefs. When we observe, say, 5 amounts, we revise our beliefs about the underlying distribution and then condition our decision on those beliefs. In this case, we are given no prior belief. That does not mean that we cannot improve our lot, however. The typical approach is to accept the current bag with some probability that is increasing in the amount in the bag. One strategy, for example, might be to observe the first 100/e bags and then accept the next bag (assuming it is the largest thus far) with probability min[(x-M)/M,1], where M is the maximum up to that point and x is the current observation. Suppose that M=$1000 and we observe x=$1100. We would accept with probability 0.1. Similarly if x=$3000, we accept with probability 1. In this way, we incorporate our instinctive belief to accept an amount if it is a great deal higher than the current maximum.

I am not arguing, incidentally, that this is an optimal strategy. Rather, I'm arguing that we might be able to increase our chances with a strategy of this nature. Personally, I would tie my decision to the standard deviation of the previously observed values.

I'll post a related (and very interesting problem) in a few minutes.