Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem

Abstract

We establish fundamental limits on estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true locations of a target over a unit cube, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution to estimate the target location. Furthermore, applying the Berry--Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint. We specialize our second-order results to measurement-dependent versions of several channel models including the binary symmetric, the binary erasure and the binary Z- channels. As a complement, we establish a second-order asymptotic achievability bound for adaptive querying and use this to bound the benefit of adaptive querying.

To appear in IEEE Transactions on Information Theory, 2021. The conference version is v1, which appeared in ISIT 2020. In fact, this version is the latest version of arXiv:1909.12954, which includes all the revisions made during to the review progress and thus v2/v3 here should be named v4 of arXiv:1909.12954. This is the reason why there is a substantial text overlap