2015/04/27 by Ameya Agaskar, Agaskar, Ameya, Yue M. Lu +1
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.1504.06924
openalex publication_date 2015/04/27 · openalex created_date 2022/08/30 · openalex updated_date 2026/07/28
We study the problem of detecting a random walk on a graph from a sequence of\nnoisy measurements at every node. There are two hypotheses: either every\nobservation is just meaningless zero-mean Gaussian noise, or at each time step\nexactly one node has an elevated mean, with its location following a random\nwalk on the graph over time. We want to exploit knowledge of the graph\nstructure and random walk parameters (specified by a Markov chain transition\nmatrix) to detect a possibly very weak signal. The optimal detector is easily\nderived, and we focus on the harder problem of characterizing its performance\nthrough the (type-II) error exponent: the decay rate of the miss probability\nunder a false alarm constraint. The expression for the error exponent resembles\nthe free energy of a spin glass in statistical physics, and we borrow\ntechniques from that field to develop a lower bound. Our fully rigorous\nanalysis uses large deviations theory to show that the lower bound exhibits a\nphase transition: strong performance is only guaranteed when the\nsignal-to-noise ratio exceeds twice the entropy rate of the random walk. Monte\nCarlo simulations show that the lower bound fully captures the behavior of the\ntrue exponent.\n