Repeating the problem:
100 uniformly random numbers from [0,1] are written on slips of paper and mixed.
We draw a slip at a time and must decide whether that's the largest number or not.
If we decide on a number and it is indeed the largest we win, else we discard the slip and draw another one.
If we fail to find the largest number we lose.
What strategy should we adopt to maximize the probability of getting the largest number?
The previous post is the scaffolding. Some integrals were wrong, but the basic idea that by not choosing the first slip and continuing the game the distribution of the remaining numbers is not uniform anymore stands.
There is an exact solution for the problem above given any number n; finding it is not that easy though.
For n=2 we can see the problem easily enough:
The corresponding probabilities are:
For n=3 we cut the cube in four parts:
Piece 3 (below) fits the hole in piece 4 (further below):
And it's in this last piece that we continue the game in case we discarded the first slip and that slip was not the maximum.
The first chart then can become one of these cases:
Solving that (using Mathematica's Integrate defined on a region), and considering the case where k3>k2 (k1=0), we find that we need to maximize 1/3 - k2^3/2 + k3/2 + k2 k3 - (k2 k3^2)/2 - k3^3/2.
I use k3 as the first choice with n=3, k2 is used for both the first choice with n=2, the second choice with n=3. ..., in order to see clearly how the choices for these rounds change with n.
Once we defined this solution (and checked with the simulations), I went to generalize the equation, by looking at how each component arose from the diagonals of the probability matrices.
Automating the generation of the equations for the probabilities of winning, we find the values of k[j] that maximize these probabilities:
And see that, as n increases, our choices for the lower rounds must change; more holes are appearing the lower levels the more we decline the slip.
If kn=1-1/n is the basic heuristic, we can see how these optimal choices perform better:
Below we see how the optimal ks get much closer to the first choice (which is rightmost in the chart). With n increasing, the curve (starting at the 1-1/n) goes up and flattens.
Given that the relationship is linear on Log[n]:
We might have differences between the ks chosen for low ns.
The performance of each heuristic was tested with simulations.
Mathematica notebook (whole) below:
Download RandomRangedMaxSolutions
The charts made it quite large when creating the PDF, so there are 4 pieces of files that correspond to the notebbok above.
PDFs:
Download RandomRangedMaxNewExplore1PDF
Download RandomRangedMaxNewExplore2PDF
Download RandomRangedMaxNewSimulsPDF
Download RandomRangedMaxSolutionsPDF
A fascinating problem.
Comments