Choosing the Largest Random Number

The very first number could be chosen if it were sufficiently close to $1,$ e.g., $0.999,$ because the chance of getting a larger number later on is only $1-0.999^{99}\approx 0.1.$

As in the Marriage Problem, we have to choose between a candidate at hand and the chance that a later number will be larger and that we will choose it.

Let's work backwards. If we have not made our mind before the last draw then we choose that number and either win or lose.

On the step before the last, if the number is the largest so far and greater than $\displaystyle \frac{1}{2},$ choose it. Else, move on.

At the third draw from the end (if we got that far), assuming that the value on the slip is $x,$ the probabilities of having $0,$ $1,$ or $2$ numbers larger than $x$ are $x^2,$ $2x(1-x),$ and $(1-x)^2,$ respectively. If we choose the next number larger than $x$, the probability of winning later $\displaystyle 2x(1-x)+\frac{1}{2}(1-x)^2,$ because, if there are $0$ later, we cannot win by going on; if $1$, we are sure to win; and, if $2$ are larger than $x,$ the chance is only $\displaystyle \frac{1}{2}$ that we choose the larger of the two. If I am indifferent to a number at some draw, I would not be indifferent to it at a later draw; instead, I would want to choose it because I do not have as many opportunities to improve my holdings as I did earlier. Consequently, when two numbers larger than the indifference number $x$ are present later in the sequences, we can be sure I would choose the first one. It has only a $50-50$ chance of being the larger of the two. Thus, in computing what would happen if we decline to choose an indifference number that has been drawn we can be sure, in general, that the best strategy chooses the next drawing whose value exceeds the indifference number in hand.

Thus the point is to determine the value of $x$ to which we are indifferent. For the third position from the end, it is the value that satisfies

$x^2=2x(1-x)+\frac{1}{2}(1-x)^2.$

Here $x^2$ is the chance of winning the number $x,$ and the right-hand side gives the chance of winning if we pass the $x$ at hand. The indifference number works out to be

$\displaystyle x=\frac{1+\sqrt{6}}{5}\approx 0.6899.$

So we choose a candidate third from the last if its value exceeds $0.6899.$

More generally, if there are $r$ draws to go and we have a candidate in hand, we choose the draw if it exceeds the indifference value $x$ computed from

(1)

$\displaystyle x^r=\sum_{k=1}^r\frac{1}{k}{r\choose k}x^{r-k}(1-x)^k.$

We can solve this equation numerically using binominal tables or other devices to find values of $x$ for modest values of $r.$ The table of the indifference numbers below shows some of these:

$\displaystyle \begin{array}{ccc} \text{Number left} & \text{Solution of (1)} & \displaystyle \frac{r}{r+0.8843}\\ \_\_\_\_\_\_ & \_\_\_\_\_\_ & \_\_\_\_\_\_\\ 1&.5000&0.5542\\ 2&0.6899&07132\\ 3&0.7758&0.7886\\ 4&0.8246&0.8326\\ 5&0.8559&0.8614\\ 6&0.8778&0.8818\\ 7&0.8939&0.8969\\ 8&0.9063&0.9086\\ 9&0.9160&0.9180\\ 10&0.9240&0.9256 \end{array}$

$\displaystyle \frac{r}{r+0.8843}$ is an approximate formula derived by Mosteller (see the references below).

Since this game provides more information than the Marriage Problem, the probabilities of winning are larger. For two slips, the player chooses the first if it's greater than $\displaystyle \frac{1}{2},$ otherwise he goes on. The chance of winning is $\displaystyle \frac{3}{4}.$ However, as the number of slips grows, the probability of winning falls monotonically. The limit is about $0.580.$

We draw a slip with $x$ and have to decide whether to select it or not. The probability that we might to do better than that in the remaining two draws is $\displaystyle 2x(1-x)+\frac{1}{2}(1-x)^2$ because of the remaing two numbers $1$ is greater than $x$ with the probability $2x(1-x)$ while both are greater than $x$ with the probability of $(1-x)^2$ but we may choose a wrong one, so the probability of doing better than $x$ in this case is only $\displaystyle\frac{1}{2}(1-x)^2.$ Thus the decision at the beginning depends on whether or not

$\displaystyle x^2\gt 2x(1-x)+\frac{1}{2}(1-x)^2.$

Simplifying we get $5x^2-2x-1\gt 0$ such that to be selected $x$ should satisfy $\displaystyle x\gt\frac{1+\sqrt{6}}{5}\approx 0.6899.$

If that's not the case (we ignore the case of equality where we can choose either way), i.e., if $x\lt 0.6899,$ and the next number is less than $x$ we ignore it. If it's greater than both $x$ and $\displaystyle \frac{1}{2},$ we pick it.

The problem has been discussed in at least books:

1. R. Honsberger, Mathematical Plums, MAA (1979)
2. F. Mosteller, Fifty Challenging Problems in Probability with Solutions, Dover (1987)

Marcos Carreira placed his invesigation on the web.