Twenty (simple) questions
Twenty (simple) questions
复制标题
二十个（简单）问题
DOI：
10.1145/3055399.3055422
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Moran
中科院分区：
文献类型：
--
作者：
Y. Dagan;Yuval Filmus;Ariel Gabizon;S. Moran
香农熵函数的一个基本组合解释是通过“20个问题”游戏。这个合作博弈是由两个参与者Alice和Bob来玩的：Alice在数字{1，.，n}上选择一个分布，并向Bob宣布。然后，她根据“是”选择一个数字x，鲍勃试图用尽可能少的“是”/“否”查询来确定x。“20个问题”游戏的最优策略是由代表x的霍夫曼代码给出的：鲍勃的问题一点一点地揭示了代表x的码字。该策略平均使用少于H（n）+1个问题找到x。然而，鲍勃提出的问题可能是任意的。在本文中，我们调查了以下问题：* 是否有限制的问题集，匹配的性能霍夫曼码，无论是完全或近似？我们的第一个主要结果表明，对于每一个分布，鲍勃有一个策略，只使用形式为“x < c？“和“x = c？“，并且平均使用最多H（k）+1个问题来发现x，在这个意义上匹配霍夫曼码的性能。我们还给出了一个自然的O（rn 1/r）问题集，其性能至多为H（n）+r，并证明了需要Ω（rn 1/r）问题才能实现这样的保证。我们的第二个主要结果给出了一个1.25n+o（n）个问题的集合Q，使得对于每个分布，Bob可以只使用Q中的问题来实现最优策略。我们还证明了对于无穷多个n，需要1. 25 n-o（n）个问题。如果我们允许r在最优策略上有一个小的松弛，那么大约（rn）Θ（1/r）个问题是必要和充分的。
A basic combinatorial interpretation of Shannon's entropy function is via the "20 questions" game. This cooperative game is played by two players, Alice and Bob: Alice picks a distribution Π over the numbers {1,…,n}, and announces it to Bob. She then chooses a number x according to Π, and Bob attempts to identify x using as few Yes/No queries as possible, on average. An optimal strategy for the "20 questions" game is given by a Huffman code for Π: Bob's questions reveal the codeword for x bit by bit. This strategy finds x using fewer than H(Π)+1 questions on average. However, the questions asked by Bob could be arbitrary. In this paper, we investigate the following question: *Are there restricted sets of questions that match the performance of Huffman codes, either exactly or approximately? Our first main result shows that for every distribution Π, Bob has a strategy that uses only questions of the form "x < c?" and "x = c?", and uncovers x using at most H(Π)+1 questions on average, matching the performance of Huffman codes in this sense. We also give a natural set of O(rn1/r) questions that achieve a performance of at most H(Π)+r, and show that Ωrn1/r) questions are required to achieve such a guarantee. Our second main result gives a set Q of 1.25n+o(n) questions such that for every distribution Π, Bob can implement an optimal strategy for Π using only questions from Q. We also show that 1.25n-o(n) questions are needed, for infinitely many n. If we allow a small slack of r over the optimal strategy, then roughly (rn)Θ(1/r) questions are necessary and sufficient.
影响因子：
2.5
作者：
Gronlund, Allan;Pettie, Seth
通讯作者：
Pettie, Seth