Title: Thresholds For Detecting An Anomalous Path From Noisy Environments,
Abstract: We consider the "searching for a trail in a maze" composite hypothesis
testing problem, in which one attempts to detect an anomalous directed path in
a lattice 2D box of side n based on observations on the nodes of the box. Under
the signal hypothesis, one observes independent Gaussian variables of unit
variance at all nodes, with zero, mean off the anomalous path and mean \mu_n on
it. Under the null hypothesis, one observes i.i.d. standard Gaussians on all
nodes. Arias-Castro et al. (2008) showed that if the unknown directed path
under the signal hypothesis has known the initial location, then detection is
possible (in the minimax sense) if \mu_n >> 1/\sqrt log n, while it is not
possible if \mu_n << 1/ log n\sqrt log log n. In this paper, we show that this
result continues to hold even when the initial location of the unknown path is
not known. As is the case with Arias-Castro et al. (2008), the upper bound here
also applies when the path is undirected. The improvement is achieved by
replacing the linear detection statistic used in Arias-Castro et al. (2008)
with a polynomial statistic, which is obtained by employing a multi-scale
analysis on a quadratic statistic to bootstrap its performance. Our analysis is
motivated by ideas developed in the context of the analysis of random polymers
in Lacoin (2010).