Selecting the Maximum of a Sequence with Imperfect Information

Abstract

N independent and identically distributed random variables are sampled sequentially from a known continuous distribution. The information obtained is whether the sampled random variable is greater or less than some level specified by the sampler. The optimal strategy for maximizing the probability of selecting the largest member of the sequence is obtained and tabulated for N ≤ 25. When following the optimal strategy, the expected value of the number sampled is shown to equal N times the probability that the maximum is attained. This remains true for a reduced set of decision levels, provided the reduced set of levels are optimal.