论文标题
嘈杂非自适应20个问题问题的分辨率限制
Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem
论文作者
论文摘要
我们建立了与测量依赖性噪声的嘈杂的20个问题问题的估计准确性的基本限制，并引入达到这些限制的最佳非自适应程序。鉴于由超过分辨率概率约束的有限数量的查询，最小的可实现分辨率定义为目标立方体在单位立方体上的估计位置和真实位置之间的绝对差。受到20个问题问题与通道编码问题之间关系的启发，我们在最小的可实现的分辨率上得出了非反应界限，以估计目标位置。此外，将浆果定理应用于我们的非反应界限时，我们获得了二阶渐近近似，以可实现的最佳非自适应查询程序可实现，并具有有限数量的查询数量，这些查询数量有限。我们将二阶结果专门用于几个通道模型的测量依赖性版本，包括二进制对称性，二进制擦除和二进制Z-通道。作为补充，我们建立了用于自适应查询的二阶渐近可实现性，并使用它来绑定自适应查询的好处。
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.
