Title: Detection of Anomalous Path in a Noisy Network
Speaker: Shirshendu Chatterjee (CUNY City College)
Abstract: 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(\mu_n, 1)$ for some $\mu_n > 0$, and the random variables away from the path have distribution $N(0, 1)$. We will describe the values of the mean shift $\mu_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.
This talk is based on a joint work with Ofer Zeitouni, Weizman Institute & NYU.