# Finding optimal thresholds for “guess if number is highest” game

Consider the following game: five numbers are chosen randomly in the interval [0..1] with uniform distribution. The player is shown each number in turn and asked if it is the highest. The game proceeds until the player either answers incorrectly (false positive and false negative are both losing outcomes) or correctly guesses that the present number is the highest (correctly answering that the current number is the highest is an instant win, since the player could presumably answer correctly that one of the others is).

If the player's goal is to maximize the probability of answering correctly whether each given number is the highest, the player should answer "yes" when shown a number which is larger than any seen thus far, and which is larger than the 1-1/2^(1/n), where n is the number of unseen numbers remaining (e.g. if the third number is sqrt(2), and the first two numbers were smaller than that, there's a 50% probability that both of the remaining numbers are less than that, so either "yes" and "no" would have a 50% probability of being correct; if the value is higher, then "yes" will more likely be correct; if it's lower, then "no" will be most likely.

If the player's goal is to maximize the probability of winning, however, the calculations would seem to get more complicated. When asked whether the fourth number is highest, the player should answer "Yes" if it's greater than 50%, and greater than all numbers seen thus far. If the player answers correctly, the player wins (a player who correctly states that the fourth number is not the biggest will have no trouble answering that the fifth is). When answering whether the "third" number is the biggest, however, the reward for correctly identifying that it is the biggest (i.e. an instant win) is larger than the reward for identifying that it is not (since the player will still risk a loss on the next number).

Is there any nice way to determine the threshold for each number where the player should announce that it's the biggest (assuming it's larger than any values seen thus far)? Attempting to partition a 3-dimensional space to decide what to do on the third guess seems awkward but not impossible, but going beyond that to figuring out the optimal strategy on the second guess would seem unworkable absent some simplification I'm not seeing.

