Reducing Guesswork via an Unreliable Oracle
Amir Burin, Ofer Shayevitz · IEEE Transactions on Information Theory · 2018
Alice holds a random variable X, and Bob is trying to guess its value by asking questions of the form “is X = x?”. Alice answers truthfully and the game terminates once Bob guesses correctly. Before the game begins, Bob is allowed to reach out to an oracle, Carole, and ask her any yes/no question, i.e., a question of the form “is X ∈ A?”. Carole is known to lie with a given probability p. What should Bob ask Carole if he would like to minimize his expected guessing time? When Carole is always truthful (p = 0), it is not difficult to check that Bob should order the symbol probabilities in descending order and ask Carole whether the index of X with respect to this order is even or odd. We show that this strategy is almost optimal for any lying probability p, up to a small additive constant upper bounded by 1/4. We discuss a connection to the cutoff rate of the BSC with feedback.