Optimal solution to the multinomial selection problem for two alternatives
Timur Tankayev, Craig A. Tovey · Sequential Analysis · 2017
The multinomial selection problem is to find a stopping policy for repeated independent trials, each of which reports a winner among competing alternatives that has low expected cost and high probability of correct selection (PCS) of the best alternative. In 1959, Bechhofer, Elmaghraby, and Morse formulated the problem as minimizing the worst-case expected number of trials, subject to a lower bound on PCS and upper bound on the maximum number of trials, over all probability vectors outside an indifference zone. For the case of two alternatives, we prove that if one employs a particular probability vector known as the slippage configuration, then a linear program always finds an optimal stopping policy.