摘要："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 H_2(μ) questions, where H_2(μ) = â^'_x μ(x)log log 1/μ(x). This also generalizes a result by Rivest et al. (1980) 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.
