Q#5: Subject name(information theory and coding)

Huffman.

Consider a set of n objects. Let X_i = 1 or 0 accordingly as the i-th object is good or defective.

Let X₁, X₂, . . . ,X_n be independent with Pr {X_i = 1} = p_i; and p₁ > p₂ > . . . > p_n > 1/2. We are asked to determine the set of all defective objects. Any yes-no question you can think of is admissible.

(a) Give a good lower bound on the minimum average number of questions required.

(b) If the longest sequence of questions is required by natures answers to our questions, what (in words) is the last question we should ask? And what two sets are we distinguishing with this question? Assume a compact (minimum average length) sequence of questions.

(c) Give an upper bound (within 1 question) on the minimum average number of questions required.