Ladies' night at Morty's

[bonanova]

It was ladies' night at Morty's, and Alex came prepared

to dazzle the girls by using his newly claimed powers of

clairvoyance. As usual, his compatriots Ian and Jaimie

were present. Davie was home, unfortunately, with a cold.

I didn't ask for it, Alex began, in a voice loud enough to be

heard over the slightly annoying music Morty was playing

to encourage couples out onto the dance floor, it just came

on me one night last week. And now I can see, dimly like, it

seems, right through objects. Not all the time, mind you, but

often enough and clearly enough that I can beat the odds

in most simple games of chance.

By now three pretty ladies were at their table, and Alex

proposed the following demonstration of his powers. He tore

a sheet of paper in half four times and asked the other five

to write numbers on the resulting 16 pieces. Think of any

number you like - they don't have to be whole numbers.

They can be the probability of winning the lottery, the

number of beers you expect to drink tonight, or the

number of molecules in the universe. They just have

to be positive numbers, and they all have to be different.

My job then is to find the largest number. I will pull them

out of a hat, one by one, and stop when I think that the

last number I've pulled from the hat is the highest of the

bunch. I get to read the numbers as I pull them, of course.

Now if I used no strategy at all, or did it blindfolded, I'd have

a 1/16 chance of getting it right. But even one of you fellows

could do better than that! But ... given my [here Alex cleared

his throat, softly, out of an abundance of feigned humility]

substantial intellect, and my newly acquired powers of

clairvoyance, I'm prepared to do it four times better.

I'm willing to do this all night, my quid against your four, and

I expect you'll be buying my drinks. What do you say?

Alex's friends exuded a silence born of past experience with his

other schemes, even tho a 1/4 chance of his picking the highest of

16 truly unpredictable numbers seemed to make an attractive bet.

And, oh, not for a moment did they buy the clairvoyance claim.

Finally Jaimie spoke up. Make the odds three to one and you're on!

Ouch! Alex responded, That's asking a lot. But, remembering his

goal of impressing the ladies, Alex agreed.

Did Alex make a good bet? Or did Jaimie finally out-fox his buddy?

Specifically, what is Alex's optimal strategy, and what are his odds of winning?

[superprismatic]

The second strategy I checked makes this a winning game for Alex. The strategy is: Pull numbers from the hat until you draw a number, X, which is larger then the first number drawn, then continue to draw until you get a number, Y, which is larger than X. Declare Y the largest number. If you fail to get such an X and Y, you lose. This strategy finds the largest number with probability about .295. So, the odds of winning are approximately .42 to 1. But, using this strategy, Alex wins 3 quid with probability .295 and loses one quid with probability .705. So, Alex expects to win 3*.295 - 1*.705 = .18 quid per game. Note that the sizes of the numbers are irrelevant to the problem. What matters is their sizes relative to one another. So, without loss of generality, the integers between 1 and 16 inclusive may be assumed. I programmed a simulation of 100,000,000 games. I don't know if this strategy is optimal.

[bonanova]

The second strategy I checked makes this a winning game for Alex. The strategy is: Pull numbers from the hat until you draw a number, X, which is larger then the first number drawn, then continue to draw until you get a number, Y, which is larger than X. Declare Y the largest number. If you fail to get such an X and Y, you lose. This strategy finds the largest number with probability about .295. So, the odds of winning are approximately .42 to 1. But, using this strategy, Alex wins 3 quid with probability .295 and loses one quid with probability .705. So, Alex expects to win 3*.295 - 1*.705 = .18 quid per game. Note that the sizes of the numbers are irrelevant to the problem. What matters is their sizes relative to one another. So, without loss of generality, the integers between 1 and 16 inclusive may be assumed. I programmed a simulation of 100,000,000 games. I don't know if this strategy is optimal.

Your strategy makes Alex a winner, so part credit for that. There is another strategy that does a little better, however, and gets him a couple more beers to share with the ladies.