-
Why is the probability of winning any different to maximising the probability of answering correctly whether each given number is the highest? –  Henry Feb 23 '14 at 22:44
And why do you say $1-1/2^n$ rather than $1/2^{1/n}$? If the first was $0.23$, the second was $0.17$, and the third $0.74$, I would guess that the third was highest and my probability of being correct would be more than $0.5$ –  Henry Feb 23 '14 at 22:48
@Henry: Sorry, I meant nth root, but didn't know how to type it and messed up when trying to produce something I could type. –  supercat Feb 23 '14 at 22:52
@Henry: With regard to the probability of guessing right vs. winning, suppose the third number is 0.7 and the first two are less (it doesn't matter by how much). If one guesses that's the biggest, one will have only a 49% chance of winning; but if one guesses that it isn't one will have a 51% chance of being right, but that will be subdivided into a 46.5 percentage-point chance of being right and winning, and a 3.5 percentage-point chance of being right but guessing wrong on the fourth number and losing anyway. Thus, if the third number is 0.7, one should guess it's biggest. –  supercat Feb 23 '14 at 22:55
OK - I like your $0.7$ example –  Henry Feb 24 '14 at 0:41

I get the same threshold numbers as Robert Israel but, I think, by a different way of thinking about things.

Generalize the problem from $5$ numbers at the beginning to $n+1$ and ask what's the threshold value, $\tau_n$, above which you should accept the first card, below which you should pass on it, and at which you are indifferent -- i.e., at which you figure the probability it's the highest value is equal to the probability that you'll actually pick the highest value when it's offered. (Note, I'm using $\tau$ for the threshold value, to distinguish it from Robert Israel's $t$'s, which use a countdown index starting from $5$.)

The key idea is that if your best course is to accept any number greater than the threshold value, that means if you pass on the threshold value (and survive), then you'll accept the next higher value as soon as it appears.

Now if the first number is $x$, the probability that it is larger than the remaining $n$ values is $x^n$. On the other hand, the probability that the largest number is among the next $n$ numbers but appears before any other number larger than $x$ is

$${n\choose 1}x^{n-1}(1-x)+{1\over2}{n\choose2}x^{n-2}(1-x)^2+{1\over3}{n\choose3}x^{n-3}(1-x)^3+\cdots+{1\over n}{n\choose n}(1-x)^n$$

To see why, consider a generic term, ${1\over k}{n\choose k}x^{n-k}(1-x)^k$. This corresponds to the possibility that of the next $n$ numbers, $k$ are greater than $x$ and $n-k$ are less than $x$. There are $n\choose k$ ways to arrange such numbers, and among these arrangements, the largest of the $k$ "large" numbers occurs first with probability $1/k$.

It stands to reason that the displayed expression is a decreasing function of $x$, whereas $x^n$ is clearly increasing on $[0,1]$. Consequently, $\tau_n$ is the unique root in $[0,1]$ of the equation

$$x^n=nx^{n-1}(1-x)+{1\over2}{n\choose2}x^{n-2}(1-x)^2+{1\over3}{n\choose3}x^{n-3}(1-x)^3+\cdots+{1\over n}{n\choose n}(1-x)^n$$

Plugging in the first few values $n=1,2,3,4,5$, we get equations that are convenient to write as follows:

\begin{align} 2x&=1\\ 5x^2&=2x+1\\ 17x^3&=6x^2+3x+2\\ 74x^4&=24x^3+12x^2+8x+6\\ 394x^5&=120x^4+60x^3+40x^2+30x+24\\ \end{align}

Note, the fourth of these agrees with Robert Israel's $37z^4-12z^3-6z^2-4z-3$. The roots of the cubic and quadratic also agree with what he calls $t_2$ and $t_3$. I've written things here to suggest the general pattern

$${a(n)\over n!}x^n=x^{n-1}+{1\over2}x^{n-2}+\cdots+{1\over n-1}x+{1\over n}$$

The sequence of $a(n)$'s, $2,5,17,74,394,\ldots$, appears to be A000774 in the OEIS. I would imagine there is some fairly simple inductive proof of this general pattern. If I come up with one, I'll edit it in, but I'd be happy if someone would do the work for me.

-
I like your reasoning; it took a moment to realize the first $n$ in the first probability formula is, for purposes of the pattern, simply ${n\choose1}$, but other people may think $n$ is clearer. There is an elegance to Mr. Israel's approach of delaying losses from a false negative, but as you note, there is also some considerable benefit to being able to say that if you're "seriously considering" a number you're certain to say yes to the next larger number that comes along, thus reducing the question to one of whether the first larger number is the largest. –  supercat Feb 25 '14 at 14:04
@supercat, I changed the $n$ to $n\choose1$. –  Barry Cipra Feb 25 '14 at 14:17
The polynomials look nice, though of course solving general polynomials is non-trivial. Would the solutions be easier if the polynomial for each stage was written in terms of the previous stage's threshold solution, or would that not really help since it would yield a "simpler" polynomial which still had the same order? What would you see as the best way to calculate things algorithmically for larger N so as to see how they converge on a limit (I vaguely recall that even for infinite N, there's a threshold that gives a moderate win probability, but I forget the details). –  supercat Feb 27 '14 at 14:04
@supercat, it stands to reason that the threshold numbers are strictly increasing, $t_1\lt t_2\lt t_3\lt\cdots$, and tend to $1$ as $n$ tends to infinity. All this should really be proved, though. –  Barry Cipra Feb 27 '14 at 14:24
Were it not for the fact that one can win by guessing "no" when there are multiple numbers over the threshold, the optimal strategy would be to use a threshold, N guesses from the end, of 1-1/N. The probability P0(N) that there will be zero numbers larger than that threshold is (1-1/N)^N. The probability P1(N) that there will be exactly one such number will be P1(N-1)*(1-1/N)+P0(N-1)*(1-(1-1/N)). As N gets large, the latter term approaches zero. I think the winning probability with that sub-optimal strategy would asymptotically approach $e^{-1}$. –  supercat Feb 27 '14 at 18:05

(EDITED)

Let $X_1, \ldots, X_5$ be the five numbers. Let $M_j = \max(X_1, \ldots, X_j)$. I'll frame the question slightly differently: the player gets to choose or reject each number in turn, and wins if she chooses $M_5$ (but in my formulation the game does not end immediately with a false negative).

A strategy corresponds to a $5$-tuple $T = [t_1, t_2, t_3, t_4, t_5]$ where the player chooses number $j$ if no previous number has been chosen and $X_j = M_j \ge t_j$.
In dynamic-programming fashion, we solve this from back to front.
The optimal $t_5$ is $0$, i.e. if you get to round $5$ you may as well choose $X_5$. The win probability on round $5$ (before $X_5$ is revealed), given $X_1,\ldots, X_4$ and the fact that those were rejected, is $P_5(M_4) = 1 - M_4$.

Now consider the situation on round $4$. If $X_4 < M_3$, the player will reject $X_4$ and have win probability $1 - M_3$. If $X_4 > M_3$, rejecting $X_4$ will yield win probability $1 - X_4$, while accepting it will yield win probability $X_4$. Thus $t_4 = 1/2$.
Thus the win probability before $X_4$ is revealed is $$P_4(M_3) = \cases{M_3 (1-M_3) + \int_{M_3}^{1/2} (1 - x)\; dx + \int_{1/2}^1 x\; dx =\dfrac{3}{4} - \dfrac{M_3^2}{2} & if M_3 \le 1/2\cr M_3 (1 - M_3) + \int_{M_3}^1 x\; dx = \dfrac{1}{2} + M_3 - \dfrac{3}{2} M_3^2 & otherwise\cr}$$

Next for the situation on round 3. If $X_3 < M_2$, the player will reject $X_3$ and have win probability $P_4(M_2)$. If $X_3 > M_2$, rejecting $X_3$ yields win probability $P_4(X_3)$, accepting it yields win probability $X_3^2$. We get $t_3 = (1 + \sqrt{6})/5 \approx 0.6898979486$. The win probability before $X_3$ is revealed is $$P_3(M_2) = \cases{M_2 P_4(M_2) + \int_{M_2}^{t_3} P_4(x)\; dx + \int_{t_3}^1 x^2\; dx = \dfrac{2 \sqrt{6}}{25} + \dfrac{293}{600} - \dfrac{M_2^3}{3}& if M_2 \le 1/2\cr \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \dfrac{2 \sqrt{6}}{25} + \dfrac{67}{150} + \dfrac{M_2^2}{2} - M_2^3 & if 1/2 < M_2 \le t_3\cr M_2 P_4(M_2) + \int_{M_2}^1 x^2\; dx = \dfrac{1}{3} + \dfrac{M_2}{2} + M_2^2 - \dfrac{11}{6} M_2^3 & if M_2 > t_3\cr}$$

Next for the situation on round 2. If $X_2 < M_1 = X_1$, the player will reject $X_2$ and have win probability $P_3(M_1)$. If $X_2 > M_1$, rejecting $X_2$ yields win probability $P_3(X_2)$, accepting it yields win probability $X_2^3$. We get $$t_2 = {\dfrac { \left( 348+51\,\sqrt {43} \right) ^{2/3}+2\,( 348+51\,\sqrt {43})^{1/3}+21}{17\,)348+51\,\sqrt {43})^{1/3}}} \approx 0.7758450684$$ and the win probability before $X_2$ is revealed is $$P_2(M_1) = \cases{ M_1 P_3(M_1) + \int_{M_1}^{t_2} P_3(x)\; dx + \int_{t_2}^1 x^3\; dx & if M_1 \le t_2\cr M_1 P_3(M_1) + \int_{M_1}^1 x^3\; dx & if M_1 > t_2\cr}$$ (the details getting rather messy)

