Can you find the optimum strategy for guessing the highest number?

There seems to be very few rules here.

As it is a thought experiment, I assume that there is no limit on the numbers and that a number could be repeated. I would also assume that the numbers are true random numbers. This means that there is no ‘best’ strategy, any piece of paper will do and the probability of being correct is 1/n.

Did you miss out any important rules that would alter this?

I don’t understand. Is there a parameter for the numbers written on the paper?

There is no limit on the numbers. You can consider them to be completely randomly chosen. There is, however, a way of improving the odds of choosing the largest to be better than 1/n.

I think you are heading towards Cover’s z-strategy. As formulated here, this does not apply. You have to have a non-uniform number distribution for this to have any effect. Random numbers are uniformly distributed over an infinite field, so the z-strategy term is zero and the 1/n probability applies.

If not the z-strategy, I await with interest to read your proposal.

How many lines on the paper? What is the size of the numbers…...and the size of the paper?

From a strictly mathematical point of view, there is no optimal strategy here. You need some extra parameter.

That being said, taking into account human psychology, there might be better solutions than others.

Pick the paper whose writer spent the longest time writing.

@WasCy – Won’t work. What if they were writing down a negative number? That would probably be the lowest number.

Note that the numbers are examined sequentially until one is selected. Suppose that the first number is looked at but is always rejected.

This is a variant of the “Let’s Make A Deal” problem – Door Number One, Number Two , Or Number Three? But in this version, one does not know if the first number is a winner or not.

But you do know that one of the observed numbers is not the winner. So your choice is now one out of two. I say take the third number.

I’d say that if the second number is higher than the first one, I’d choose that number, but if it is lower than the first one, I would always go to the third number, and never stick with number one.

@markferg

Nothing about this is foolproof. There is no surefire way to do it.

@wundayatta has it.

For the general case, you turn up some number of items which give you an expectation of the distribution of the others. Depending on the distribution, you have an expectation of what’s to come. You can estimate whether any turned number exceeds the expectation of the rest.

I’m not sure yet how to quantify that. I think it’s complex.

Like @zenvelo I based this on the “Let’s make a deal” problem.

Initially, each paper has an equal chance of having the highest number. That means that, after you turn over the first paper, there is a two-thirds chance that the highest number is one of the other two. If the second number is lower than the first, then you know the third number has a two-thirds chance of being the highest.

If the second is higher than the first… well, I was going on intuition here. I guess it seems likely that if the higher number is one of the second two, then you stick with the first higher number. This is not quite satisfying, so I know someone else could explain that choice better.

@wundayatta got the strategy right. The calculation of the probability can be done as follows. There is a ⅓ chance the first number is highest. The strategy will never choose it. There is a ⅓ chance that the second number is highest. The strategy will always choose it, because if the second number is highest it will also be larger than the first number. There is a ⅓ chance that the highest number is the third one. In this case the strategy works half the time, which is the chance that the second number is lower than the first. The overall probability is ⅓*0 + ⅓*1 + ⅓*½ = ½. There is a 50% chance of choosing the highest number.

Generalized strategy perhaps: turn half of the papers over. Then accept any answer that is the highest.

Oh wait. This is like the 100 princesses problem!

There is an optimal strategy. Assuming that the chance that each number is the greatest is the same for each peice, this is what you should do:

Uncover the first paper. There is a ⅓ chance that this is the greatest, but their is a two thirds chance that it isn’t, so keep going.

Uncover the second paper. If this number is smaller than the first one, your only hope is to go on to the third and final one. Since you know that the second number isn’t it, there is a fifty-fifty chance that the third number is it, and you will win. If you uncover the second number and find that it is greater than the first, you can choose to either to go on or stay without affecting your odds. Since you can eliminate the first number, there is a fifty-fifty chance that either the second or third number are the greatest. However, if the first number is 2, and the second is 3, I would go on due to the fact that I don’t expect them to put a 2.5 under the three.

By working out the different outcomes on paper, I have figured out that this method gives you a 5/12 chance of winning. Even though this is only a little bit better than the ⅓ chance of winning by random play, it is the optimal way to play.

Besides, its a game on a TV show. They already know that the game isn’t fair.

Can’t be 1/12’s. Must be 1/6’s since there are only 6 possibilities.

123 – Lose
132 – WIN
213 – Win
231 – WIN
312 – Lose
321 – Lose

You win half the time.

@6rant6 Since posting my above reply, I have realized something.

If the second number is greater than the first, there is a ⅓ chance that the first is the smallest and the second is the middle number, a ⅓ chance that the first number is the smallest, and the second the largest, and a ⅓ chance that the first number is the middle number, and the second is the largest. Thus, if the second number is larger than the first, there is a ⅔ chance that the second number is the greatest.

If the second number is smaller than the first, the same idea applies, and the first number has a ⅔ chance of being the greatest, and the third number has a ⅓ chance of being the largest.

