We establish fundamental limits of tracking a moving target over the unit cube under the framework of 20 questions with measurement-dependent noise. In this problem, there is an oracle who knows the instantaneous location of a target. Our task is to query the oracle as few times as possible to accurately estimate the trajectory of the moving target, whose initial location and velocity is \emph{unknown}. We study the case where the oracle's answer to each query is corrupted by random noise with query-dependent discrete distribution. In our formulation, the performance criterion is the resolution, which is defined as the maximal absolute value between the true location and estimated location at each discrete time during the searching process. We are interested in the minimal resolution of any non-adaptive searching procedure with a finite number of queries and derive approximations to this optimal resolution via the second-order asymptotic analysis.
翻译:我们用基于测量的噪音,在20个问题的框架内,确定了在单元立方体上跟踪移动目标的基本限制。 在这个问题中,有一个神器知道目标的瞬间位置。 我们的任务是尽可能多地询问神器准确估计移动目标的轨迹,其初始位置和速度为 \ emph{ 未知}。 我们研究神器对每个查询的回答因随机噪音和根据查询的离散分布而损坏的案例。 在我们的写法中, 性能标准是分辨率, 它被定义为搜索过程中每个离散时间的真正位置和估计位置之间的最大绝对值。 我们感兴趣的是, 任何非适应性搜索程序的最小解析, 其查询数量和速度有限, 并通过第二顺序的随机测试分析得出对最佳解析的近似值 。