@article {253216, title = {Optimal Detection of Random Walks on Graphs: Performance Analysis via Statistical Physics}, journal = {Technical Report}, year = {2015}, abstract = { We study the problem of detecting a random walk on a graph from a sequence of noisy measurements at every node.\ There are two hypotheses: either every observation is just meaningless zero-mean Gaussian noise, or at each time step exactly one node has an elevated mean, with its location following a random walk on the graph\ over time.\ We want to exploit knowledge of the graph structure and random walk parameters (specified by a Markov chain\ transition matrix) to detect a possibly very weak signal.\ The optimal detector is easily derived, and we focus on the harder problem of characterizing its performance through the\ (type-II) error exponent: the decay rate of the miss probability under a false alarm constraint.The expression for the error exponent resembles the free energy of a spin glass in statistical physics, and we borrow\ techniques from that field to develop a lower bound. Our fully\ rigorous analysis uses large deviations theory to show that the lower bound exhibits a phase transition: strong\ performance is only guaranteed when the signal-to-noise ratio exceeds twice the entropy rate of the random walk.Monte Carlo simulations show that the lower bound fully captures the behavior of the true exponent. }, url = {http://arxiv.org/abs/1504.06924}, author = {Agaskar, A. and Lu, Y.M.} }