Resolution Limits of Noisy 20 Questions Estimation

09/27/2019
by   Lin Zhou, et al.
0

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 this 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. 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. Our results are then extended to adaptive query procedures, establishing a lower bound on the resolution gain associated with adaptive querying.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro