2010/02/26 by John Gill, John T. Gill III, Gill, John T. +2
Computer Science · Mathematics · #Algorithms and Data Compression #Discrete Mathematics (cs.DM) #E.4 #FOS: Computer and information sciences #H.1.1 #Information Theory (cs.IT) #Natural Language Processing Techniques #Video Analysis and Summarization #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1002.4907
2 pages, 2 figures, submitted to IEEE Transactions on Information Theory
arxiv created 2010/02/26 · openalex publication_date 2010/02/26 · arxiv updated 2010/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Huffman coding is often presented as the optimal solution to Twenty Questions. However, a caveat is that Twenty Questions games always end with a reply of "Yes," whereas Huffman codewords need not obey this constraint. We bring resolution to this issue, and prove that the average number of questions still lies between H(X) and H(X)+1.