Finally for round 1. Rejecting $X_1$ yields win probability $P_2(X_1)$, accepting it yields win probability $X_1^4$. We find that $t_1$ is a root of the polynomial $37 z^4-12 z^3-6 z^2-4 z-3$, approximately $0.824589583005756$. The win probability before $X_1$ is revealed is $$P_1 = \int_0^{t_1} P_2(x)\; dx + \int_{t_1}^1 x^4\; dx \approx 0.639194247576567$$

-
If I understand you correctly, you're essentially figuring that the numbers that haven't been seen haven't been chosen yet, so a player who says "no" is basically betting that some bigger number is going to appear, and doesn't lose until all later numbers are chosen and none happens to be bigger. I implemented this game as a programming assignment back in 1987 and figured out the strategy to maximize the "guess correctly" probability, but decades on realized that that strategy won't maximize the probability of winning. From the standpoint of someone playing the game... –  supercat Feb 23 '14 at 23:00
...it's nice to only be asked to make decisions in cases where it will matter, but from a probability standpoint I can see that orthogonal handling of cases without regard for whether a player's action will "matter" may simplify things. –  supercat Feb 23 '14 at 23:03
Using the fifth root of 1/2 as a basis for the first guess would suggest a threshold of 0.87; the optimal threshold of 0.825 is about 46% more likely to yield a "yes". In a way I'm glad to see that my failure to see a particularly way to calculate the thresholds is that there wasn't one. Integrals aren't exactly pretty, but because the thresholds are ranked, many portions of them look like they will evaluate to constants, so within the ranges of interest each integral should become a polynomial. –  supercat Feb 27 '14 at 14:00