Simple Binary Identification Problems

Abstract

Given some unknown object belonging to a known finite set of n possibilities, it is required to determine its identity by successive comparisons with each of the possibilities. Associating with each of these possibilities a testing cost and a probability that it is identical to the unknown object, we would like to obtain such a testing procedure which has minimum expected testing cost. Intuitively, it would appear that one should proceed by always applying the remaining test with least cost/probability ratio. We show that this technique does not necessarily yield the optimal procedure and present an algorithm which determines the optimal testing sequence in a number of steps proportional to n · log2 n.