2017/03/05 by Amir Burin, Burin, Amir, Ofer Shayevitz +1 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1703.01672
openalex publication_date 2017/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Alice holds an 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 w.r.t 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 a 1/4. We discuss a connection to the cutoff rate of the BSC with feedback.