En grundläggande kombinatorisk tolkning av Shannons entropifunktion sker via spelet "20 frågor". Detta kooperativa spel spelas av två spelare, Alice och Bob: Alice väljer en distribution π över siffrorna {1,..., n}, och meddelar det till Bob. Hon väljer sedan ett nummer x enligt π, och Bob försöker identifiera x med så få Ja / Inga frågor som möjligt, i genomsnitt. En optimal strategi för "20 frågor" spelet ges av en Hu man kod för π : Bobs frågor avslöjar kodordet för x bit för bit. Denna strategi nds x använder färre än H (π ) + 1 frågor i genomsnitt. Men de frågor som Bob ställde kunde vara godtyckliga. I detta dokument undersöker vi följande fråga: Finns det begränsade uppsättningar av frågor som matchar utförandet av Hu man koder, antingen exakt eller ungefärligt? Vårt första huvudresultat visar att för varje distribution π, Bob har en strategi som använder bara frågor av formen "x < c?" och "x = c?", och avslöjar x använder högst H (π )+1 frågor i genomsnitt, matchar prestanda Hu man koder i denna mening. Vi ger också en naturlig uppsättning av O (rn 1/r ) frågor som uppnår en prestanda på högst H (π ) + r, och visar att (rn 1/r ) frågor krävs för att uppnå en sådan garanti. Vårt andra huvudresultat ger en uppsättning Q på 1,25 n+o (n) frågor så att för varje distribution π, Bob kan genomföra en optimal strategi för π med endast frågor från Q. Vi visar också att 1,25 n-o (n) frågor behövs, för i nitelt många n. Om vi tillåter en liten slack av r över den optimala strategin, då ungefär (rn)  och (1/r ) frågor är nödvändiga och tillräckliga.
Dagan m.fl. REF ger en strategi med endast jämförelse- och jämställdhetsfrågor, som ställer högst H(μ) + 1 frågor i genomsnitt.
Twenty (simple) questions
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}