The Taub Faculty of Computer Science Events and Talks

In the "20 questions" game Alice picks a probability distribution over the set {1,...,n}, and draws a secret element x from it. Bob's goal is to construct a strategy to reveal x using only "Yes or No" questions, while minimizing the expected number of questions asked. Bob's success is guaranteed if he uses Huffman code, but then he might ask any possible question. In the paper "Twenty (simple) questions", Dagan et al. showed that the minimal number of questions which allows to construct optimal strategies for all distributions, denoted q(n), is much smaller than the number of all questions. They provide lower and upper bounds on q(n) for any n, but calculate it exactly only for some n values. We give a formula for the value of q(n) for any n, and present a new explicit lower bound on q(n). We also generalize some results of Dagan et al. to the "d-ary 20 questions" game, in which every question has d>1 possible answers, instead of only "Yes" and "No".