Partitioning a Sample Using Binary-Type Questions with Ternary Feedback

The problem is to find the largest observation (or the q largest observations) in a random sample of size n by asking binary-type questions of people (or items) in the sample. At each stage of the search, a threshold is calculated and a binary-type question is posed to each member of the sample. This question is of the form “Is your observation greater than the threshold?” The threshold is determined from answers given to the previous questions, and no exact data is ever collected, i.e., no member is asked to explicitly provide his observation. Arrow, Pesotchinsky, and Sobel (APS) calculated the optimal threshold sequence for two different objectives: i) minimize the average number of questions required for a solution, and ii) maximize the probability of solving the problem in, at most, r questions. APS have assumed that the number of respondents in the affirmative at each stage of the search is exactly known (this is the case of “full feedback”). There exist applications (e.g., multiuser communications) where the number of affirmative answers is only known to be one member of the set {0,1, more than 1} (“ternary feedback”). For these applications, we calculate exactly the optimal thresholds, in the sense of maximizing the probability of getting precisely one affirmative answer to the next binary question. We find that, with ternary feedback, the expected number of questions needed to terminate the search is ~2.445 (for large n). Using the same objective function, APS calculated 2.44144 for full feedback. Application of the threshold-calculation procedure is demonstrated in resolution of packet collisions over multiuser communication channel. At any instant, the procedure maximizes the probability of successful packet transmission during the next time slot.