Measurement dependent noisy search: The Gaussian case

摘要: This paper considers the problem of searching for unknown location a target among finite number possible locations by probing multiple simultaneously. Outcome each search measurement is corrupted Gaussian noise whose intensity proportional to probed. We characterize non-asymptotic lower bound on adaptivity gain; i.e. reduction in expected measurements under an adaptive strategies over non-adaptive strategies. Then we investigate gain two complementary asymptotic regimes: one where total area kept fixed but width shrinking or resolution increasing, and other growing. Interestingly, grows distinctly different manner these regimes. In particular, gains are significant later regime when space grows; implying far more critical either large.