Here is the best strategy:
If the second number is greater than the first, stay.
If the second number is less than the first, since you can’t go back, go on.

Since you have a ½ chance of a ⅔ chance and a ½ chance of a ⅓ chance, you have a fifty-fifty chance of winning.

@PhiNotPi Yes, that’s the straegy that @wundayatta posted and I said was correct. I gave you the simpler explanation and the same answer – ½. Your last post said “5/12” was the result with “optimal play”.

I don’t get what it is you think you’re adding now. The text gets pretty unwieldy. Much cleaner approach would be a probability tree.

@6rant6 Well, I found out that the first strategy wasn’t actually optimal. And yes, I see now that your reply did show the exact same thing. I just did thought that you were trying to show that my answer of 5/12 was wrong (which it is) by testing out my strategy.

I never did get around to talking about what happens as the number of numbers increases. What changes is the number of cards initially examined and discarded. For example, in the case of 5 numbers, the best strategy is to look at the first two numbers and then keep looking at new ones until either one is found that is larger than all previous ones or the last one is reached. The probability, I believe, was about 43%. I still have not gotten around to writing a computer program, but when I do, I will look to see if there is a pattern to how many numbers are initially discarded and to the probability of choosing the largest.

I wrote the program (let me know if you want the code).

It’s exhaustive brute force which means that none of this is probabilistic. It also means that my little computer can’t progress above 8 items very quickly with all the combinatorial growth.

For 8 items, best strategy is 3 (40.98%)

For 7 items, best strategy is 2 (41.42%)

For 6 items, best strategy is 2 (42.77%)

For 5 items, best strategy is 2 (43.33%)

For 4 items, best strategy is 1 (45.83%)

For 3 items, best strategy is 1 (50%)

I’m surprised at how good the strategy is even for eight items. This looks like a natural bar bet. I imagine you could get 3 to 1 odds every time with eight items. One suggestion – don’t let anyone dictate the order you turn them.

I’m sure a generalized answer can be obtained using real math. Just above me. If anyone wants to try it, you should be able to check your answers against these.

Thanks for the offer. I am still going to write my own program. It makes for a good exercise. I will check my answers against yours.

It would indeed make a good bar bet.

I wonder if you could improve performance via two terms: one, for the number of cards turned perforce and two, a number of standard deviations above the prior maximum.

Example: I have 9 cards. I’ve turned 3 and the sample deviation is 2 and the maximum 9. Would I get better results looking for something that exceeds 9 or waiting for something that exceeds 9+k*2 (where 0<k<1)?

I suppose you could actually compute a z-score and use that to determine whether a number as it is turned can be expected to exceed the maximum of the remaining cards. If considered that way, it’s clear that the threshold one should use ought to decrease with every new card (assuming k > 0).

My intuition is that choosing the current maximum works best. It is all just a matter of combinatoriics. You could start with turning over just 1 card. At each stage, if the current card is not maximal then obviously it is best to choose another. If the current card is maximal, then it is a matter of determining the number of ways that the current card is the overall maximum versus the number of ways that one of the unturned cards is the overall maximum. The first number will initially be less than the second. The first number keeps increasing with the number of cards turned over and the second number keeps decreasing. The point at which the first number exceeds the second is the number of cards that should be turned over initially.

I finally wrote a computer program and it looks like both the proportion of cards to choose initially and the maximum probability are both 1/e, where e is Euler’s constant.

@LostInParadise How far did you go? Can you post results past 8?

I was able to get up to 100000. I did not use combinatorics. I calculated the probability similarly to how I showed above for n=3. I just looped for each n over the number of cards chosen initially and chose the maximum.

Here are some sample values:
Number: Chosen: Probability
10 3 0.39869
100 37 0.37104
1000 368 0.36820
10000 3679 0.36791
100000 36788 0.36788

1/e starts out as .3678794, in agreement to 4 places and pretty close on the fifth, which has to be more than a coincidence.

This is the code I used. in C#. I know it can be made much more efficient, but I was in a hurry to get results.

class clsHighCardProbTester
{
public double maxProb = 0;
public int choose = 0;

private double probForNstartingWithK(double n, double k)
{
double prob = 0;
for (double j = k; j <= n – 1; j++)
{
prob += k / j;
}
return prob;
}

public void HighCardStrategy(int n)
{
double prob = 0;

maxProb = 0;
choose = 0;

for (int i = 1; i < n – 1; i++)
{
prob = probForNstartingWithK(n,i);

if (prob > maxProb)
{
maxProb = prob;
choose = i;
}
else if (maxProb > 0)
{
maxProb /= n;
return;
}
}
}

} // clsHighCardProbTester

} // HighestCard

Mind boggling that it goes to 1/e… not that e is involved but that it’s so simple.

Also remarkable is that if you can get those 3 to 1 odds, even a million cards makes a good bar bet.

@6rant6 , Based on @roundsquare‘s comment, I did a search for the 100 princesses problem. It is also known as the secretary problem. Wikipedia has an article on it.