文章基本信息

标题：The Entropy of Lies: Playing Twenty Questions with a Liar
本地全文：下载
作者：Yuval Dagan ; Yuval Filmus ; Daniel Kane 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：1:1-1:16
DOI：10.4230/LIPIcs.ITCS.2021.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要："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.
关键词：entropy; twenty questions; algorithms; sorting