Twenty Questions with Random Error

This monograph provides a self-contained review of information theoretical benchmarks for a statistical learning problem named Twenty Questions with random error. The problem finds diverse applications across domains of communications, signal processing and computer science, e.g., beam alignment in mmWave multiple antenna communication, target localization using sensor networks, and face localization in images and videos. The problem can also find potential applications in other domains where parameter estimation is required in a query-and-answer manner.

The problem of Twenty Questions with random error originated from a parlor game between two players. The game starts from a player named an oracle, who privately thinks of a secret. The other player, called the questioner, tries to guess the secret by querying the oracle with at most twenty questions having Yes/No answers. The mathematical formulation of the problem was pioneered by Alfred R幯yi as a parameter estimation problem, who assumed that oracle could lie randomly to each question and the number of questions can be more than 20. This monograph concentrates on non-adaptive query procedures where all questions are designed prior to posing questions and covers settings relevant to estimating a single target, a single moving target, and multiple targets over the unit cube of a finite dimension. For each case, theoretical benchmarks of optimal query procedures are presented and illustrated via numerical examples. This monograph also considers adaptive querying for a single target to illustrate the benefit of adaptivity. In adaptive querying, each question is designed sequentially using responses to all previous questions. One of the particular features of this monograph is the presentation of second-order asymptotic techniques that provide tighter convergence guarantees for the Twenty Questions searching and tracking problems considered here. These guarantees provide insights into the factors affecting the convergence rates depending on the problem setting and model parameters.

This monograph is suitable for researchers and graduate students who are interested in statistical learning, information theory, communications, signal processing and computer science. In particular, the ideas covered in this monograph demonstrate the application of information theory to a statistical learning problem, with applications in communications, signal processing and computer science. Therefore, people interested in statistical learning and information theory could benefit from knowing how statistical learning problems can be solved via information theoretical tools, and people interested in communications, signal processing and computer science can learn about potential algorithms for practical applications.