Reducing Guesswork via an Unreliable Oracle

摘要

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