# The entropy of lies: playing twenty questions with a liar

arXiv: https://arxiv.org/abs/1811.02177 · HTML: https://mlsanity.com/paper/1811.02177/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2018.

## Built on by (most cited first, 2 of 2)

- [Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time](https://mlsanity.com/paper/2605.08290/) (2026)
- [Sequence prediction under a lying oracle](https://mlsanity.com/paper/2608.14102/) (2026)

## Abstract (arXiv)

`Twenty questions' is a guessing game played by two players: Bob thinks of an integer between 1 and n, and Alice's goal is to recover it using a minimal number of Yes/No questions. Shannon's entropy has a natural interpretation in this context. It characterizes the average number of questions used by an optimal strategy in the distributional variant of the game: let μ be a distribution over [n], then the average number of questions used by an optimal strategy that recovers x~ μ is between H(μ) and H(μ)+1. We consider an extension of this game where at most k questions can be answered falsely. We extend the classical result by showing that an optimal strategy uses roughly H(μ) + k H2(μ) questions, where H2(μ) = sumx μ(x)loglogfrac1μ(x). This also generalizes a result by Rivest et al. for the uniform distribution. Moreover, we design near optimal strategies that only use comparison queries of the form `x ≤ c?' for c∈[n]. The usage of comparison queries lends itself naturally to the context of sorting, where we derive sorting algorithms in the presence of adversarial noise.