aez-notes

Choosing the Largest Random Number

As a second task, the king wants the wise man to choose the largest number from among 100, by the same rules, but this time the numbers on the slips are randomly drawn from the numbers from 0 to 1 (random numbers, uniformly distributed). Now what should the wise man's strategy be?

The choice is to either select the current value, or to select the next one that is larger. If the next one is selected then it also needs to be greater than anything that comes after it. Iterating this process gives a complete decision process. The results are given in the table.

Number seen	Minimum to hold
99	0.5
98	0.6898
97	0.7758
96	0.8245
95	0.856
94	0.8778
93	0.894
92	0.9062
91	0.916
90	0.9239
89	0.9305
88	0.936
87	0.9407
86	0.9448
85	0.9484

This comes from comparing the probability that everything subsequent will be smaller, and the probability that there will be at least one larger in the subsequent draws, but that any ones larger will have the largest as the first value encountered. The requirement on the ordering is why there is a factor of \(1/i\) in the sum.

load("distrib")$
load("newton1")$

prob_current_wins(x,r,n) := x ^ (n - r);

prob_next_wins(x, r, n) := sum(
  (1/i) * pdf_binomial(i, n - r, 1 - x),
  i,
  1,
  n - r);

hundred_case(r) := newton(
  prob_current_wins(x, r, 100) - prob_next_wins(x, r, 100),
  x,
  0.9,
  0.001);

fpprintprec : 4;

for r:99 step (-1) thru 85 do {
  print("|", r, "|", float(hundred_case(r)), "|")
  }$

The values are computed numerically because otherwise the solve struggles below 95.