Resolution Limits of Non-Adaptive Querying for Noisy 20 Questions Estimation
作者：周琳 时间：2020年08月24日 21:36 点击数：
语言：English
发表会议：2020 IEEE International Symposium on Information Theory (ISIT)
发表日期：2020年8月24日
摘要：
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.
原文链接
