Optimal randomized and non-randomized procedures for multinomial selection problems

Multinomial selection problem (MSP) procedures aim to select the best (most probable) alternative based upon a sequence of multinomial observations. The classical formulation of the procedure design problem is to find a decision rule for terminating sampling. The decision rule should minimize the expected number of observations taken while achieving a specified indifference zone requirement on the prior probability of making a correct selection when the alternative configurations are in a particular subset of the possible probability space called the preference zone. We study the constrained version of the design problem in which there is a given maximum number of allowed observations.;Numerous procedures have been proposed over the past 50 years, all of them suboptimal. In this thesis, we find the optimal selection procedure for any given probability configuration via linear programming. The optimal procedure turns out to be necessarily randomized in many cases. We also find the optimal non-randomized procedure via mixed integer programming. We demonstrate the performance of the methodology on a number of examples.;We then reformulate the mathematical programs to make them more efficient to implement, thereby significantly expanding the set of real world problems that can be modeled. We prove that there exists an optimal policy which has at most one randomized decision point and we develop a procedure for finding such a policy. Additionally, we show that the formulations can be extended to replicate existing bounded procedures from the literature, simply by altering the feasible region of the mathematical programs.;Our formulations also allow us to examine situations in which marginal observation costs are not constant. While variable marginal observation costs are realistic, they have not been considered in the literature, largely because the tools required did not exist. We leverage our formulations to develop a new methodology that guarantees the optimal randomized and non-randomized procedures for a broad class of variable observation cost functions. We then analyze procedure performance under a representative set of observation cost functions. We also develop two new tools for examining specific cost-related issues — one for deciding whether or not to purchase experimental supplies in batches and one for determining the effect on total observation cost due to changing probability requirements.;Next, we show that there is very little difference between the relative performances of the optimal randomized and non-randomized procedures, particularly for large budgets. Additionally, we compare existing procedures using the optimal procedure as a benchmark, and produce updated tables for a number of those procedures. For our comparisons, we develop a new set of metrics and employ some traditional statistical measures, such as variance, not typically considered in the literature.;Finally, we examine some fundamental assumptions — normally taken for granted in the literature — regarding the application of MSP procedures. In particular, we show how the choice of the indifference zone parameter affects the size of the preference zone when any alternative configuration is equally possible. We then define the concept of an "acceptable selection" for alternatives in the indifference zone and discuss some Monte Carlo sampling results. Finally, we look at issues regarding the conditional (posterior) probability of correct selection upon procedure termination and its implications on the applicability of MSP procedures in general.