Regarding your approach, I wonder how crucial a role is played by the number of successively larger numbers you use. Finding the optimal number of these plateaus [given the sample size] is an interesting problem. You'd use an X and Y and a Z at some point, perhaps in the 50-100 range. The increase of plateaus is probably logarithmic with the sample size.

There is a companion problem, to select the highest possible number. If you picked the 2nd highest number e.g., you'd score high in the companion problem, whereas in the OP problem, [highest or no count] it would simply be a losing choice. Your strategy seems a good one for the companion problem, especially with the best choice for the number of "plateaus" employed in the choice.

[WitchOfSecrets]

What about this one? I've heard a variant on this one before, but I've never actually worked the logic for the BEST answer. Here's a reasonably intuitive answer, though, that's similar to superprismatic's approach:

Sixteen numbers have been drawn, right? Let's suppose that Alex draws the first four numbers, and calls the largest of those numbers X. Then he draws until he reaches a number Y that is larger than X.

There is a 1/4 chance that the largest number will be one of the first four numbers drawn. In this case, Alex loses.

There is a 1/4 * 12/15 (.2) chance that the SECOND-LARGEST number will be one of the first four numbers drawn, but the largest number won't. In this case, Alex wins.

There's a 1/4 * 12/15 * 11/14 * 1/2 (~.079) chance that the THIRD-LARGEST number will be one of the first four numbers drawn, the largest and second-largest won't be, and that Alex will encounter the largest number before the second-largest number. Alex wins.

There's a 1/4 * 12/15* 11/14* 10/13* 1/3 (~.04) chance that the FOURTH-LARGEST number will be one of the first four numbers drawn, the top three won't be, and that Alex will encounter the largest number before the second- or third-largest. Alex wins.

There's a 1/4 * 12/15 * 11/14 * 10/13 * 9/12 * 1/4 (.023 ) chance that the FIFTH-LARGEST... etc.

The odds of winning add up to something over .33!

Edited May 22, 2012 by WitchOfSecrets

[bonanova]

Your strategy makes Alex a winner, so part credit for that. There is another strategy that does a little better, however, and gets him a couple more beers to share with the ladies.

Regarding your approach, I wonder how crucial a role is played by the number of successively larger numbers you use. Finding the optimal number of these plateaus [given the sample size] is an interesting problem. You'd use an X and Y and a Z at some point, perhaps in the 50-100 range. The increase of plateaus is probably logarithmic with the sample size.

There is a companion problem, to select the highest possible number. If you picked the 2nd highest number e.g., you'd score high in the companion problem, whereas in the OP problem, [highest or no count] it would simply be a losing choice. Your strategy seems a good one for the companion problem, especially with the best choice for the number of "plateaus" employed in the choice.

Here is the evidence that the number of "plateaus" available for stopping points rises logarithmically with the sample size. The vertical scale is logarithmic. A plateau is added approximately every factor of 3 increase of sample size. For the OP sample size of 16, the average number is about 3.4. This means that after the first number is drawn, there will be a larger number, followed by a larger number, followed by a larger number more than half of the time.

The next plot gives the cumulative probability of encountering a given number of plateaus before hitting the end of the draw, for sample base sizes of 2, 3, 4, 11, 30, 82, 223, 615 and 1670. These are the numbers (4 and larger) that correspond to integral numbers of expected plateaus. One can see the likelihood of encountering various numbers of plateaus, on average, for various sample sizes. An example would be that for a sample size of 1670, if one encounters 8 plateaus, there is a 60% chance there are no more plateaus that follow it.

These number aid in specifying the number of plateaus to use for a given sample size.

The fun part of this puzzle, which has appeared in various forms and forums, is that the first plateau should be small enough to exclude the highest number, but large enough to set a substantial reference point for selecting it. Just where to place it is given by a surprisingly elegant result.

[bonanova]

What about this one? I've heard a variant on this one before, but I've never actually worked the logic for the BEST answer. Here's a reasonably intuitive answer, though, that's similar to superprismatic's approach:

Sixteen numbers have been drawn, right? Let's suppose that Alex draws the first four numbers, and calls the largest of those numbers X. Then he draws until he reaches a number Y that is larger than X.

