Twenty Questions with Random Error

Twenty Questions originated as 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. Early versions of the game can be traced to ancient Greece and ancient Rome. Motivated by the Hungarian version of this game, in the middle of the twentieth century, Rényi formulated the game as a mathematical problem of guessing an integer from a finite set, where the oracle could lie either randomly to each question or lie to a finite number of questions. The mathematical study of Twenty Questions is motivated by current applications in many domains: communications; ma-chine learning; and computer vision. The game with an oracle who is allowed a fixed number of lies was also studied by Ulam and Berlekamp and is known as the Rényi-Ulam-Berlekamp game. In contrast, the setting where the oracle lies randomly is less understood. In this monograph, we summarize recent advances in the information theoretical analysis of Twenty Questions with random error. In particular, focusing on the practical application of sensor network target localization, we study a query-dependent channel to model oracle’s noisy response behavior, such as providing a wrong answer or declining to answer a question. We concentrate on non-adaptive query procedures where all questions are designed prior to posing questions. We cover settings relevant to estimating a single target, a single moving target, and multiple targets over the unit cube of a finite dimension. We also consider 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. All of our theoretical results are illustrated using numerical examples. Finally, we discuss future research directions. These include geometry constraints for query sets, low-complexity query procedures, connections to group testing, and practical applications in machine learning and communications.