Consider a two dimensional finite graph having side length O(n). Each vertex
of the graph is associated with a random variable, and these are assumed to be
independent. In this setting, we will consider the following hypothesis testing
problem. Under the null, all the random variables have common distribution
N(0, 1), while under the alternative, there is an unknown path (with unknown
initial vertex) having O(n) edges (e.g. a “left to right crossing") along which the
associated random variables have distribution N(μn, 1) for some μn > 0, and the
random variables away from the path have distribution N(0, 1). We will describe
the values of the mean shift μn for which one can reliably detect (in the minimax
sense) the presence of the anomalous path, and for which it is impossible to
detect.