There is a 1/4 chance that the largest number will be one of the first four numbers drawn. In this case, Alex loses.

There is a 1/4 * 12/15 (.2) chance that the SECOND-LARGEST number will be one of the first four numbers drawn, but the largest number won't. In this case, Alex wins.

There's a 1/4 * 12/15 * 11/14 * 1/2 (~.079) chance that the THIRD-LARGEST number will be one of the first four numbers drawn, the largest and second-largest won't be, and that Alex will encounter the largest number before the second-largest number. Alex wins.

There's a 1/4 * 12/15* 11/14* 10/13* 1/3 (~.04) chance that the FOURTH-LARGEST number will be one of the first four numbers drawn, the top three won't be, and that Alex will encounter the largest number before the second- or third-largest. Alex wins.

There's a 1/4 * 12/15 * 11/14 * 10/13 * 9/12 * 1/4 (.023 ) chance that the FIFTH-LARGEST... etc.

The odds of winning add up to something over .33!

Very close, and your analysis is on the right track. But you can still get a little better result.

[Yoruichi-san]

Very close, and your analysis is on the right track. But you can still get a little better result.

Using that approach, calling the number of cards first drawn N and varying that number, I get a maximum probability of ~.35 when N=7.

I tried to do it analytically, but the summations got messier than my college dorm room , so I ended up giving up and doing it numerically.

Not sure if there's an alternate strategy that gives better numbers or how to prove it.

[superprismatic]

and got a maximum when the first six were used as the base set. With this, I got a probability of Alex winning of approximately .388, giving the odds of winning at about .634 to 1, and the expected payoff to Alex of .5521 quid per game. I have no idea if this is optimal and, if it is, I have no idea as to how to prove it.

[bonanova]

Using that approach, calling the number of cards first drawn N and varying that number, I get a maximum probability of ~.35 when N=7.

I tried to do it analytically, but the summations got messier than my college dorm room , so I ended up giving up and doing it numerically.

Not sure if there's an alternate strategy that gives better numbers or how to prove it.

Very close, and heroic attempt at the summation.

and got a maximum when the first six were used as the base set. With this, I got a probability of Alex winning of approximately .388, giving the odds of winning at about .634 to 1, and the expected payoff to Alex of .5521 quid per game. I have no idea if this is optimal and, if it is, I have no idea as to how to prove it.

And you found the optimal winning probability.

What remains is to notice the relative position of the cutoff number in the sample space, the resulting probability, and how these values relate to the most useful transcendental number known to man.

Good job all!

[superprismatic]

Very close, and heroic attempt at the summation.

And you found the optimal winning probability.

What remains is to notice the relative position of the cutoff number in the sample space, the resulting probability, and how these values relate to the most useful transcendental number known to man.

Good job all!

How does one prove optimality here?

[bonanova]

How does one prove optimality here?

First, what is the best heuristic. Of the simplest and most plausible heuristics, one has been found to be the best: Reject the first r candidates, noting the maximum m of their values. Select the next candidate whose value exceeds m.

Second, what is the optimal value of r. To find this value, one writes the probability of success for a general value of r and a given value of n, the number of candidates in the sample space. The expression is a finite series. The value of r that maximizes the probability [the value for which the derivative vanishes] is then found. Letting n grow to large values reveals that the optimal value of r/n approaches 1/e. Further, one finds that the probability for success for finite n is itself always larger then 1/e, tending to that value as n approaches infinity.

The general strategy then, for finite n, is to choose r to be the integer closest to n/e, and pick the next number that exceeds the maximum m of those first r values. You will succeed in picking the largest value of the entire set with a probability of at least 1/e, which is about 36.8% of the time.

For n=16, n/e = 5.89, and the best choice of r is 6. Second best would be 5. The resulting probabilities [that I calculated for 1,000,000 simulations] are respectively .388 and .386, agreeing with your result of .388 for 100,000,000 trials with r=6.

If you want to research this in more detail, Google: the Secretary Problem, or the Game of Googol.