Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 196/296 - Student Colloquium

Ery Arias-Castro

UCSD

Searching for a Trail of Evidence in a Maze

Abstract:

Suppose we observe a security network composed of sensors with each sensor returning a value indicating whether the sensor is at risk (high value) or not (low value). ?A typical attack leaves a trail where the sensors return higher-than-normal values.? The goal is to detect a possible attack.? Within a simplified framework, we will see that if the sensor do not return high-enough values (we will quantify that), then detection is impossible. Formal abstract: Consider the complete regular binary tree of depth M oriented from the root to the leaves.? To each node we associate a random variable and those variables are assumed to be independent.? Under the null hypothesis, these random variables have the standard normal distribution while under the alternative, there is a path from the root to a leaf along which the nodes have the normal distribution with mean A and variance 1, and the standard normal distribution away from the path. We show that, as M increases, the hypotheses become separable if, and only if, A is larger than the square root of? 2 ln 2.? We obtain corresponding results for other graphs and other distributions.? The concept of predictability profile plays a crucial role in our analysis. Joint work with Emmanuel Candes, Hannes Helgason and Ofer Zeitouni.

November 29, 2007

11:00 AM

AP&M B402A

****************************