Detection of Anomalous Path in a Noisy Network

• Activity Number: 69 - Modern Statistical Methods for Multi-Scale and Time Series Data
• Type: Contributed
• Date/Time: Sunday, July 30, 2017 : 4:00 PM to 5:50 PM
• Sponsor: International Indian Statistical Association
• Author(s): Shirshendu Chatterjee* and Ofer Zeitouni
• Companies: City University of New York and Weizmann Institute
• Keywords: network ; anomalous path ; statistical inference ; detection problem ; scan statistics ; minimax

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.