Abstract:
|
Consider a graph with n vertices, which is embedded in a square lattice with nearest-neighbor edges . 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 along which the associated random variables have distribution N(?, 1), ? > 0, and the random variables away from the path have distribution N(0, 1). We will describe the values of the mean shift ? for which one can reliably detect (in the minimax sense) the presence of the anomalous path, and for which it is impossible to detect.
|