Optimal Selection of the Penultimate Candidate (Mathematics of Decision Making under Uncertainty and Related Topics)

Abstract

A known number n of objects appear one at a time. Let X_{k}, 1leq kleq n, denote the value of the kth object and suppose that X_{1}, X_{2}, X_{n} are independent and identically distributed continuous random variables with a known distribution function. Let L_{k}= max(X_{1}, ldots, X_{k}), and call the kth object a candidate if it is a relative maximum, i.e. X_{k}=L_{k}. We denote by C_{j} the jth to last candidate, jgeq 1. Hence C_{1} is the last candidate and C_{2} the penultimate candidate, etc. The problem we consider here seeks a stopping rule that maximizes the probability of choosing C_{2}. We give the optimal rule and the corresponding success probability. It can be shown that this success probability tends to 0.416002 as narrowinfty. Some comparisons with other related problems are also made.