TY - JOUR

T1 - Partitioning a Sample Using Binary-Type Questions with Ternary Feedback

AU - Cohen, Amit

AU - Kam, Moshe

AU - Conn, Robert

N1 - Funding Information:
One possible objective is to design the questions such that the expected length of the search (= number of questions needed to find the holder of the largest observation) is minimized. Another Manuscript received February 13, 1994; revised November 18, 1994. This work was supported by the National Science Foundation under Grant ECS 9057587. The authors are with the Department of Electrical and Computer Engineer-ing, Data Fusion Laboratory, Drexel University, Philadelphia, PA 19104 USA. IEEE Log Number 9413265.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

PY - 1995/10

Y1 - 1995/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029393116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029393116&partnerID=8YFLogxK

U2 - 10.1109/21.464441

DO - 10.1109/21.464441

M3 - Article

AN - SCOPUS:0029393116

SN - 0018-9472

VL - 25

SP - 1405

EP - 1408

JO - IEEE Transactions on Systems, Man and Cybernetics

JF - IEEE Transactions on Systems, Man and Cybernetics

IS - 10

ER -