Shannon Theory
Finite-blocklength Analysis

Resolution Limits of Non-Adaptive Querying for Noisy 20 Questions Estimation

Alfred Hero, Lin Zhou

Date & Time

01:00 am – 01:00 am


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.


Alfred Hero

University of Michigan, Ann Arbor

Lin Zhou

University of Michigan, Ann Arbor

Session Chair

Masahito Hayashi

Nagoya University