Three numbers are drawn one at a time, independently and uniformly from [0,1]. You see each value and must accept or reject it immediately with no recall, keeping whatever you accept. What is the largest achievable expected value, and what thresholds achieve it?

Three numbers are drawn one at a time, independently and uniformly from [0,1]. You see each value and must accept or reject it immediately with no recall, keeping whatever you accept. What is the largest achievable expected value, and what thresholds achieve it?

Approach: Work backwards from the final draw. At each stage the continuation value is the expected value of playing the remaining problem optimally, and you accept exactly when the observed draw beats it.

89/128. Backward induction gives the thresholds. With one draw left the expected value is 1/2. At the second draw the continuation value is 1/2, so the threshold policy accepts x > 1/2 and E_2 = (1/2)E[x | x > 1/2] + (1/2)(1/2) = 3/8 + 1/4 = 5/8. At the first draw the continuation value is 5/8, so E_3 = P(x > 5/8)E[x | x > 5/8] + P(x <= 5/8)(5/8) = (3/8)(13/16) + (5/8)(5/8) = 39/128 + 50/128 = 89/128 = 0.6953. The thresholds are 5/8, then 1/2, then accept whatever arrives, and each threshold equals the continuation value of the problem that remains.

Follow-up: What does the first threshold converge to as the number of draws grows?

Key concepts: continuation value, threshold policy, backward induction, expected value.