The entropy of lies: playing twenty questions with a liar

on YouTube ↗23m

" summary

Distributional 20 Questions with up to K lies requires on average H(mu) + K·H2(mu) yes/no queries, where H(mu) + K·H2(mu) is tight (matching lower bound up to lower-order terms) and H2(mu)=Σ p_i·log log(1/p_i). The procedure is an efficient comparison-query binary search that flags suspicious answers, uses 2K+1 majority verification to correct lies, and yields a noisy-sorting corollary replacing the K·log n penalty by K·H2 of the permutation prior.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:26The Twenty questions game
3. 2:43Distributional Twenty questions game
4. 3:41A possible question-asking strategy
5. 4:30Optimal strategy (distributional, no lies)
6. 5:40Distributional Twenty questions with lies
7. 6:30Optimal cost (#questions) in different set
8. 8:28Application: sorting via comparison queste
9. 10:03Upper bound
10. 10:27Binary search on a line Gilbert, Moore's
11. 13:59Correcting lies
12. 17:30Algorithm (sketch)
13. 20:29Lower bound - with lies
14. 22:43Conclusion