Resolution Limits of Non-Adaptive Querying for Noisy 20 Questions Estimation
Author：Lin Zhou Time：August 24, 2020 Number of clicks：
Language：English
Conference：2020 IEEE International Symposium on Information Theory (ISIT)
Date of Publication：August 24, 2020
Abstract：
We study fundamental limits of 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 values of the target random variable, 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. Furthermore, applying the Berry-Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to finite blocklength performance, specifically the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint.
Original Link
