Friday puzzle -- One More Envelope Puzzle

Re: Friday puzzle -- One More Envelope Puzzle

David Weaver

Off the top of my head, I would have to say it's going to be something of the form of observing the first N (<10) values and then after that, taking the envelope if it's larger than all of the first N values.

I just don't know what N is and am at work and can't spend time running through the scenarios.

I know, though, just for an example, if you pass the first 9 and take the 10th, your odds are 10%. If you take the first, your odds are 10%.

If, for example, you pass the first 8, the odds are 1 in 5 that the largest envelope is in the last two. If the largest is in the last two, the remaining envelope is equal chance of being the smallest to the next to largest.

If #9 then is not the largest, and you take it because it's larger than the others, the only way you take it is if it is in the 9th position. I *think* that chance is one in 9 when #10 is conditioned to be the last. Half the time when 10 is in the last two, 10 will show up first.

Those half you win. That's 10% likelihood. Using the strategy, if 10 is in the second position, one time in 9, 9 is the other number in the first position.

So of the other 10%, 88.9%, you decline to take that one and you get to ten in the second position.

I believe that would be an 18.9% chance to win using that strategy.

Ghee...that's a very labor intensive start when I purposely picked the easiest scenario.

On the right track

Re: Friday puzzle -- One More Envelope Puzzle

Larry Barrett

Following along the same line of thinking outlined by David, this is how I look at this problem:

Label the 10 envelopes A to J (to avoid confusion with the probabilities).

1.Open envelope A. A has a 1/10 probability of being the largest amount. Also, the probability that the largest amount is in envelopes B-J is 9/10.

2.Reject envelope A and open B. If B is smaller than A, then the probability that A was the largest amount is 1/9, and the probability that the largest amount is in envelopes C-J is 8/9. If B is larger than A, then the probability that B is the largest amount is 1/9, and the probability that the largest amount is in C-J is 8/9.

So at this point, A has been rejected; if B was smaller than A, then clearly you want to reject B and open C. If B is larger than A, it has a 1/9 probability of being the largest. You can choose to stop here or reject B and open C. If you stop, you have improved your chance of having the largest amount from 1/10 to 1/9.

3.If you continue, open C. By the same reasoning, if C is smaller than the larger of A or B (designate this by [A,B]), then the probability that [A,B] was the largest amount is 1/8 and the probability that the largest amount is in D-J is 7/8. If C is larger than [A,B], then probability that C is the largest amount is 1/8 and the probability that the largest amount is in D-J is 7/8.

So at step N (N=1 to 10), if the the envelope is smaller than [A, ...], then the probability that the [A,...] was the largest amount is 1/(10-(N-1)); but if the envelope opened at step N is larger than those opened earlier, then the probability that it is the largest amount is 1/(10-(N-1)) and the probability that the largest amount is in the remaining envelopes is (10-N)/(10-(N-1))

If you get all the way to envelope I (9th step) and it is smaller than [A,..,H], then the probablity that [A,..,H] was the largest amount is 1/(10-8) = 1/2, and the probability that the largest amount is in envelope J = 1/2. If I is larger than [A,..,H], then the probability that I is the largest amount is 1/2 and the probability that J is the largest is also 1/2.

An improvement, but not optimal

Alex Y

It took a while for me to come to this conclusion, so check me out. I think your method is equivalent to saying "Reject the first envelope, then pick the first subsequent envelope (if any) containing a larger amount." Following your process, [A,B,...] is always A, since if you get a number larger than A at any stage, you quit.

I think your strategy gives you an 28.29% chance of winning.

Answer

Alex Y

Your best strategy is to reject the first four envelopes, noting the largest amount in them, then to pick the next one you open with a larger amount. This will work about 40% of the time.

This puzzle is credited to Martin Gardner from about 1960. It appears in various guises as "the Sultan's Dowry" (picking the daughter with the largest dowry), "the secretary problem" (hiring the most qualified secretary, when there is no call-back of previous candidates), or picking the best mate.

Interestingly, you can do almost as well picking the best of 100 or 1000 as you can with 10. As the number of envelopes (or daughters or job candidates) n-> inf, the optimal strategy is to reject the first n/e envelopes, then pick the next higher one, with a success rate of 1/e (abt 37%)

The math

Alex Y

In case there are any other probability geeks out there.

This assumes that the best strategy is to observe a number of instances, then pick the next higher one. I haven't seen a proof that this is optimal, just a derivation of the probability using this approach.

n envelopes

k rejections, then pick the first among k+1, k+2,...,n that is larger than the largest in the first k.

Assume that the largest amount is in envelope m. If m>k, then the probability that we will choose it is k/(m-1). Pr: Consider the first m-1 amounts. If the largest of those is in the first k envelopes, we will select m; otherwise we will select an earlier envelope.

The probability that the largest amount is in m is 1/n, so the probability that it is in that envelope and we choose it is 1/n*k/(m-1).

Looking at all the possible positions for the largest envelope and our success at picking it, we find that our probability of success is

(k/n)*Sum(m=k+1:m=n)(1/(m-1))

For n=10 and k=4, that is

4/10*( 1/4+1/5+1/6+1/7+1/8+1/9) = 39.83%

For other values of k, the probability is lower.